Appearance
B 树
为什么需要B 树
当数据量非常大时，数据无法全部存放在内存中，必须存储在磁盘上。磁盘的读写速度远慢于内存，每次磁盘 I/O 都是性能瓶颈。如果使用二叉查找树（如 AVL 树、红黑树），树的高度为 O(log₂n)，查找一个关键字可能需要 log₂n 次磁盘访问——当 n 很大时，这是不可接受的。
B 树通过增加每个节点的分支数（多路查找），大幅降低树的高度，从而减少磁盘 I/O 次数。例如一棵 1001 阶 B 树，存储 10 亿个关键字只需要 3 层，最多 3 次磁盘访问即可完成查找。这就是数据库索引和文件系统广泛使用 B 树的原因。
核心思想
B 树是m 阶多路平衡查找树的典型代表。核心特点：
- 多路分支：每个节点最多有 m 棵子树、m-1 个关键字，一次磁盘 I/O 读入一个节点后可以进行多次比较
- 平衡：所有叶节点都在同一层，保证最坏情况下查找路径长度一致
- 节点半满约束：除根节点外，每个节点至少有 ⌈m/2⌉ 棵子树，保证空间利用率
B 树节点的结构示意：
┌──┬────┬──┬────┬──┬─ ... ─┬──────┬──┐
│P₀│ K₁ │P₁│ K₂ │P₂│ │Kₙ │Pₙ│
└──┴────┴──┴────┴──┴─ ... ─┴──────┴──┘其中 Kᵢ 为关键字（K₁ < K₂ < ... < Kₙ），Pᵢ 为指向子树的指针。子树 Pᵢ 中所有关键字的值在 Kᵢ 和 Kᵢ₊₁ 之间。
交互可视化
通过下方的交互动画，你可以逐步观察B 树的执行过程：
操作详解
B 树的性质
一棵 m 阶 B 树满足以下性质：
| 性质 | 描述 |
|---|---|
| 每个节点最多 m 棵子树 | 即最多 m-1 个关键字 |
| 根节点子树数 | 至少 2 棵（若非叶节点）；关键字至少 1 个 |
| 非根非叶节点子树数 | 至少 ⌈m/2⌉ 棵，即关键字至少 ⌈m/2⌉-1 个 |
| 所有叶节点在同一层 | 叶节点是查找失败到达的空指针，不含任何信息 |
| 节点内关键字有序 | K₁ < K₂ < ... < Kₙ，节点内可用顺序/折半查找 |
B 树节点的 C 语言定义：
c
#define M 5 // 5 阶 B 树
typedef struct BTNode {
int keyNum; // 当前关键字个数
int keys[M]; // 关键字数组（keys[0]不用，从1开始）
struct BTNode *children[M + 1]; // 子树指针数组
struct BTNode *parent; // 指向父节点的指针
} BTNode;⭐ 关键字个数范围（m 阶 B 树，非根节点）：
$$⌈m/2⌉ - 1 \leq n \leq m - 1$$
⭐ 最小/最大关键字总数：
- 含 n 个关键字的 B 树，最小高度：每个节点尽可能满，每层 m-1 个关键字。各层节点数为 1, m, m², ...，因此 $n \leq m^h - 1$，即 $h \geq \log_m(n+1)$
- 含 n 个关键字的 B 树，最大高度：每个节点尽可能少。根节点至少 1 个关键字、2 棵子树，其余节点至少 ⌈m/2⌉ 棵子树。第 h+1 层（叶节点层/失败层）至少有 $2⌈m/2⌉^{h-1}$ 个节点，而 n 个关键字对应 n+1 个失败节点，因此 $n + 1 \geq 2⌈m/2⌉^{h-1}$，即 $h \leq \log_{⌈m/2⌉}\frac{n+1}{2} + 1$
查找操作
B 树的查找是一个在节点间纵向移动（磁盘 I/O）与在节点内横向比较（内存操作）交替进行的过程。
关键步骤：
- 从根节点开始，将目标关键字 key 与当前节点中的关键字顺序比较（节点内关键字较少时用顺序查找，较多时可用折半查找）
- 若 key = Kᵢ，查找成功，返回该节点及位置
- 若 K ᵢ < key < Kᵢ₊₁，沿着指针 Pᵢ 进入对应子树，读取下一层节点（一次磁盘 I/O）
- 若到达叶节点（空指针），查找失败
c
// B 树查找（返回关键字所在节点和位置）
typedef struct {
BTNode *node; // 关键字所在节点
int index; // 在节点中的位置
int found; // 是否找到：1-成功，0-失败
} SearchResult;
SearchResult BTreeSearch(BTNode *root, int key) {
BTNode *p = root, *parent = NULL;
int i;
while (p != NULL) {
// 在当前节点中顺序查找
for (i = 1; i <= p->keyNum && key > p->keys[i]; i++);
if (i <= p->keyNum && key == p->keys[i])
return (SearchResult){p, i, 1}; // 查找成功
parent = p;
p = p->children[i - 1]; // 沿指针进入子树
}
return (SearchResult){parent, i, 0}; // 查找失败，返回插入位置
}⭐ 查找过程中磁盘 I/O 次数 = 查找路径上的节点数 = 树的高度 h。节点内的比较在内存中完成，不涉及磁盘访问。
插入操作
B 树的插入总是发生在最底层的非叶节点（即终端节点）。
关键步骤：
- 先执行查找，确定关键字应插入的终端节点位置
- 若该节点插入后关键字数 ≤ m-1，直接插入，完成
- 若插入后关键字数 = m（溢出），需要进行节点分裂
⭐ 节点分裂过程：
- 取该节点的中间关键字 K₍⌈m/2⌉₎
- 将中间关键字上提到父节点中
- 原节点分裂为两个节点：中间关键字左边的关键字组成左节点，右边的关键字组成右节点
- 若父节点也溢出，继续向上分裂，最坏情况一直分裂到根节点，树高度增加 1
以 5 阶 B 树为例，每个节点最多 4 个关键字，插入导致 5 个关键字时触发分裂：
分裂前（溢出）: [K₁ K₂ K₃ K₄ K₅]
↑ 中间关键字 K₃ 上提
分裂后: 父节点 ← [..., K₃, ...]
/ \
[K₁ K₂] [K₄ K₅]⭐ B 树长高的唯一方式就是根节点分裂——这保证了所有叶节点始终在同一层。
删除操作
B 树的删除需要保证删除后每个节点的关键字数不低于 ⌈m/2⌉-1。分两种情况讨论：
情况一：删除的关键字在终端节点
直接删除，然后检查是否下溢（关键字数 < ⌈m/2⌉-1）。
情况二：删除的关键字在非终端节点
用该关键字的直接前驱（左子树中最右的关键字）或直接后继（右子树中最左的关键字）替换它，转化为删除终端节点中的关键字。
⭐ 删除后下溢的处理（终端节点关键字数 < ⌈m/2⌉-1）：
| 处理策略 | 条件 | 操作 |
|---|---|---|
| 借兄弟（左借） | 左兄弟关键字数 > ⌈m/2⌉-1 | 父节点关键字下移到当前节点，左兄弟最大关键字上移到父节点 |
| 借兄弟（右借） | 右兄弟关键字数 > ⌈m/2⌉-1 | 父节点关键字下移到当前节点，右兄弟最小关键字上移到父节点 |
| 合并 | 左右兄弟关键字数都 = ⌈m/2⌉-1 | 当前节点与一个兄弟合并，父节点中间隔关键字下移参与合并 |
合并操作可能导致父节点也下溢，需要逐层向上处理，最坏情况合并到根节点，根节点关键字被掏空后树高度减 1。
借右兄弟示例（5 阶 B 树，节点最少 2 个关键字）:
[..., 35, ...] 父节点
/ \
[20] [40, 50, 60] 当前节点下溢，右兄弟富余
↓
[..., 40, ...] 35 下移，40 上提
/ \
[20, 35] [50, 60] 恢复平衡合并示例（5 阶 B 树）:
[..., 35, ...] 父节点
/ \
[20] [40, 50] 当前节点下溢，右兄弟刚好 ⌈m/2⌉-1
↓
[...] 35 下移参与合并
|
[20, 35, 40, 50] 合并为一个节点复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log_m n) 次磁盘 I/O，节点内 O(m) | 树高 h = O(log_{⌈m/2⌉} n)，每层一次磁盘访问 |
| 插入 | O(log_m n) | 查找 + 最坏情况逐层分裂到根 |
| 删除 | O(log_m n) | 查找 + 最坏情况逐层合并到根 |
磁盘 I/O 次数：查找过程中为 h 次；插入最坏需要 h 次查找 + h 次分裂写回；删除最坏需要 h 次查找 + h 次合并写回。实际应用中 m 取较大值（如几百到上千），使得 h 通常只有 3~4 层。
考研高频考点
- ⭐ m 阶 B 树中非根节点关键字数范围 ⌈m/2⌉-1 ~ m-1（选择题/填空题高频）
- ⭐ 含 n 个关键字的 m 阶 B 树的最大高度公式推导（大题常考）
- ⭐ 插入时节点分裂的过程、中间关键字上提（手动建树题）
- ⭐ 删除时借兄弟与合并操作的判断和执行（手动操作题）
- ⭐ B 树 vs B+ 树的区别（简答题/选择题必考）
- B 树所有叶节点在同一层的原因（概念题）
- 磁盘 I/O 与 B 树阶数选择的关系（理解题）
- 给定关键字序列，画出 B 树的构造过程（综合应用题）