9、B树

2023-10-03 本文已影响0人史记_d5da

1、概念

B树是一种平衡多路搜索树，多用于文件系统、数据库的实现。

1.1、m阶B数的性质

假设一个节点存储的元素个数为x
根节点：1 $\leq$ x $\leq$ m-1
非根节点： $\lceil m/2 \rceil$ -1 $\leq$ x $\leq$ m-1
如果有子节点，子节点个数y=x+1
根节点：2 $\leq$ y $\leq$ m
非根节点： $\lceil m/2 \rceil$ $\leq$ y $\leq$ m

4阶B树

1.2、B树VS二叉搜索树

B树和二叉搜索树在逻辑上等价的
多代节点合并可以获得一个超级节点
n代合并的超级节点，最多拥有 $2^n$ 个子节点（至少是 $2^n$ 阶B树）
m阶B树，最多需要 $\log_2m$ 代合并

1.3、搜索

跟二叉搜索树的搜索类似
1、先在节点内部从小到大开始搜索元素
2、如果命中，搜索结束
3、如果未命中，再去对应的子节点中搜索元素，重复步骤1

1.4、添加

新添加的元素必定是添加到叶子节
点

1.5、在添加过程中可能会出现上溢的情况

m阶B树上溢的节点个数必然为m
1、假设上溢的位置为k，将k的元素向上与父节点合并
2、将[0,k]和[k+1,m-1]位置的元素分裂成2个子节点，这两个子节点的个数，必然都不会低于最低限制 $\lceil m/2 \rceil$ -1
3、一次分裂完毕后可能会导致父节点上溢，依然按照上述方法解决，最极端的情况，可能一直分裂到根节点。
如下为5阶B树插入34元素的分裂过程

添加34

1.6、假如需要删除的元素在非叶子节点中

1、先找到前驱或后继元素，覆盖所需删除元素的值
2、再把前驱或后继元素删除

1.7、删除-下溢

叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ $\geq$ $\lceil m/2 \rceil$ -1）
这种现象被称为下溢
下溢节点的元素数量必然等于 $\lceil m/2 \rceil$ -2
如果下溢节点临近的兄弟节点，有至少 $\lceil m/2 \rceil$ 个元素，可以向下借一个元素