B树的性质以及解决上溢和下溢
B树的性质以及解决上溢和下溢
B树是一种平衡的多路搜索树，在文件系统和数据库实现中有着广泛的应用。本文将详细介绍B树的性质、搜索、元素添加和删除等操作，并通过具体的例子和图示，帮助读者理解B树的上溢和下溢问题及其解决方案。
一、B树
B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现。
观察上边的B树结构，B树具有几个明显的特质：
a：每个结点可以有多个元素，也可以有2个以上的分支；
b：树比较矮；
c：每个节点的子树高度一致；
二、B树的性质
假设有一颗m阶的B树（m>=2）
假设一个节点的存储元素个数为x：
1：根节点：1 <= x <= m-1;
2: 非根节点： ┌ m/2 ┐ (向上取整)- 1 <= x <= m − 1
3：如果有子结点，子结点的个数：y=x+1
根结点： 2 <= y <= m;
非根节点：┌ m/2 ┐ <= y <= m
比如 m = 3，2 ≤ y ≤ 3，因此可以称为（2, 3）树、2-3树
比如 m = 4，2 ≤ y ≤ 4，因此可以称为（2, 4）树、2-3-4树
比如 m = 5，3 ≤ y ≤ 5，因此可以称为（3, 5）树
三、B树的搜索
1、先在根节点内部从小到大搜索元素；
2、 如果命中，搜索结束；
3、 如果未命中，再去对应的子结点搜索，重复步骤1
四、 元素添加
新添加的元素必定是会添加到叶子结点
4.1、普通添加
给定一颗4阶B树：
添加两个元素55,95
如果这个时候在往里添加一个元素97，这个时候右下角结点的元素个数将超过上限
这种现象称为上溢 overflow
4.2、 解决上溢
上溢结点的元素个数必然为m，假设上溢结点最中间的元素为k，将[0,k-1] 和 [k+1,m-1] 位置的元素分裂成两个子结点，元素k和父结点结合。
一次上溢解决后，可能会导致父结点也出现上溢情况，按照上述的方法解决即可。
所以新增元素97后就变成了
继续新增元素52,54后，继续处理上溢
五、删除元素
5.1、元素在叶子结点
直接删除即可
删除元素30
5.2、元素在非叶子结点
先找到前驱或者后驱元素，覆盖所需删除元素。再将原先的前驱或者后驱元素从叶子结点中删除。
比如删除元素60
5.3、删除下溢
删除元素22，结点元素就只剩一个了。元素个数低于最低限制，这种现象称为下溢。underflow
解决下溢的方法有两种：
5.3.1 方法1
我们知道，下溢元素节点的个数必然为 ┌ m/2 ┐-2。
如果下溢结点的附近的兄弟结点的元素个数有至少┌ m/2 ┐个元素，那么就向兄弟结点借一个元素。
a： 将父结点的元素b插入到下溢结点的起始位置；
b： 用兄弟结点中的最大元素a代替父结点中的元素。
这种操作就是旋转。
5.3.2 方法2
如果兄弟结点的元素个数只有┌ m/2 ┐-1个元素
a：将父结点的元素b挪下来跟左右结点进行合并。
b：合并后元素结点个数为 ┌ m/2 ┐-1 + ┌ m/2 ┐-2 + 1= ┌ m/2 ┐+┌ m/2 ┐-2 不超过m-1
c：这个操作可能会导致父结点下溢。
所以下边这个b树
删除元素22后:
六、其他
B树的在线生成模型