B树是一种平衡的多路搜索树
,多用于文件系统、数据库的实现
可能现在我们还不清楚B树
是干啥的,但等我学完了之后如果有人再问我们
请问你心里有
B树
吗?我:有!
B树是一种平衡的多路搜索树
,多用于文件系统、数据库的实现
B树长这样(即最多拥有几个结点就叫几阶B树):
通过我们对B树
的仔细观察,我们似乎能发现一些B树的特点:
- 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
- 拥有二叉搜索树的一些性质
- 平衡,每个节点的所有子树高度一致
- 比较矮(高度都为3)
为什么叫
B树
呢?有一种说法是因为非常平衡(Balance)
,可以看到B树的高度都很矮那怎么区分是
几阶B树
呢? 我们看结点最多拥有多少个子结点
,它就是多少阶B树
假设一个结点存储的元素个数为
x
我们有以下性质:
-
如果该结点是
根结点
,那么它的元素个数x满足:1 <= x <= m-1
例如上面的四阶B树,我们可以推断出其根结点元素个数必须大于等于1且小于等于3
-
如果该结点是
非根结点
,其元素个数x满足:┌ m/2 ┐ − 1 ≤ x ≤ m − 1
(m/2向上取整) -
如果有子结点,子结点个数
y = x + 1
,即分支个数等于当前结点元素个数+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)树
- 比如 m = 6,3 ≤ y ≤ 6,因此可以称为(3, 6)树
- 比如 m = 7,4 ≤ y ≤ 7,因此可以称为(4, 7)树
思考:如果 m = 2,那B树是什么样子?
很显然根结点的子结点:2 <= y <=2,非根结点的子结点:1<= y <=2,显然就是一棵BST
你猜数据库实现中一般用几阶B树?
数据库里的B树一般是
200 ~ 300
阶,即一个结点能存储200到300个元素
我们先来看同一组数字组成的B树和BST树
其实我们可以看到我们将BST简单处理就能得到3阶B树
所以我们将BST的某些父子结点合并就能将其变成一棵B树
我们可以的出一些重要的结论:
-
B树 和 二叉搜索树,在逻辑上是等价的
-
多代节点合并,可以获得一个超级节点
超级结点指的是B树上这种能同时存储多个数据的结点,即普通BST可以通过将子父祖结点合并从而得到超级结点
这里我们也有一些结论:
- 2代合并的超级节点,最多拥有 4 个子节点(至少是 4阶B树)
- 3代合并的超级节点,最多拥有 8 个子节点(至少是 8阶B树)
- n代合并的超级节点,最多拥有 2 n个子节点( 至少是 2^n阶B树)
-
m阶B树,最多需要 log2m 代合并
搜索
其实B树的搜索和BST的搜索过程非常类似
具体过程为:
- 先在节点内部从小到大开始搜索元素
- 如果命中,搜索结束
- 如果未命中,再去对应的子节点中搜索元素,重复步骤 1
添加
我们首先需要知道:
新添加的元素必定是添加到叶子节点
这点性质和BST一样,BST插入一定会插入到叶子结点中,因为BST排序的性质,之前的元素都是排序好的
我们演示一下:
如果我们现在还要插入98呢?(假设这是一棵 4阶B树)
我们首先由B树的性质可以知道,四阶B树的叶子结点内存放的元素个数最多为3个,插入98显然会出现问题:
- 最右下角的叶子节点的元素个数将超过限制
- 这种现象可以称之为:
上溢(overflow)
为了更好的分析上溢问题,这里以五阶B树进行举例
我们知道五阶B树一个结点中最多存储4个结点,如果超出了我们就称发生了上溢
我们知道一旦发生了上溢现象,那么其元素个数一定等于阶数,即
- 上溢节点的元素个数必然等于 m
解决:
-
假设上溢节点最中间元素的位置为 k
-
将 k 位置的元素向上与父节点合并
-
将 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点
这 2 个子节点的元素个数,必然都不会低于最低限制(
┌ m/2 ┐ − 1
)
一次分裂完毕后,有可能导致父节点上溢,依然按照上述方法解决
最极端的情况,有可能一直分裂到根节点
我们来看一个比较合理的例子:
我们现在要在下面的B树上插入98
这个结点
显然结点95
需要上溢
我们插入结点52
我们插入结点54
,显然这个时候结点52
会发生上溢现象且其父结点也会发生上溢
上溢是唯一可能让B树长高的情况
假如需要删除的元素在叶子节点中,那么直接删除即可
例如我们要删除结点30
,我们直接删除即可
假如需要删除的元素在非叶子节点中,例如我们要删除结点60
显然我们不能直接删除,因为如果删除了,那么结点40
会有三个子结点,这显然是不符合B树性质的(┌ m/2 ┐ − 1 ≤ x ≤ m − 1
)
这里我们的做法其实和二叉搜索树
一样
- 先找到前驱或后继元素,覆盖所需删除元素的值
- 再把前驱或后继元素删除
我们先找到前驱,即先找到左子树,再找左子树中最大的(一直往右找),找到元素55
,我们用55
覆盖掉我们想要删除的结点60
,接着我们再将结点55
删除
注意:
- 非叶子节点的前驱或后继元素,
必定在叶子节点中
- 所以这里的删除前驱或后继元素 ,就是最开始提到的情况:
删除的元素在叶子节点中
- 真正的删除元素都是发生在叶子节点中
假设我们有一棵五阶B树,我们现在需要删除结点22
我们会发现:叶子节点被删掉一个元素后,元素个数可能会低于最低限制( ≥ ┌ m/2 ┐ − 1 )
这种现象称为:这种现象称为:下溢(underflow)
这里我们有几个结论:
- 下溢节点的元素数量必然等于
┌ m/2 ┐ − 2
- 如果下溢节点临近的兄弟节点,有至少
┌ m/2 ┐
个元素,可以向其借一个元素
所以我们对下溢的解决方法是(父结点下来,挑一个兄弟结点的孩子做父亲):
- 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
- 用兄弟节点的元素 a(最大的元素)替代父节点的元素 b
- 这种操作其实就是:
旋转
如果下溢节点临近的兄弟节点,只有 ┌ m/2 ┐ − 1
个元素,显然就不能通过旋转解决下溢问题,这时我们需要通过合并来解决
- 将父节点的元素
b
挪下来跟左右子节点进行合并
- 合并后的节点元素个数等于
┌ m/2 ┐ + ┌ m/2 ┐ − 2
,不超过m − 1
这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播
如果一直下溢到根结点,根结点如果元素个数不够,就会和子结点合并,这样B树高度就会减一
请画出四阶B树添加元素从1到20的图
可以在这个网站上看B树生长的过程:https://cdn.fengxianhub.top/eureka-static/Visualization/BTree.html
最后面结果就是这样的: