搜索步骤
跟二叉搜索树的搜索类似
步骤1. 先在节点内部从小到大开始搜索元素
步骤2. 如果命中，搜索结束
步骤3. 如果未命中，再去对应的子节点中搜索元素，重复步骤 1
查找操作
在二叉树中，每个结点只有一个元素。但是在B-Tree中，每个结点都可能包含多个元素，并且非叶子结点在元素的左右都有指向子结点的指针。
如果需要查找一个元素，那流程是怎么样的呢？我们看下图，如果我们要在下面的B-Tree中找到关键字24，那流程如下
从这个流程我们能看出，B-Tree的查询效率好像也并不比平衡二叉树高。但是查询所经过的结点数量要少很多，也就意味着要少很多次的磁盘IO，这对 性能的提升是很大的。
插入操作
从已有的B树插入
新添加的元素必定是添加到叶子节点(就是最后一排),
插入详细步骤:
**
插入55
插入95
**
再插入 98 呢？（假设这是一棵 4阶B树）
最右下角的叶子节点的元素个数将超过限制
这种现象可以称之为：上溢（overflow）
添加上溢的解决
假如是五阶b树,那么一个节点最多四个元素.
1.上溢节点的元素个数必然等于 m
假如说是五阶b树,那么m就是5.
2.假设上溢节点最中间元素的位置为 k
假如说中间元素是34
3.将 k 位置的元素向上与父节点合并
4.将 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点
因为34和父节点合并了,所以以前和34节点平级的节点现在变成了34节点的子节点
一次分裂完毕后，有可能导致父节点上溢，父节点依然按照上述方法,从步骤2开始重新解决
最极端的情况，有可能一直分裂到根节点**
这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ − 1）
假如说m是5,那么就是子节点最少要存储2个元素
插入操作,上溢演示
原始b树:
插入 98:
95向上合并了.
插入52:
插入 54
54 插入之后52向上合并,成为52 60 80 95 , 然后60又向上合并,根节点成为40 60
从空的B树开始插入
B树特性
1、每个结点最多m个子结点。
2、除了根结点和叶子结点外，每个结点最少有m/2（向上取整）个子结点。
3、如果根结点不是叶子结点，那根结点至少包含两个子结点。
4、所有的叶子结点都位于同一层。
5、每个结点都包含k个元素（关键字），这里m/2≤k
B树的删除操作
真正的删除元素都是发生在叶子结点中.
假如需要删除的元素在叶子节点中，那么直接删除即可
假如需要删除的元素在叶子节点(最底层节点)中，那么直接删除即可
如果删除非叶子结点呢?
假如需要删除的元素在非叶子节点中
1.先找到前驱或后继元素，覆盖所需删除元素的值
再把前驱或后继元素删除
删除 60:
**
删除60,先找到60的前驱元素,就是55(通过52找的), 然后删除60,把55提出来覆盖掉原来60的位置
你发现了么,删除非叶子节点的数据, 真正被删掉的还是叶子节点的数据,就像上面的,你删除60,但是真正被删除的是原来55的位置.
删除下溢
叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ ≥ ┌ m/2 ┐ − 1 ）
这种现象称为：下溢（underflow）
◼下溢节点的元素数量必然等于 ┌ m/2 ┐ − 2
◼如果下溢节点临近的兄弟节点，有至少 ┌ m/2 ┐ 个元素，可以向其借一个元素
将父节点的元素 b 插入到下溢节点的 0 位置（0位置就是最小位置）
用兄弟节点的元素 a（最大的元素）替代父节点的元素 b
这种操作其实就是：旋转,
将父节点挪到右分支子节点的左边, 将原来父节点左分支最大的a节点上升为父节点.
如果下溢节点临近的兄弟节点，只有 ┌ m/2 ┐ − 1 个元素
将父节点的元素 b(b是中间元素) 挪下来跟左右子节点进行合并. 左节点是蓝色的节点,右节点是绿色的节点
合并后的节点元素个数等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超过 m − 1 ,不会出现上溢的情况.
结论:
说白了,就是一个节点如何产生下溢的话,就看看兄弟节点能不能借用一个,如果没有的话就父节点的中间元素拉下来向下合并就可以了
这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播
若有收获，就点个赞吧
0 人点赞
