## B 树基本概念
B 树是一种平衡的多路搜索树,多用于文件系统、数据库系统的实现,B 树具有以下特点
* 与二叉树不同,一个节点可以存储超过 2 个元素,也可以拥有超过 2 个子树
* 平衡,每个节点的所有子树高度一致,整体高度较矮
* 也具有二叉搜索树的性质,例如对于任意元素,大于所有左子树上的元素而小于所有右子树(以及同节点内右侧的元素)上的元素

对于一棵 5 阶 B 树,每个节点最多可以有 5 个子树
### m 阶 B 树的性质($ m \geq 2 $)
* 设一个节点存储的元素个数为 $ x $
* 根节点:$ 1 \leq x \leq m-1 $
* 非根节点:$ (m / 2)(向上取整) - 1 \leq x \leq m - 1 $
* 若一个节点存在子节点,则子节点个数 $ y = x + 1 $
* 根节点:$ 2 \leq y \leq m $
* 非根节点:$ (m / 2)(向上取整) \leq y \leq m $
因此,对于常见的 B 树,有
* 3 阶 B 树:$ m = 3 $,任意节点 $ 1 \leq x \leq 3 $,$ 2 \leq y \leq 3 $,因此也称为 2-3 树
* 4 阶 B 树:$ m = 4 $,任意节点 $ 2 \leq x \leq 4 $,$ 2 \leq y \leq 4 $,因此也称为 2-3-4 树
* 5 阶 B 树:$ m = 5 $,任意**非根节点** $ 2 \leq x \leq 4 $,$ 3 \leq y \leq 5 $,因此也称为 2-3-4 树
### B 树 与 二叉搜索树
将二叉搜索树的节点合并,可以成为 B 树,即多代节点合并称为超级节点,如对于下面的 BST

将 18 和 33 合并,23 和 30 合并,20 和 21 合并,45 和 47 合并,50 和52 合并,即可得到如下的 3 阶 B 树

可以看到,2 代合并的超级节点,最多拥有 4 个子节点(至少是 4 阶B树),而 $ n $ 代合并的超级节点,最多拥有 $ 2^n $ 个子节点(至少是 $ 2^n $ 阶 B 树)
## B 树的操作
### 搜索
1. 先在节点内部从小到大搜索元素,或者使用二分搜索
2. 如果命中,搜索结束
3. 如果未命中,再去对应的子节点中搜索元素,重复步骤 1

假设搜索 72,首先在根节点做比较,72 大于 40,所以接着在根节点的右子树搜索,72 大于 60 小于 80,继续在 60 和 80 之间的子树寻找,因为 72 大于 70,所以需要继续往 70 的右子树寻找,但是右子树为空,所以得出结论 72 不在该 B 树上
### 添加
首先明确,新添加的元素必定是添加到**叶子节点**,对于下面的 4 阶 B 树(每个节点最多容纳 3 个元素,最多 4 个子树)

1. 插入 55,首先在根节点做比较,55 大于 40,所以接着在根节点的右子树搜索,55 小于 60,继续在 60 的左子树寻找,55 大于 50,此时已经在叶子节点,且节点容量足够,所以将 55 插入在 50 的右侧
2. 插入 95,首先在根节点做比较,95 大于 40,所以接着在根节点的右子树搜索,95 大于 80,继续在 80 的右子树寻找,95 大于 90 小于 100,此时已经在叶子节点,且节点容量足够,所以将 95 插入在节点 90 和 100 的中间
此时形成的二叉树如下

如果此时再插入元素 98,那么右下角的叶子节点容量将超过 4 阶 B 树的限制,会导致上溢(overflow)
### 上溢
对于一棵如下的 5 阶 B 树(局部),如果插入元素 34

* 上溢节点的元素个数必然等于 m(5)
* 假设上溢节点最中间元素的位置为 k(2)
* 将 k 位置的元素向上与父节点合并
* 将 `[0,k-1]` 和 `[k+1,m-1]` 位置的元素分裂成 2 个子节点,这 2 个子节点的元素个数,必然都不会低于最低限制 $ (m / 2)(向上取整) - 1 $

* 当然,一次上溢的解决,因为子节点元素合并到父节点,可能导致父节点上溢,则继续按照上面的方法解决,最坏的情况,有可能一直上溢到根节点,导致根节点分裂上溢

* 添加元素导致的上溢,是**唯一**的可能导致 B 树**长高**的操作
### 删除
与 BST 类似,假如需要删除的元素在叶子节点中,那么直接删除即可,例如对于下面的 4 阶 B 树

删除 30,因为是叶子节点,且删除后不会低于 4 阶 B 树的限制,直接删除

假如需要删除的元素在非叶子节点中,参照 BST ,可以先找到前驱或后继元素,覆盖所需删除元素的值,再把前驱或后继元素删除

删除 60,60 的前驱为 55,将 55 覆盖 60,然后将 55 从 54 和 55 节点中删除

因为非叶子节点的**前驱**或**后继**元素,必定在**叶子节点**中,所以这里**实际上**删除的前驱或后继元素,就是最开始提到的情况,删除的元素在叶子节点中,也就是说真正的删除元素都发生在叶子节点中。
### 下溢
如下有一棵 5 阶 B 树(非根节点元素个数大于等于2),如果删除 22,该叶子节点的元素个数可能会低于最低限制,此时便发生下溢(underflow)

下溢节点的元素数量必然等于 $ m/2(向上取整) - 2 $
1. 如果下溢节点临近的兄弟节点,有至少 $m/2(向上取整)$ 个元素,可以向其“借”一个元素

* 绿色节点在删除一个元素后,节点元素个数低于最低限制($ \geq m/2(向上取整) - 1 $)
* 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
* 用兄弟节点的元素 a(最大的元素)替代父节点的元素 b
* 注意子节点d也需要调整
* 这种操作其实就是**旋转**
2. 如果下溢节点临近的兄弟节点,最多只有 $ m/2(向下取整) - 1 $ 个元素,即“不够借”

* 将父节点的元素 b 挪下来跟左右子节点进行合并
* 合并后的节点元素个数等于 $ m/2(向上取整) + m/2(向上取整) - 2 $,不超过 $ m-1 $
* 当然,这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播到根节点
删除元素导致的下溢,是**唯一**的可能导致 B 树**变矮**的操作
## 参考
* [恋上数据结构与算法(第一季)](https://ke.qq.com/course/385223)
* [小码哥《恋上数据结构与算法》笔记(十):B树](https://juejin.im/post/6844903971681730573)

数据结构 | B 树