数据结构与算法-基础(2)

11、数据结构与算法 - 基础：B 树

摘要

B树是一种平衡的多路搜索树，在添加、删除和搜索等一些操作上和二叉搜索树是同样的逻辑，除此之外 4 阶 B 树在结构上和红黑树也是相似的。所以了解 B 树，可以更好的切入学习红黑树。

红黑树是自平衡树之一，在数据结构中有比较重要的地位。同时也是入手学习比较复杂的一种结构。所以在学习红黑树之前，先学习 B 树，当作铺垫。那么为什么 B 树可以作为学习红黑树的铺垫呢？

先说结论，红黑树和 4 阶 B 树在结构上是大致一样的，所以学习完 B 树可以更好的理解红黑树。下面开始学习 B 树。

B 树

B树是一种平衡的多路搜索树，比较多的应用到文件系统、数据库场景。B 树中的一个节点可以存放超过 2 个元素，并且可以有超过 2 个子节点。这么看来似乎超出二叉树的范畴，为什么要搞出这样的树结构？

因为B 树也是符合二叉搜索树的一些性质，而且每个节点的所有子树高度是一致的，也就是平衡的，可以存储多个元素，有多个子节点情况，会让 B 树高度变小一些。

B树结构中的元素符合二叉搜索树结构排序，即当前节点的元素大于左子树所有节点的元素，小于右子树所有节点的元素。

m 阶 B 树性质（m ≥ \geq ≥ 2）

m 通俗讲就是每个节点最大可以有多少个子节点。这里要特别说明，B 树中的每个节点可以有多个元素，不是一个节点只有一个元素。

如果一个节点可以存储的元素个数为 x，那么（以 4 阶 B 树为例）：

m 阶 B 树性质（m ≥ \geq ≥ 2）	4 阶 B 树
根节点的元素个数为：1 ≤ \leq ≤ x ≤ \leq ≤ m - 1	根节点元素个数是 1～ 3 个
非根节点的元素个数为：m / 2(向下取整) -1 ≤ \leq ≤ x ≤ \leq ≤ m - 1	非根节点的元素个数是 1～3 个
若有子节点，子节点的个数 y = x + 1	子节点的个数就是元素个数 x - 1 个
根节点若有子节点，子节点的个数就是 2 ≤ \leq ≤ y ≤ \leq ≤ m	根节点的子节点个数就是 2～4 个

B 树与二叉搜索树

B树和二叉搜索树在逻辑上是等价的。二叉搜索树从最底层叶子节点向上合并成为超级节点（超过 2 个元素的节点）。如下图所示：

B 树的操作

搜索同二叉搜索树一样，从根节点开始比较，相等就命中结束，不相等就根据比较节点元素的大小到对应的子树中比较。

添加元素是添加到叶子节点，添加完成之后就要判断节点上的元素数量是否超过个数限制（m / 2(向下取整) ≤ \leq ≤ x ≤ \leq ≤ m - 1），若超出则称为上溢。

解决上溢的大致步骤就是：

1、将该节点的中间元素向上合并，元素个数为单数，就取中间元素，若为双数，就取中间的两个元素中的随意一个；
2、将该节点的剩余元素拆分为两个子节点；
3、当节点合并到父节点时，就要判断合并后的父节点是否存在上溢，若存在，就返回步骤1往下继续操作若不存在，结束；

删除元素要考虑的情况比较多，最简单的情况就是删除的元素在叶子节点，这种情况就直接删除该元素就好。

若删除的元素不是在叶子节点，则需要找到该元素节点的前驱或者后继，作替换之后再处理（同二叉搜索树操作一样）。当出现删除元素之后，节点中元素个数不满足 m / 2(向下取整) -1 ≤ \leq ≤ x ≤ \leq ≤ m - 1 的时候，称为下溢情况。

当出现下溢情况时，大致的处理步骤是：

1、看节点的兄弟节点是否移除一个之后，兄弟节点的元素个数是否满足m/2(向下取整)-1≤\leq≤x≤\leq≤m-1，若满足就借过来，合并到父节点，父节点中拿出一个元素给到当前节点（要依然满足二叉搜索树的性质）；
2、若不满足m/2(向下取整)-1≤\leq≤x≤\leq≤m-1，就需要把父节点中的元素拿出来和左右子节点合并然后需要再判断父节点是否有下溢情况，若存在，返回步骤1，若不存在，结束；

4 阶 B 树

4阶B 树在结构上和红黑树是很相似的。4 阶 B 树 所有节点能存储的元素个数 x，1 ≤ \leq ≤ x ≤ \leq ≤ 3。所有非叶子节点的子节点个数 y，2 ≤ \leq ≤ x ≤ \leq ≤ 4。