数据结构 B树

B 树基本概念

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

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

5阶B树

对于一棵 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

BST合并

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

3阶B树

可以看到,2 代合并的超级节点,最多拥有 4 个子节点(至少是 4 阶B树),而 $ n $ 代合并的超级节点,最多拥有 $ 2^n $ 个子节点(至少是 $ 2^n $ 阶 B 树)

B 树的操作

搜索

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

B树的搜索

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

添加

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

B树的添加1

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

此时形成的二叉树如下

B树的添加2

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

上溢

对于一棵如下的 5 阶 B 树(局部),如果插入元素 34

B树上溢1

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

B树上溢2

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

B树上溢3

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

删除

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

B树的删除1

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

B树的删除2

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

B树的删除3

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

B树的删除4

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

下溢

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

B树下溢1

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

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

B树下溢2

  • 绿色节点在删除一个元素后,节点元素个数低于最低限制($ \geq m/2(向上取整) - 1 $)
    • 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
    • 用兄弟节点的元素 a(最大的元素)替代父节点的元素 b
    • 注意子节点d也需要调整
    • 这种操作其实就是旋转
  1. 如果下溢节点临近的兄弟节点,最多只有 $ m/2(向下取整) - 1 $ 个元素,即“不够借”

B树下溢3

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

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

参考