数据结构 B树
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
假设搜索 72,首先在根节点做比较,72 大于 40,所以接着在根节点的右子树搜索,72 大于 60 小于 80,继续在 60 和 80 之间的子树寻找,因为 72 大于 70,所以需要继续往 70 的右子树寻找,但是右子树为空,所以得出结论 72 不在该 B 树上
添加
首先明确,新添加的元素必定是添加到叶子节点,对于下面的 4 阶 B 树(每个节点最多容纳 3 个元素,最多 4 个子树)
- 插入 55,首先在根节点做比较,55 大于 40,所以接着在根节点的右子树搜索,55 小于 60,继续在 60 的左子树寻找,55 大于 50,此时已经在叶子节点,且节点容量足够,所以将 55 插入在 50 的右侧
- 插入 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 $
- 如果下溢节点临近的兄弟节点,有至少 $m/2(向上取整)$ 个元素,可以向其“借”一个元素
- 绿色节点在删除一个元素后,节点元素个数低于最低限制($ \geq m/2(向上取整) - 1 $)
- 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
- 用兄弟节点的元素 a(最大的元素)替代父节点的元素 b
- 注意子节点d也需要调整
- 这种操作其实就是旋转
- 如果下溢节点临近的兄弟节点,最多只有 $ m/2(向下取整) - 1 $ 个元素,即“不够借”
- 将父节点的元素 b 挪下来跟左右子节点进行合并
- 合并后的节点元素个数等于 $ m/2(向上取整) + m/2(向上取整) - 2 $,不超过 $ m-1 $
- 当然,这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播到根节点
删除元素导致的下溢,是唯一的可能导致 B 树变矮的操作
参考
本博客所有文章除特别声明外,均采用 知识共享署名-相同方式共享 4.0 国际许可协议 ,转载请注明出处!