恋上数据结构笔记：B-Tree
B-Tree
B 树是一种平衡的多路搜索树，用于文件系统、数据库的实现。
仔细观察 B 树有什么眼前一亮的特点？
- 一个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
- 拥有二叉搜索树的一些性质，我们拿 3 阶 B 树举例，root 节点左侧都是比 18 小的，右侧都是比 48 大的，而中间的节点是在他们两者之间的。
- 平衡，每个节点所有的子树高度都是一致的。
- 比较矮
m 阶 B-tree 的性质（m ≥ 2）
- 假设一个节点存储的元素个数为
- 根节点： 1 ≤ x ≤ m - 1 ：
- 非根节点：⌈m /2⌉ - 1 ≤ x ≤ m -1
- 如果有子节点，子节点的个数 y = x + 1
如果我们是 3 阶段 Btree：
- 根节点：1 ≤ x ≤ 2
- 非根节点 2≤ y ≤3
因此可以成为（2，3）树、2-3 树。
B 树 VS 二叉搜索树
- B-Tree 和 二叉搜索树，在逻辑上是等价的
我们只要让二叉搜索树中的 18 和 33合并成为一个节点，之后再让 23 和 30 合并以此类推，就变成了 B-Tree。所以我们只需要将二叉搜索树的某些父子节点合并后就可以将变成一颗 B-Tree。
多代节点合并可以获得一个超级节点。
- 2 代合并的超级节点，最多拥有 4 个子节点（至少是 4 阶 B—Tree）
- 3 代合并的超级节点，最多拥有 8 个子节点（至少是 8 阶 B—Tree）
- n 代合并的超级节点，最多拥有 2^n 个子节点（至少是 2^n 阶 B—Tree）
- m 阶 B-Tree，最多需要 log2m 代合并
搜索
B-Tree 的搜索和二叉树的搜索类似。
- 先从节点内部从小到大开始搜索元素
- 如果命中，搜索结束
- 如果未命中，再去对应的子节点中搜索元素，重复步骤 1
添加
新添加的元素必定是添加到叶子节点。
我们现在有一个4 阶B 树。
现在我们要向这棵树中插入 55
- 首先是与 40 进行比较，发现 55 比 44 大，那么向右子树添加
- 右子树中找到了 60~88，55 比 66 小，那么就像左子树添加
- 最终我们找到了 50 节点，这个时候新添加的元素必须放在叶子节点上，那么就会将 55 添加 50 上。
现在我们继续向B-Tree 中插入数据 95，按照上面的逻辑执行后。
如果这个时候右下角的子树已经达到了 3 个节点，如果我们再向其中插入 98 呢？如果在加入的话节点就出了 4 阶 B-Tree 的子节点数量。
这个时候就需要进行：上溢（overflow）。
上溢（overflow）
现在假设是 5 阶 B-Tree，一个节点最多存储四个元素。如果存储了五个元素那么就开始上溢。
- 上溢节点的元素个数必然等于 m
假设上溢节点最中间的元素的位置为 k
- 将 K 位置的元素向上与父节点合并
将[0, k- 1]和 [k+1, m -1] 位置的元素分裂成两个子节点
- 这两个子节点的元素个数，必然都不会低于最低限制 ⌈m /2⌉ - 1
这个时候，子节点的上溢会导致父节点的上溢，因为父节点此时也已经超过了最大值，所以一次分裂完毕后，依然按照上述方法进行解决，最极端的情况，可能会一直分裂到根节点。
我们回到上节的那个例子。
现在插入 98 后。
插入 52：
插入 54
删除
删除 - 叶子结点
如果我们需要删除的元素在叶子结点中，那么直接删除即可。
删除- 非叶子节点
- 先找到前驱或者后继元素，覆盖所需元素的值
- 先把前驱后继元素删除
寻找 60 的前驱和后继：
- 非叶子节点的前驱或后继元素，必须在叶子节点中。
- 所以这里的删除前驱或后继元素，就是最开始提到的情况：删除的元素在叶子节点中。
- 真正的删除元素都是发生在叶子节点上。
叶子节点被删除一个元素后，元素个数可能低于最低限制。这种现象称为下溢（underflow）。
下溢
- 下溢节点的元素数量必然等于 ⌈m /2⌉ - 2
如果下溢节点临近的兄弟节点，有至少 ⌈m /2⌉ 个元素，可以像其接一个元素
- 将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
- 用兄弟节点的元素 a（最大元素）替代父节点的 yuansub
- 这种操作其实就是：旋转
图是一颗 5 阶 B-Tre,现在要删除 22，：
如果下溢节点临近的兄弟节点，只有 ⌈m /2⌉ -1 哥元素
- 将父节点的元素 b 挪下来和左右子节点进行合并
- 合并后的节点元素个数等于 ⌈m /2⌉ + ⌈m /2⌉ - 2，不会好过 m -1。
- 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播。
上溢和下溢带来的现象
- 上溢会让 B-Tree 变高
- 下溢会让 B-Tree 变矮