B树

B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让我们在O(log n)的时间复杂度内查找、插入和删除数据。一棵m阶的B树，或者为空或者满足以下条件：每个节点至多有m棵子树；根节点或为叶节点，或至少两棵子树；中间节点至少m/2棵子树；叶节点均在同一层次，且不含信息（实际为标志查找失败使用）；所有叶子节点包含全部关键字信息及指向记录的指针，且按次序链接。B树常作为数据库和文件系统的索引结构。