B树

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

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

假设一个节点存储的关键字个数为 x

• 根节点：1 ≤ x ≤ m - 1
• 非根节点： ┌ m/2 ┐ − 1 ≤ x ≤ m − 1 (┌ ┐是向上取余)
• 如果有子节点，子节点个数 y = x + 1
• 所有叶子节点位于同一层

4阶B树

4阶B树的性质

• 所有节点能存储的元素个数 x: 1≤ x ≤ 3
• 所有非叶子节点的子节点个数 y: 2 ≤ y ≤ 4

添加

新添加的元素必定添加到叶子节点上，我们将 1 到 22 依次添加到4阶B树上

B树origin.png

关键字 1，2，3 可以依次加到根节点上

B树1.png

根节点的存储个数已满3个，当添加4的时候，已经容纳不下，节点的关键字个数将超过限制，我们将这种现象称为：上溢(overflow)
解决方法:将 中间 位置的 2 与父节点合并，如果没有父节点就新建一个。

B树2.png
添加 关键字 5 B树3.png
当添加数字6时，需将4上移，与2进行融合 B树4.png
当添加 到 8 时，将 6 上移即可 B树5.png
当 添加到 21时 B树6.png

将 20上移，然后让16上移，然后让8 上移

删除

• 假如需要删除的元素在叶子节点中，那么直接删除即可

  
  B树7.png
  

  删除关键字10

  
  B树 8.png
• 删除- 非叶子结点
  1，先找到前驱或后继元素，覆盖所需删除元素的值
  2，再把前驱或后继元素删除
  在图 B树7 中，删除 关键字 8， 找到其前驱 7，然后 将 8 覆盖。
  关键字6 的左边 就变成了 6 --> 7 --> 9, 10, 导致 7的左边没有子节点了，也就是 7的左边 的关键字个数为 0，低于了 最低限制 ┌ 4/2 ┐ − 1 ≤ x ≤ 4 − 1,这种现象称为 下溢(underflow)

下溢的解决

• 如果下溢节点临近的兄弟节点，至少 有 ┌ m/2 ┐个元素,可以向其借一个元素，进行 “左旋”，
  在图 B树7 中，删除 关键字 8， 找到其前驱 7，然后 将 8 覆盖。
  关键字6 的左边 就变成了 6 --> 7 --> 9, 10,将 7 移下来，将 9 移上去
  B树9.png

搜索

跟二叉搜索树的搜索类似

4阶B树.png

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