1. B树（B-tree）
(1) 定义
B树（B-tree）：一种平衡的 多路搜索树，多用于文件系统、数据库的实现。其特点：
- 1个节点可以存储超过2个元素，可以拥有超过2个子节点
- 拥有 二叉搜索树 的一些性质
- 平衡，每个节点的所有子树高度平衡
- 比较矮
3阶B树
4阶B树
5阶B树
(2) 性质
m阶B树的性质（m
2）
假设一个节点存储的元素个数为x
- 根节点：1
x
- 非根节点：
- 1
如果有子节点，子节点个数：y = x + 1
- 根节点：2
- 非根节点：
比如m = 3，2
比如m = 4，2
比如m = 5，3
(3) B树 对比 二叉搜索树
B树 和 二叉搜索树，在逻辑上是等价的
多代节点合并，可得一个超级节点
- 2代节点合并的超级节点，最多拥有4个子节点（至少是4阶B树）
- 3代节点合并的超级节点，最多拥有8个子节点（至少是8阶B树）
- n代节点合并的超级节点，最多拥有
个子节点（至少是
- m阶B树，最多需要
代合并
二叉搜索树
3阶B树
(4) 上溢
- 新添加的元素必定是添加到 叶子节点
- 上溢（overflow）：添加时，叶子节点的元素个数超过限制
- 解决方法：中间元素向上 与父节点合并（可能循环操作）
上溢解决方法
(5) 下溢
- 真正的删除元素都是发生在 叶子节点中
情况一：删除叶子节点
情况二：删除非叶子节点，用前驱或后继节点替代- 下溢（underflow）：删除时，叶子节点的元素个数低于最低限制（
- 解决方法：
情况一：兄弟节点借一个元素，旋转即可
情况二：兄弟节点无法借元素，父节点向下，与左右子节点合并（可能循环操作）
下溢解决方法一
下溢解决方法二
下溢解决实例
(6) 4阶B树
4阶B树 (2, 3)树 和 红黑树 完美匹配
- 所有节点能存储的元素个数：1
- 所有非叶子节点的子节点个数：2
4阶B树
