B 树

引入

在计算机科学中，B 树（B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

在 B 树中，有两种节点：

1. 内部节点（internal node）：存储了数据以及指向其子节点的指针。
2. 叶子节点（leaf node）：与内部节点不同的是，叶子节点只存储数据，并没有子节点。

树是一种数据结构。树用多个节点储存元素。某些节点存在一定的关系，用连线表示。二叉树是一种特殊的树，每个节点最多有两个子树。二叉树常用于实现二叉搜索树和二叉堆。 而

性质

首先介绍一下一棵 阶的 B 树的特性。 表示这个树的每一个节点最多可以拥有的子节点个数。一棵 阶的 B 树满足的性质如下：

1. 每个节点最多有 个子节点。
2. 每一个非叶子节点（除根节点）最少有 个子节点。
3. 如果根节点不是叶子节点，那么它至少有两个子节点。
4. 有 个子节点的非叶子节点拥有 个键，且升序排列，满足 。
5. 每个节点至多包含 个键。
6. 所有的叶子节点都在同一层。

一个简单的图例如下：

过程

与

查找

B 树中的节点包含有多个键。假设需要查找的是 ，那么从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。 子树值的范围被它的父节点的键确定。因为是从根节点开始的二分法查找，所以查找一个键的代码如下：

遍历

B 树的中序遍历与二叉搜索树的中序遍历也很相似，从最左边的孩子节点开始，递归地打印最左边的孩子节点，然后对剩余的孩子和键重复相同的过程。 最后，递归打印最右边的孩子节点。

遍历的代码如下：

插入

为了方便表述，插入设定为在以 为根节点的 B 树中插入一个值为 的新节点。

一个新插入的 总是被插入到叶子节点。与二叉搜索树的插入操作类似，从根节点开始，向下遍历直到叶子节点，将值为 的新节点插入到相应的叶子节点。 与二叉搜索树不同的是，通过最小度定义了一个节点可以包含键的个数的一个取值范围，所以在插入一个新节点时，就需要确认插入这个叶子节点之后，它的父节点是否超出该节点本身最大可容纳的节点个数。

针对一棵高度为 的 阶 B 树，插入一个元素时，首先要验证该元素在 B 树中是否存在，如果不存在，那么就要在叶子节点中插入该新的元素，此时分 3 种情况：

1. 如果叶子节点空间足够，即该节点的关键字数小于 ，则直接插入在叶子节点的左边或右边；
2. 如果空间满了以至于没有足够的空间去添加新的元素，即该节点的关键字数已经有了 个，则需要将该节点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右节点中，中间关键字元素上移到父节点中，而且当节点中关键元素向右移动了，相关的指针也需要向右移。
   1. 从该节点的原有元素和新的元素中选择出中位数
   2. 小于这一中位数的元素放入左边节点，大于这一中位数的元素放入右边节点，中位数作为分隔值。
   3. 分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。

如果一直分裂到根节点，那么就需要创建一个新的根节点。它有一个分隔值和两个子节点。

这就是根节点并不像内部节点一样有最少子节点数量限制的原因。每个节点中元素的最大数量是 。当一个节点分裂时，一个元素被移动到它的父节点，但是一个新的元素增加了进来。所以最大的元素数量 必须能够被分成两个合法的节点。 如果 是奇数，那么 ，总共有 个元素，一个新的节点有 个元素，另外一个有 个元素，都是合法的节点。如果 是偶数，那么 , 总共有 个元素。一半是 ，正好是节点允许的最小元素数量。

插入的代码如下：

删除

B 树的删除操作相比于插入操作更为复杂，因为删除之后经常需要重新排列节点。

与 B 树的插入操作类似，必须确保删除操作不违背 B 树的特性。正如插入操作中每一个节点所包含的键的个数不能超过 一样，删除操作要保证每一个节点包含的键的个数不少于 个（除根节点允许包含比 少的关键字的个数）。

有两种常用的删除策略：

1. 定位并删除元素，然后调整树使它满足约束条件。
2. 从上到下处理这棵树，在进入一个节点之前，调整树使得之后一旦遇到了要删除的键，它可以被直接删除而不需要再进行调整。

下面介绍使用第一种策略的删除。

首先，查找 B 树中需删除的元素，如果该元素在 B 树中存在，则将该元素在其节点中进行删除；删除该元素后，首先判断该元素是否有左右孩子节点， 如果有，则上移孩子节点中的某相近元素（"左孩子最右边的节点" 或 "右孩子最左边的节点"）到父节点中，然后是移动之后的情况；如果没有，直接删除。

1. 某节点中元素数目小于 ， 向上取整，则需要看其某相邻兄弟节点是否丰满。
2. 如果丰满（节点中元素个数大于 ），则向父节点借一个元素来满足条件。
3. 如果其相邻兄弟都不丰满，即其节点数目等于 ，则该节点与其相邻的某一兄弟节点进行 "合并" 成一个节点。

接下来用一个 5 阶 B 树为例，详细讲解删除的操作。

如图所示，接下来要依次删除 8，20，18，5。 首先要删除元素 8。先查找到元素 8 在叶子节点中，删除 8 后叶子节点的元素个数为 2，符合 B 树的规则。然后需要把元素 11 和 12 都向前移动一位。完成后如图所示。

下一步，删除 20，因为 20 没有在叶子节点中，而是在中间节点中找到，可以发现 20 的继承者是 23（字母升序的下个元素），然后需要将 23 上移到 20 的位置，之后将孩子节点中的 23 进行删除。 删除后检查一下，该孩子节点中元素个数大于 2，无需进行合并操作。

所以这一步之后，B 树如下图所示。

下一步删除 18，18 在叶子节点中，但是该节点中元素数目为 2，删除导致只有 1 个元素，已经小于最小元素数目 2。 而由前面已经知道：如果其某个相邻兄弟节点中比较丰满（元素个数大于 ），则可以向父节点借一个元素，然后将最丰满的相邻兄弟节点中上移最后或最前一个元素到父节点中。 在这个实例中，右相邻兄弟节点中比较丰满（3 个元素大于 2），所以先向父节点借一个元素 23 下移到该叶子节点中，代替原来 19 的位置。19 前移。 然后 24 在相邻右兄弟节点中，需要上移到父节点中。最后在相邻右兄弟节点中删除 24，后面的元素前移。

这一步之后，B 树如下图所示。

最后一步需要删除元素 5，但是删除后会导致很多问题。因为 5 所在的节点数目刚好达标也就是刚好满足最小元素个数 2。 而相邻的兄弟节点也是同样的情况，删除一个元素都不能满足条件，所以需要该节点与某相邻兄弟节点进行合并操作；首先移动父节点中的元素（该元素在两个需要合并的两个节点元素之间）下移到其子节点中。 然后将这两个节点进行合并成一个节点。所以在该实例中，首先将父节点中的元素 4 下移到已经删除 5 而只有 6 的节点中，然后将含有 4 和 6 的节点和含有 1，3 的相邻兄弟节点进行合并成一个节点。

这一步之后，B 树如下图所示。

但是这里观察到父节点只包含了一个元素 7，这就没有达标（因为非根节点包括叶子节点的元素数量 必须满足于 ，而此处的 ）。 如果这个问题节点的相邻兄弟比较丰满，则可以向父节点借一个元素。而此时兄弟节点元素刚好为 2，刚刚满足，只能进行合并，而根节点中的唯一元素 13 下移到子节点。 这样，树的高度减少一层。

所以最终的效果如下图。

删除的伪代码如下：

B-Tree-Delete-Key(x, k) 
if not leaf[x] then 
    y ← Preceding-Child(x) 
    z ← Successor-Child(x) 
    if n[[y] > t − 1 then 
        k' ← Find-Predecessor-Key(k, x)]() 
        Move-Key(k', y, x) 
        Move-Key(k, x, z) 
        B-Tree-Delete-Key(k, z) 
    else if n[z] > t − 1 then 
        k' ← Find-Successor-Key(k, x) 
        Move-Key(k', z, x) 
        Move-Key(k, x, y) 
        B-Tree-Delete-Key(k, y) 
    else 
        Move-Key(k, x, y) 
        Merge-Nodes(y, z) 
        B-Tree-Delete-Key(k, y) 
    else (leaf node) 
    y ← Preceding-Child(x) 
    z ← Successor-Child(x) 
    w ← root(x) 
    v ← RootKey(x) 
        if n[x] > t − 1 then Remove-Key(k, x) 
        else if n[y] > t − 1 then 
            k' ← Find-Predecessor-Key(w, v) 
            Move-Key(k', y,w) 
            k' ← Find-Successor-Key(w, v) 
            Move-Key(k',w, x) 
            B-Tree-Delete-Key(k, x) 
        else if n[w] > t − 1 then 
            k' ← Find-Successor-Key(w, v) 
            Move-Key(k', z,w) 
            k' ← Find-Predecessor-Key(w, v) 
            Move-Key(k',w, x) 
            B-Tree-Delete-Key(k, x) 
        else 
            s ← Find-Sibling(w) 
            w' ← root(w) 
                if n[w'] = t − 1 then 
                    Merge-Nodes(w',w) 
                    Merge-Nodes(w, s) 
                    B-Tree-Delete-Key(k, x)
                else
                    Move-Key(v,w, x)
                    B-Tree-Delete-Key(k, x)

B 树优势

之前已经介绍过二叉查找树。但是这类型数据结构的问题在于，由于每个节点只能容纳一个数据，导致树的高度很高，逻辑上挨着的节点数据可能离得很远。

考虑在磁盘中存储数据的情况，与内存相比，读写磁盘有以下不同点：

1. 读写磁盘的速度相比内存读写慢很多。
2. 每次读写磁盘的单位要比读写内存的最小单位大很多。

由于读写磁盘的这个特点，因此对应的数据结构应该尽量的满足 "局部性原理"："当一个数据被用到时，其附近的数据也通常会马上被使用"，为了满足局部性原理， 所以应该将逻辑上相邻的数据在物理上也尽量存储在一起。这样才能减少读写磁盘的数量。

所以，对比起一个节点只能存储一个数据的 BST 类数据结构来，要求这种数据结构在形状上更 "胖"、更加 "扁平"，即：每个节点能容纳更多的数据， 这样就能降低树的高度，同时让逻辑上相邻的数据都能尽量存储在物理上也相邻的硬盘空间上，减少磁盘读写。

参考资料

• B 树 - 维基百科，自由的百科全书
• B 树详解
• B 树、B + 树索引算法原理（上）
• B 树，B + 树详解