B 和 B＋树

一、B-树（B-tree）的基本概念

1. 什么是 B-树

B-树是一种 多路平衡查找树。
在 B-树中，一个结点可以包含多个关键字，从而显著降低树的高度，减少磁盘 I/O 次数。

B-树中，所有结点的 最大孩子数 称为 B-树的 阶，用 m 表示，一般要求：

m ≥ 3

---

2. m 阶 B-树的性质（核心）

设结点中关键字个数为 n。

（1）关键字个数范围

• 根结点

  • 至少 1 个关键字（非叶）
  • 至多 m − 1 个关键字

• 非根结点

  • 至少 ⌈m/2⌉ − 1 个关键字
  • 至多 m − 1 个关键字

---

（2）分支数与关键字的关系

• 含 n 个关键字的结点
• 含 n + 1 个子树指针

---

（3）结点结构

P0 | k1 | P1 | k2 | P2 | ... | kn | Pn

满足有序性：

P0 < k1 < P1 < k2 < ... < kn < Pn

---

（4）平衡性

• 所有叶子结点 位于同一层
• B-树是一棵严格的平衡树

---

二、B-树的查找过程

示例：在 B-树中查找关键字 42

                [30]/           \[15 26]       [39 45 59]\[40 42 44]

查找路径：

30 → 39 → 42（查找成功）

---

三、B-树的插入操作

1. 插入的基本原则

• 新关键字 一定插入到终端结点（叶子结点）
• 插入后若关键字数超出上限，需要 拆分结点

---

2. 关键字个数限制

对于 m 阶 B-树：

⌈m/2⌉ − 1 ≤ 关键字数 ≤ m − 1

---

3. 结点拆分规则（重点）

当某结点关键字数达到 m：

1. 取第 ⌈m/2⌉ 个关键字
2. 该关键字 上升到父结点
3. 左右关键字分别形成两个新结点
4. 若父结点溢出，继续拆分（连锁反应）

拆分示意（5 阶 B-树）

原结点：
[k1 k2 k3 k4 k5]拆分后：k3/  \[k1 k2] [k4 k5]

---

四、B-树的删除操作（难点）

1. 删除的总体思想

• 尽量将删除操作 转化为终端结点删除
• 删除后结点关键字数不能低于下限
• 若不满足，需要 借关键字或合并结点
• 删除可能引发 连锁反应

---

2. 删除终端结点关键字的三种情况

设最少关键字数为 ⌈m/2⌉ − 1

---

情况 ①：关键字数 > 最小值

✔ 直接删除

---

情况 ②：关键字数 = 最小值，兄弟结点可借

✔ 通过父结点调整，从兄弟结点借关键字

    [ b ]/     \
[a c]   [ d ]

调整后：

    [ c ]/     \
[a b]   [ d ]

---

情况 ③：关键字数 = 最小值，兄弟结点也不可借

✘ 必须进行 结点合并

    [ b ]/     \[ a ]  [ c ]合并后：
[ a b c ]

父结点关键字减少，可能继续向上合并。

---

3. 删除非终端结点关键字

步骤：

1. 找该关键字的 相邻关键字

   • 左子树中的最大关键字
   • 或右子树中的最小关键字

2. 用相邻关键字替换原关键字

3. 转化为终端结点删除问题

---

五、B+树的基本概念

（一）B+ 树是什么

B+树是 B-树的一种重要变形，广泛应用于数据库索引与文件系统。

（二）\(m\)阶B+树的核心特性

1. 每个分支结点至多有\(m\)棵子树；根结点若为分支结点，至少2棵子树，其他分支结点至少\(\lceil m/2 \rceil\)棵子树。
2. 叶结点包含全部关键字及对应记录指针，关键字按序排列；叶结点通过指针连成有序链表，便于范围查找。
3. 分支结点仅存关键字和子树指针，关键字是对应子树叶结点的最大/最小关键字，仅作索引。
4. 所有叶结点在同一层，分支结点的关键字数与子树数相等（B树为关键字数+1=子树数）。

（三）B+树与B树的核心差异

1. 关键字存储：B+树叶结点存全部关键字，分支结点为索引；B树所有结点都存关键字。
2. 子树与关键字关系：B+树分支结点关键字数=子树数；B树结点关键字数+1=子树数。
3. 查找特性：B+树查找必到叶结点，支持顺序查找（链表）和多路查找；B树找到关键字即可终止。
4. 磁盘性能：B+树叶结点链表适配范围查询，分支结点索引更紧凑，磁盘I/O次数更少。

（四）B+树的操作

查找、插入、删除逻辑与B树类似，但插入/删除需保证叶结点链表的连续性，且分支结点的索引关键字需同步调整。

---

六、B+树结构示意

4 阶 B+树示意

              [50 | 96]/      |      \[15|50]  [62|78]  [96]|         |       |
-----------------------------------------
3 8 15 20 26 43 50 56 62 71 78 84 89 96
-----------------------------------------

叶子结点链表

[3 8] → [15 20] → [26 43] → [50 56] → ...

---

八、为什么数据库更常用 B+树

1. 非叶结点不存记录，索引更紧凑
2. 所有查询路径长度一致
3. 支持高效 范围查询与顺序扫描
4. 叶子链表天然适合磁盘顺序读写

---