数据结构与算法笔记目录： 《恋上数据结构》 笔记目录想加深 Java 基础推荐看这个： Java 强化笔记目录
我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note
B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现；
仔细观察B树，有什么眼前一亮的特点？
- 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
- 拥有二叉搜索树的一些性质
- 平衡，每个节点的所有子树高度一致
- 比较矮
m阶B树的性质
数据库实现中一般用几阶B树？
- 200 ~ 300
B树 vs 二叉搜索树
B树 和 二叉搜索树，在逻辑上是等价的；
多代节点合并，可以获得一个超级节点
- 2 代合并的超级节点，最多拥有 4 个子节点（至少是 4 阶B树）
- 3 代合并的超级节点，最多拥有 8 个子节点（至少是 8 阶B树）
- n 代合并的超级节点，最多拥有 2^n^ 个子节点（ 至少是 2^n^ 阶B树）
m 阶 B树，最多需要 log2^m^ 代合并；
搜索
跟二叉搜索树的搜索类似：
- 先在节点内部从小到大开始搜索元素
- 如果命中，搜索结束
- 如果未命中，再去对应的子节点中搜索元素，重复步骤 1
添加 – 上溢
新添加的元素必定是添加到叶子节点：
插入 55：
插入 95：
再插入 98 呢？（假设这是一棵 4阶B树）
- 最右下角的叶子节点的元素个数将超过限制
- 这种现象可以称之为：上溢（overflow）
添加 – 上溢的解决(假设5阶)
上溢节点的元素个数必然等于 m；
假设上溢节点最中间元素的位置为 k
- 将 k 位置的元素向上与父节点合并
- 将 [0, k - 1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点
这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ − 1）一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决
- 最极端的情况，有可能一直分裂到根节点
添加示例：
插入 98：
插入 52：
插入 54：
删除
删除 – 叶子节点
假如需要删除的元素在叶子节点中，那么直接删除即可；
例：删除 30
删除 – 非叶子节点
假如需要删除的元素在非叶子节点中
- 先找到前驱或后继元素，覆盖所需删除元素的值
- 再把前驱或后继元素删除
例：删除 60
非叶子节点的前驱或后继元素，必定在叶子节点中；
- 所以这里的删除前驱或后继元素 ，就是最开始提到的情况：删除的元素在叶子节点中
- 真正的删除元素都是发生在叶子节点中；
删除 – 下溢
删除 22？（假设这是一棵 5阶B树）
- 叶子节点被删掉一个元素后，元素个数可能会低于最低限制（
≥┌ m/2 ┐ − 1 ） - 这种现象称为：下溢（underflow）
删除 – 下溢的解决
下溢节点的元素数量必然等于 ┌ m/2 ┐ − 2
如果下溢节点临近的兄弟节点，有至少 ┌ m/2 ┐ 个元素，可以向其借一个元素
- 将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
- 用兄弟节点的元素 a（最大的元素）替代父节点的元素 b
- 这种操作其实就是：旋转
如果下溢节点临近的兄弟节点，只有 ┌ m/2 ┐ − 1 个元素
- 将父节点的元素 b 挪下来跟左右子节点进行合并
- 合并后的节点元素个数等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超过 m − 1
- 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播
删除示例：
4阶B树
如果先学习 4 阶 B 树（2 - 3 - 4 树），将能更好地学习理解红黑树：
4阶B树的性质：
- 所有节点能存储的元素个数 x ：1 ≤ x ≤ 3
- 所有非叶子节点的子节点个数 y ：2 ≤ y ≤ 4
添加：从 1 添加到 22
