B树

什么是B树

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

4阶B树.png

B树具有以下特点：

1. 一个节点可以存储超过2个元素，一个节点可以拥有超过两个子节点；
2. 拥有二叉搜索树的一些性质；
3. 平衡，每个节点的所有子树高度一致
4. B树比较矮

m阶B树的性质（m>=2）

假设一个节点存储的元素个数为x，

1. 根节点： 1 <= x <= m-1
2. 非根节点：⌈ m/2 ⌉ -1 <=x <= m-1
3. 如果有子节点，子节点个数 y = x+1
   a. 根节点：1 <= y <= m
   b. 非根节点：⌈ m/2 ⌉ <= y <= m
   比如，m=3，1 <= y< = 3，因此可以称为（2, 3）树、2-3树；
   再如，m=4 ,2 <= y <= 4，因此可以称为（2, 4）树、2-3-4树；
   再如，m=5 ,3 <= y <= 5，因此可以称为（3, 5）树；
   再如，m=6 ,3 <= y <= 6，因此可以称为（3, 6）树；
   再如，m=7 ,4 <= y <= 7，因此可以称为（4, 7）树。

B树与二叉搜索树

1. 对于m阶B树，m=2就是二叉搜索树。B树与二叉搜索树在逻辑上是等价的；
2. 多代节点合并，可以获得一个超级节点，比如：
   两代合并的超级节点，最多拥有4个子节点（至少是4阶B树），
   三代合并的超级节点，最多拥有8个子节点（至少是8阶B树），
   n代合并的超级节点，最多拥有2^{n个子节点（至少是2}n阶B树）
3. m阶B树，最多需要logm代合并

B树的搜索

与二叉树搜索类似，

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

B树的元素添加

4阶B树添加元素.png

1. 新添加的元素必定是添加到叶子节点【这个是B树的性质】
2. 添加元素，元素个数可能会高于最大限制（要求的最大限制是 m-1），造成“上溢（overflow）”
3. 上溢的解决：
   上溢节点的元素个数必然等于m，假设上溢节点最中间元素的位置为k，
   a. 将k位置的元素向上与父节点合并；
   b. 将[0, k-1] 和 [k+1, m-1] 位置的元素分裂成2个子节点。这2个子节点的元素个数，必然都不会低于最低限制 ⌈m/2⌉-1
   c. 一次分裂完成后，有可能导致父节点上溢，依然按照上述方法解决
   上溢的解决又可能让B树变高。

B树的元素删除

4阶B树删除元素.png

1. 如果需要删除的元素在叶子节点中，那么直接删除即可；

2. 如果需要删除的元素在非叶子节点中：
   a. 先找到前驱或后继元素，覆盖所要删除的元素的值
   b. 再把前驱或后继元素删除
   注意：非叶子节点的前驱或后继元素，必定在叶子节点中。所以这里的删除前驱或后继元素，就是步骤1中的情况，删除的元素在叶子节点中。也就是说，真正的删除元素都是发生在叶子节点中。

3. 叶子节点被删除掉一个元素后，元素个数可能会低于最低限制（要求的最低限制是 ⌈m/2⌉-1），就会出现“下溢（underflow）”。

4. “下溢”的解决：
   下溢节点的元素数量必然等于：⌈m/2⌉-2
   a. 如果下溢节点临近的兄弟节点，有至少⌈m/2⌉ 个元素，可以向其借一个元素：1. 将父节点的元素b插入到下溢节点的0位置出（最小值所在位置）；2. 用兄弟节点的元素a（最大的元素）替代父节点的元素b；这种操作其实就是旋转。

   看兄弟节点满足否.png
   从兄弟节点借.png
   b. 如果下溢节点临近的兄弟节点，只有 ⌈m/2⌉-1个元素：1. 将父节点的元素b挪下来跟左右子节点进行合并；2. 合并后的节点元素个数等于⌈m/2⌉+⌈m/2⌉ -2，不超过m-1
   兄弟节点不满足.png

挪动父节点.png

c. 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播，可以让B树变矮。