描述
B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。 –摘自维基百科
B树的阶
B树每个节点最多包含k个孩子，k被成为B树的阶。k的大小取决于磁盘页的大小。
特征
- 根节点至少有两个孩子
- 每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <= m
- 每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
- 所有叶子节点都位于同一层
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
优点
一个Ｂ树通过约束所有叶子节点在相同深度来保持平衡。深度在元素添加至树的过程中缓慢增长，而整体深度极少地增长，并导致所有叶子节点与根节点距离加1。
在存取节点数据所耗时间远超过处理节点数据所耗时间的情况下，Ｂ树在可选的实现中拥有很多优势，因为存取节点的开销被分摊到里层节点的多次操作上。这通常出现在当节点存储在二级存储器如硬盘存储器上。通过最大化内部里层节点的子节点的数量，树的高度减小，存取节点的开销被缩减。另外，重新平衡树的动作也更少出现。子节点的最大数量取决于，每个子节点必需存储的信息量，和完整磁盘块的大小或者二次存储器中类似的容量。虽然2-3 树更易于解释，实际运用中，Ｂ树使用二级存储器，需要要大量数目的子节点来提升效率。
B树运用的理念
- 保持键值有序，以顺序遍历
- 使用层次化的索引来最小化磁盘读取
- 使用不完全填充的块来加速插入和删除
- 通过优雅的遍历算法来保持索引平衡
- B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。