B 树基本概念

B 树是一种平衡的多路搜索树，多用于文件系统、数据库系统的实现，B 树具有以下特点

• 与二叉树不同，一个节点可以存储超过 2 个元素，也可以拥有超过 2 个子树
• 平衡，每个节点的所有子树高度一致，整体高度较矮
• 也具有二叉搜索树的性质，例如对于任意元素，大于所有左子树上的元素而小于所有右子树（以及同节点内右侧的元素）上的元素

对于一棵 5 阶 B 树，每个节点最多可以有 5 个子树

m 阶 B 树的性质（$ m \geq 2 $）

• 设一个节点存储的元素个数为 $ x $
  • 根节点：$ 1 \leq x \leq m-1 $
  • 非根节点：$ (m / 2)(向上取整) - 1 \leq x \leq m - 1 $
• 若一个节点存在子节点，则子节点个数 $ y = x + 1 $
  • 根节点：$ 2 \leq y \leq m $
  • 非根节点：$ (m / 2)(向上取整) \leq y \leq m $

因此，对于常见的 B 树，有

• 3 阶 B 树：$ m = 3 $，任意节点 $ 1 \leq x \leq 3 $，$ 2 \leq y \leq 3 $，因此也称为 2-3 树
• 4 阶 B 树：$ m = 4 $，任意节点 $ 2 \leq x \leq 4 $，$ 2 \leq y \leq 4 $，因此也称为 2-3-4 树
• 5 阶 B 树：$ m = 5 $，任意非根节点 $ 2 \leq x \leq 4 $，$ 3 \leq y \leq 5 $，因此也称为 2-3-4 树

B 树 与 二叉搜索树

将二叉搜索树的节点合并，可以成为 B 树，即多代节点合并称为超级节点，如对于下面的 BST

将 18 和 33 合并，23 和 30 合并，20 和 21 合并，45 和 47 合并，50 和52 合并，即可得到如下的 3 阶 B 树

可以看到，2 代合并的超级节点，最多拥有 4 个子节点（至少是 4 阶B树），而 $ n $ 代合并的超级节点，最多拥有 $ 2^{n $ 个子节点（至少是 $ 2}n $ 阶 B 树）

B 树的操作

搜索

1. 先在节点内部从小到大搜索元素，或者使用二分搜索
2. 如果命中，搜索结束
3. 如果未命中，再去对应的子节点中搜索元素，重复步骤 1

假设搜索 72，首先在根节点做比较，72 大于 40，所以接着在根节点的右子树搜索，72 大于 60 小于 80，继续在 60 和 80 之间的子树寻找，因为 72 大于 70，所以需要继续往 70 的右子树寻找，但是右子树为空，所以得出结论 72 不在该 B 树上

添加

首先明确，新添加的元素必定是添加到叶子节点，对于下面的 4 阶 B 树（每个节点最多容纳 3 个元素，最多 4 个子树）

1. 插入 55，首先在根节点做比较，55 大于 40，所以接着在根节点的右子树搜索，55 小于 60，继续在 60 的左子树寻找，55 大于 50，此时已经在叶子节点，且节点容量足够，所以将 55 插入在 50 的右侧

2. 插入 95，首先在根节点做比较，95 大于 40，所以接着在根节点的右子树搜索，95 大于 80，继续在 80 的右子树寻找，95 大于 90 小于 100，此时已经在叶子节点，且节点容量足够，所以将 95 插入在节点 90 和 100 的中间

此时形成的二叉树如下

如果此时再插入元素 98，那么右下角的叶子节点容量将超过 4 阶 B 树的限制，会导致上溢（overflow）

上溢

对于一棵如下的 5 阶 B 树（局部），如果插入元素 34

• 上溢节点的元素个数必然等于 m（5）
• 假设上溢节点最中间元素的位置为 k（2）
• 将 k 位置的元素向上与父节点合并
• 将 [0,k-1] 和 [k+1,m-1] 位置的元素分裂成 2 个子节点，这 2 个子节点的元素个数，必然都不会低于最低限制 $ (m / 2)(向上取整) - 1 $

• 当然，一次上溢的解决，因为子节点元素合并到父节点，可能导致父节点上溢，则继续按照上面的方法解决，最坏的情况，有可能一直上溢到根节点，导致根节点分裂上溢

• 添加元素导致的上溢，是唯一的可能导致 B 树长高的操作

删除

与 BST 类似，假如需要删除的元素在叶子节点中，那么直接删除即可，例如对于下面的 4 阶 B 树

删除 30，因为是叶子节点，且删除后不会低于 4 阶 B 树的限制，直接删除

假如需要删除的元素在非叶子节点中，参照 BST ，可以先找到前驱或后继元素，覆盖所需删除元素的值，再把前驱或后继元素删除

删除 60，60 的前驱为 55，将 55 覆盖 60，然后将 55 从 54 和 55 节点中删除

因为非叶子节点的前驱或后继元素，必定在叶子节点中，所以这里实际上删除的前驱或后继元素，就是最开始提到的情况，删除的元素在叶子节点中，也就是说真正的删除元素都发生在叶子节点中。

下溢

如下有一棵 5 阶 B 树（非根节点元素个数大于等于2），如果删除 22，该叶子节点的元素个数可能会低于最低限制，此时便发生下溢（underflow）

下溢节点的元素数量必然等于 $ m/2(向上取整) - 2 $

1. 如果下溢节点临近的兄弟节点，有至少 $m/2(向上取整)$ 个元素，可以向其“借”一个元素

• 绿色节点在删除一个元素后，节点元素个数低于最低限制（$ \geq m/2(向上取整) - 1 $）
  • 将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
  • 用兄弟节点的元素 a（最大的元素）替代父节点的元素 b
  • 注意子节点d也需要调整
  • 这种操作其实就是旋转

2. 如果下溢节点临近的兄弟节点，最多只有 $ m/2(向下取整) - 1 $ 个元素，即“不够借”
   

• 将父节点的元素 b 挪下来跟左右子节点进行合并
• 合并后的节点元素个数等于 $ m/2(向上取整) + m/2(向上取整) - 2 $，不超过 $ m-1 $
• 当然，这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播到根节点

删除元素导致的下溢，是唯一的可能导致 B 树变矮的操作

参考

• 恋上数据结构与算法（第一季）
• 小码哥《恋上数据结构与算法》笔记（十）：B树