1、B树（B-tree、B-树）介绍

了解B树是最终理解红黑树的关键

B树

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

仔细观察B树，有什么眼前一亮的特点？

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

2、m阶B树的性质（m≥2）

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

  • 根节点：

  • 非根节点：

  注意：这个┌ ┐表示ceilling向上取整

  • 如果有子节点，子节点个数
    • 根节点：
    • 非根节点：
      • 比如，因此可以称为（2, 3）树、2-3树
      • 比如，因此可以称为（2, 4）树、2-3-4树
      • 比如，因此可以称为（3, 5）树
      • 比如，因此可以称为（3, 6）树
      • 比如，因此可以称为（4, 7）树

思考：如果 m = 2，那B树是什么样子？
如果m =2，那么根节点的子节点个数是2，非根节点的子节点个数是1或者2，那么不就是二叉搜索树嘛。

猜猜数据库实现中一般用几阶B树？
一般是200 ~ 300阶

3、B树 VS 二叉搜索树

• 和二叉搜索树，在逻辑上是等价的

• 多代节点合并，可以获得一个超级节点

  • 2代合并的超级节点(例如：18和12、33合并)，最多拥有 4 个子节点（至少是 4阶B树）
  • 3代合并的超级节点(例如：18和12、33和10、5、13、48合并)，最多拥有 8 个子节点（至少是 8阶B树）
  • n代合并的超级节点，最多拥有个子节点（ 至少是阶B树）

• m阶B树，最多需要代合并

多代节点合并：18和33合并成一个超级节点。
2代合并的超级节点：18和12、33合并，他们拥有最多子节点是12和33节点的左右子节点之和。

4、搜索

跟二叉搜索树的搜索类似

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

5、添加

• 新添加的元素必定是添加到叶子节点
  

• 插入55
  

  插入55

• 插入95
  

  插入95

• 再插入 98 呢？（假设这是一棵4阶B树）
  最右下角的叶子节点的元素个数将超过限制
  这种现象可以称之为：

5.1、添加 – 上溢的解决(假设5阶)

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

• 假设上溢节点最中间元素的位置为

  • 将位置的元素向上与父节点合并
  • 将 [] 和 [] 位置的元素分裂成 2 个子节点
    • 这 2 个子节点的元素个数，必然都不会低于最低限制（）

• 一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决
  最极端的情况，有可能一直分裂到跟节点

下图中依次添加98、52、54

• 插入98
  
  插入98
• 插入52
  
  插入52
• 插入54
  
  插入54

6、删除

6.1、删除 – 叶子节点

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

6.2、删除 – 非叶子节点

• 假如需要删除的元素在非叶子节点中

删除60

删除60后就剩下一个40元素了，那么一个元素怎么能拥有三个子节点呢？

1. 先找到前驱或后继元素，覆盖所需删除元素的值
2. 再把前驱或后继元素删除

• 的前驱或后继元素，必定在中
  • 所以这里的删除前驱或后继元素 ，就是最开始提到的情况：删除的元素在叶子节点中
  • 真正的删除元素都是发生在叶子节点中

6.3、删除 – 下溢

• 删除 22 ？（假设这是一棵 5阶B树）
  • 叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ ）
  • 这种现象称为：

6.4、删除 – 下溢的解决

• 下溢节点的元素数量必然等于
• 如果下溢节点临近的兄弟节点，有至少个元素，可以向其借一个元素
  • 将父节点的元素插入到下溢节点的位置（最小位置）
  • 用兄弟节点的元素（最大的元素）替代父节点的元素
  • 这种操作其实就是：
    

• 如果下溢节点临近的兄弟节点，只有 个元素
• 将父节点的元素挪下来跟左右子节点进行
• 合并后的节点元素个数等于，不超过
• 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播

上溢可能会让树变高，下溢可能会让树变矮。

7、4阶B树

• 如果先学习（），将能更好地学习理解

• 的性质

  • 所有节点能存储的元素个数 ： ≤ ≤
  • 所有非叶子节点的子节点个数 ： ≤ ≤

• 添加
  从 1 添加到 22，就会是一个
  

  4阶B树