B树-多路搜索树

B树

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

特点

m 阶的意思：就是意味着这棵 B树最多有 m 个子节点，每个节点最多存储 m-1 个元素。

1、假设一个节点存储的元素个数为 x

2、如果有子节点，子节点个数为 y = x + 1

4 阶 B树如下图所示

数据库实现中一般用【几阶B树】？

一般是 200 ~ 300

思考：如果 m = 2，那【B树】是什么样子的？

B树和二又搜索树，在逻辑上是等价的（只不过是【B树】一个节点融合了多个元素）
多代节点合并，可以获得一个超级节点
- 2 代合并的超级节点，最多拥有 4 个子节点（至少是 4阶B树）
- 3 代合并的超级节点，最多拥有 8 个子节点（至少是 8阶B树）
- n 代合并的超级节点，最多拥有 (2^n) 个子节点（至少是 2^n 阶B树）
m阶B树，最多需要 log2(m) 代合并

二叉搜索树

B树

当在【B树】中添加元素时，可能会导致上溢（Overflow）情况，即节点中的关键字个数超过了节点的容量。

上溢节点的元素个数必然等于 m。
假设上溢节点最中间元素的位置为 k
- 将 k 位置的元素向上与父节点合并
- 将 [0, k-1] 和 [k+1, m-1] 位置的元素分裂成 2 个子节点
  - 这 2 个子节点的元素个数，必然都不会低于最低限制 (┌ m/2 ┐ - 1)
一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决
- 最极端的情况，有可能一直分裂到根节点

具体如下图所示

假如需要删除的元素在叶子节点中，那么直接删除即可。

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

如下图示：

下溢节点的元素数量必然等于 ┌ m/2 ┐ - 2
如果下溢节点临近的兄弟节点，有至少 ┌ m/2 ┐ 个元素，可以向其借一个元素
- 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
- 用兄弟节点的元素 a (最大的元素) 替代父节点的元素 b
- 这种操作其实就是：旋转
如果下溢节点临近的兄弟节点，只有 ┌ m/2 ┐ - 1 个元素
- 将父节点的元素 b 挪下来跟左右子节点进行合并
- 合并后的节点元素个数等于 ┌ m/2 ┐ + ┌ m/2 ┐ - 2，不超过 m - 1
- 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播，最坏的情况是一直到根节点下溢