B树

1. B树

从二叉查找树演变成 n 叉查找树

struct Node{
	int key[4];  // 最多n-1个关键字
	Node* child[5]; // 最多n个孩子
	int num; // 结点内有几个关键字
}

2. 保证查找效率

若关键词太少则查找效率太低
策略：

  1. m叉除根节点外至少 ⌈m/2⌉ 个分叉，即至少含有 ⌈m/2⌉−1 关键字
  2. 保证每个子树的高度都是相同的

满足以上策略就是 B 树

3. 插入

B树每个结点关键词范围 ⌈m2⌉−1≤n≤m−1

以五叉树为例，先查找到插入的位置，如果插入后超过能存储的关键词数量则在 ⌈m/2⌉ 处分裂成两部分，中间元素插入到上一级。依次递归向上。

超过上限
image.png
分裂，把关键词提到父结点位置
image.png
注意每次插入的结点都是插在最底层的结点

中间的关键词提到父节点指向当前结点指针的右边位置
image.png

父节点超出情况，父节点继续分裂
image.png
image.png

4. 删除

删除非终端结点可以统一转化成删除终端结点：找直接前驱或直接后继顶替当前非终端结点的，然后判断当前终端结点内的关键词数量是否满足 ⌈m2⌉−1≤n≤m−1

因此产生以下三种情况：

  1. 直接删除关键词后满足关键词数量
  2. 兄弟够借，把兄弟的元素拿过来，即把后继代替当前删除元素和后继的后继放入根节点
  3. 兄弟不够借就合并，合并两个兄弟结点的时候需要把父节点中夹在两结点中间的关键词也合并进来

image.png

合并
image.png
image.png

https://www.bilibili.com/video/BV1b7411N798/?p=79&spm_id_from=pageDriver&vd_source=b23e4c35b835b062551fba1278a3ecc7