## 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)