B树

B树(B-Tree，Balanced Tree)是一种平衡的多路搜索树，多用于文件系统、数据库的实现

B树的特点：

• 一个节点可以存储超过2个节、可以拥有超过2个子节点；
• 拥有二叉搜索树的一些性质，例如从左到右大小分布；
• 平衡，每个节点所有子树的高度一致；
• 高度较低；

阶：B树分为m阶B树( m ≥ 2 )，m为节点度的最大值；

• 节点存储元素个数 x
  • 根节点：1 ≤ x ≤ m - 1
  • 非根节点：┌ m/2 ┐− 1 ≤ x ≤ m - 1 （注解：┌ m ┐ 代表m向上取整）
• 如果有子节点，子节点数 y = x + 1
  • 根节点：2 ≤ y ≤ m
  • 非根节点：┌ m/2 ┐≤ y ≤ m

例如：m = 5，
节点存储元素：根节点： 1 ≤ x ≤ 4，非根节点：3 - 1 ≤ x ≤ 4；
子节点数：根节点：2 ≤ y ≤ 5，非根节点：3 ≤ y ≤ 5；

B树和二叉搜索树，在逻辑上是等价的
多代节点合并，可以获得一个超级节点

• 2代合并的超级节点，最多拥有4个子节点（至少是4阶B树）
• 3代合并的超级节点，最多拥有8个子节点（至少是8阶B树）
• n代合并的超级节点，最多拥有2n个子节点（至少是2n阶B树）

搜索

• 先在节点内部从小到大开始搜索元素
• 如果命中，搜索结束
• 如果未命中，再去对应的子节点中搜索元素，重复步骤1

添加

新添加的元素必定时添加到叶子节点；
上溢(overflow)：添加时，存储节点数量可能会 > m-1，此时称为上溢；

• 上溢节点的元素个数必然等于m

解决上溢：（假设上溢节点最中间元素的位置为k）

1. 将k位置的元素向上与父节点合并；
2. 将[0,k-1]和[k + 1,m-1]位置的元素分裂成2个子节点；
3. 一次分裂完毕后，有可能导致父节点上溢，依然照上述步骤解决（最极端的情况可能一直分裂到根节点）；

删除

真正的删除都是发生在叶子节点；
删除的元素为非叶子节点，会先找到前驱或后继元素，覆盖所需删除元素的值，再把前驱或后继元素删除；
下溢(underflow)：删除时，存储节点数量可能会 ≥ ┌ m/2 ┐− 1，此时称为下溢；

• 下溢节点的元素个数必然等于┌ m/2 ┐− 2

解决下溢：

• 情况1：(条件：临近的兄弟节点，有至少┌m/2┐个元素) 操作：旋转
  1. 将父节点的元素b插入到下溢节点的0位置（最小位置）；
  2. 用兄弟节点的元素a（最大的元素）替代父节点的元素b ；

• 情况2：(条件：临近的兄弟节点，只有┌m/2┐− 1个元素) 操作：向下合并
  1. 将父节点的元素b挪下来跟左右子节点进行合并；
  2. 合并后的节点元素个数等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超过m − 1；
  3. 操作会导致父节点下溢，依然照上述步骤解决，下溢现象可能会一直往上传播；