平衡二叉树能把高度控制在 $O(\log n)$，但每个结点只有两个分支。如果结点存放在磁盘页中，一次 I/O 只带回一个关键字会浪费整页带宽。B 树让一个结点容纳多个关键字和子树，用更大的分支因子换取更低的树高。

学习目标

• 按统一口径写出 m 阶 B 树的结点和关键字上下界；
• 在一个结点内定位关键字并选择正确子树；
• 推演 B 树插入时的分裂与向上扩散；
• 推演删除时的直接删除、借键和合并；
• 根据树高计算最少、最多关键字数；
• 比较 B 树与 B+ 树的存储位置、查找终点和范围查询能力。

m 阶 B 树的定义

B 树（B-tree）是多路平衡查找树。"m 阶"表示一个结点最多有 $m$ 棵子树。本章采用以下定义：

1. 每个结点最多有 $m$ 棵子树，因而最多有 $m-1$ 个关键字；
2. 非叶根结点至少有 2 棵子树，至少有 1 个关键字；
3. 除根结点外，所有非叶结点至少有 $\lceil m/2\rceil$ 棵子树；
4. 含 $k$ 棵子树的结点含 $k-1$ 个关键字；
5. 结点内关键字严格递增，各子树关键字落在相邻关键字划分的区间中；
6. 所有叶结点位于同一层。

为统一计算，可以把最底层实际存放关键字、没有孩子的结点称为叶结点。不同教材有时会额外画出失败查找的空指针叶；做题前要确认高度是否把空叶计算在内。

设：

$$t=\lceil \frac{m}{2}\rceil .$$

则非根结点的关键字数范围为 $t-1$ 到 $m-1$。

DEF定义 · m 阶 B 树的结点边界

设 $t=\lceil m/2\rceil$，对 m 阶 B 树：

• 非根结点：子树数 ∈ $[t,m]$，关键字数 ∈ $[t-1,m-1]$；
• 非叶根结点：子树数 ∈ $[2,m]$，关键字数 ∈ $[1,m-1]$；
• 叶结点：都在同一层，且同样满足关键字数上下限（根单独讨论）。

根是最常见的例外，不能把非根的下限套到根上。

例：5 阶 B 树

• 每个结点最多 5 棵子树、4 个关键字；
• 非根内部结点至少 3 棵子树、2 个关键字；
• 非叶根至少 2 棵子树、1 个关键字。

根结点是最常见的例外。不能把"非根至少 $t-1$ 个关键字"直接套到根上。

EX示例 · 5 阶 B 树的上下界

取 $m=5$，$t=\lceil 5/2\rceil =3$。

结点类型	子树数范围	关键字数范围
根（非叶）	$2\sim 5$	$1\sim 4$
非根结点	$3\sim 5$	$2\sim 4$

注意根最少只要 1 个关键字，而非根结点最少要 2 个。若把根的 2 子树 / 1 关键字误认为所有结点的下限，就会在构造题中出错。

结点内的查找

假设当前结点关键字为：

$$K_1<K_2<\cdots <K_r,$$

并有指针 $P_0,P_1,\dots ,P_r$：

• 若 $key=K_i$，查找成功；
• 若 $key<K_1$，进入 $P_0$；
• 若 $K_i<key<K_{i+1}$，进入 $P_i$；
• 若 $key>K_r$，进入 $P_r$。

结点内可以顺序比较，也可以在关键字数组中折半查找。B 树分析常把一次结点访问视为一次外存 I/O；结点内的若干 CPU 比较通常远便宜于再读一个磁盘页。

IDEA直觉 · 为什么"多分支"能省 I/O

二叉树每层只有两个分支，$n$ 个记录需要 ${\log }_{2}n$ 层，也就是 ${\log }_{2}n$ 次磁盘访问。B 树一个结点放 $m$ 个关键字、$m$ 个分支，每层能排除 $m$ 倍候选，层数降为 ${\log }_{m}n$。虽然结点内要多做几次 CPU 比较，但一次磁盘 I/O 就能把整个页读回内存，页内比较比再读一个页便宜得多。

高度与关键字数量

设根位于第 1 层，高度为 $h$，且 $h\ge 2$。让每个结点尽量少放关键字时：

• 根有 1 个关键字、2 个孩子；
• 第 2 层起，每个非根结点至少有 $t-1$ 个关键字和 $t$ 个孩子。

高度为 $h$ 的 m 阶 B 树最少关键字数为：

$$n_{min}=1+2(t-1)(1+t+\cdots +t^{h-2})=2t^{h-1}-1.$$

最多时每个结点都有 $m-1$ 个关键字和 $m$ 个孩子：

$$n_{max}=m^h-1.$$

例如 3 阶 B 树有 $t=2$，高度为 5 时最少关键字数为 $2\times 2^4-1=31$。

EX示例 · 高度为 5 的 3 阶 B 树最少关键字数

$m=3$，$t=\lceil 3/2\rceil =2$。让每个结点取最少关键字：

• 根：1 个关键字、2 个孩子；
• 第 2～5 层：每个非根结点 1 个关键字、2 个孩子（$t-1=1$，$t=2$）。

从根到叶共 5 层，结点总数 $1+2+4+8+16=31$，每个 1 个关键字，故最少 $31$ 个。这也正好是高度 5 的满二叉形结构。

高度口径会改变公式

若题目把最底层空指针也算一层，则上式中的 $h$ 要相应减 1。先画出题目所称的第 1 层和叶结点，再代公式。

插入：先落叶，再分裂

B 树插入总是先沿查找路径到达最底层结点，把新关键字按序插入。若结点插入后仍不超过 $m-1$ 个关键字，操作结束；若出现 $m$ 个关键字，则结点溢出。

对溢出结点：

1. 取第 $\lceil m/2\rceil$ 个关键字上移到父结点；
2. 上移关键字左侧内容形成一个结点，右侧内容形成另一个结点；
3. 子树指针按关键字区间一起分配；
4. 若父结点也溢出，继续向上分裂；
5. 若原根分裂，创建只含上移关键字的新根，树高增加 1。

THM定理 · 插入为什么只向上不向下

B 树插入总是先落到叶结点，新增关键字只会让结点"变满"（向上分裂），绝不会让已有结点"变空"（那属于删除的方向）。因此插入操作只有一条路：从叶往上，满了就分裂，直到某个父结点有空位或根被分裂成新根。

4 阶 B 树示例

4 阶 B 树每个结点最多 3 个关键字。向叶结点 [5, 6, 9] 插入 13 后得到 [5, 6, 9, 13]，发生溢出。取第 2 个关键字 6 上移，可分成：

这里右侧比左侧多一个关键字仍然合法：非根结点最少只需 $\lceil 4/2\rceil -1=1$ 个关键字。

EX示例 · 插入触发一次分裂

向空的 4 阶 B 树依次插入 5, 6, 9，得到一个结点 [5, 6, 9]（未满 3 个）。再插入 13：

1. 插入后 [5, 6, 9, 13]，有 4 个关键字，溢出；
2. 取第 $\lceil 4/2\rceil =2$ 个关键字 6 上移；
3. 左半边 [5]，右半边 [9, 13]，父结点为 [6]。

结果：

树高从 1 变为 2，所有叶仍同层。若父结点再溢出（例如连续插入多个），就继续向上分裂，可能直到根被分裂、树高再加 1。

删除：把问题移到叶结点

删除比插入多一个方向：结点不仅可能过满，还可能过少。

删除叶结点中的关键字

若删除后关键字数仍不少于 $t-1$，直接删除即可。若删除后少于下限，则需要向相邻兄弟借键或合并。

删除内部结点中的关键字

用它的中序前驱或后继替换，再到最底层结点删除原前驱或后继。实际减少关键字数的位置仍落在叶结点。

兄弟够借

若相邻兄弟的关键字数大于 $t-1$：

1. 把父结点中分隔当前结点与兄弟的关键字下移；
2. 把兄弟靠近分隔线的关键字上移到父结点；
3. 若是内部结点，同时移动相应子树指针。

关键字不是直接从兄弟横向搬过来，而是经过父结点"旋转"一次。

兄弟不够借

若相邻兄弟也只有最少关键字，则把"当前结点 + 父分隔关键字 + 兄弟结点"合并。父结点因此少一个关键字和一个孩子；若父结点也低于下限，继续向上修复。

根结点是例外：若根的最后一个关键字被合并下移，只剩一个孩子，就让该孩子成为新根，树高减 1。

PROP性质 · 借键与合并的触发条件

• 借键：兄弟有多余关键字（>$t-1$），只需旋转，父结点关键字数不变；
• 合并：兄弟也只有下限（=$t-1$），必须把父结点分隔关键字也拉进来，父结点因此少一个孩子，可能继续向上修复。

合并是"向上传播"的根源，而借键是局部的。

删除示例：3 阶 B 树的借键

考虑最右侧局部结构：

3 阶 B 树的非根结点至少有 1 个关键字。删除 78 后最右叶变空，而左兄弟 [60,62] 有多余关键字：将父中的 65 下移到最右叶，再把兄弟最大的 62 上移到父结点，得到：

新的最右叶关键字是 65。这个过程同时保持结点下限和区间次序。

EX示例 · 借键的完整走一遍

3 阶 B 树（$t=2$，非根至少 1 个关键字）。删除 [78] 里的 78：

1. [78] 变空，低于下限 1；
2. 父结点中分隔 [60,62] 与 [78] 的分隔键是 65；
3. 左兄弟 [60,62] 有 2 个关键字 > 1，够借；
4. 把 65 下移到右叶，把 62 上移到父结点。

结果 [55,62] | [47] | [60] | [65]。注意关键字是"经过父结点旋转"，不是直接 [78]→[65] 那么简单的横向搬动。

EX示例 · 兄弟不够借时合并

考虑一个 5 阶 B 树（$t=3$，非根至少 2 个关键字）的局部：当前叶 [40] 只有 1 个关键字（已低于下限），兄弟 [10,20] 也正好 2 个（下限），父分隔键 30。

合并时把三者合成一个结点 [10, 20, 30, 40]，共 4 个关键字（未超过 $m-1=4$）。父结点因此少了一个孩子和一个关键字。若父结点因此也低于下限，则继续向上合并。

B+ 树

B+ 树把"导航"和"数据记录"分开：

• 内部结点只保存用于导航的索引关键字和子树指针；
• 全部记录或记录指针都在叶结点；
• 叶结点按关键字顺序链接；
• 精确查找通常也要走到叶结点；
• 范围查询定位起点后，可以沿叶链顺序扫描。

本章在结构示意中采用"内部结点有 $k$ 个关键字、$k+1$ 个孩子"的分隔键口径。部分 408 教材把每个孩子的最大或最小关键字复制为索引，写成"$k$ 个孩子对应 $k$ 个关键字"。两种定义都能实现 B+ 树；涉及数量计算时必须使用题目给定口径，不能混用公式。

B 树与 B+ 树对比

特性	B 树	B+ 树
记录存放位置	内部结点和叶结点都可存记录	记录只在叶结点
精确查找终点	可能在内部结点提前结束	通常到叶结点结束
叶结点链接	通常不要求	按关键字顺序链接
范围查询	需要树内遍历	定位后沿叶链扫描
内部结点扇出	同页还要容纳记录，可能较小	只放索引，通常能容纳更多分支
常见用途	多路搜索结构	数据库与文件系统索引

EX示例 · 范围查询在两种树上的差别

查询"所有在 $[50,80]$ 之间的记录"：

• B+ 树：先沿树找到 $\ge 50$ 的最小叶结点，再沿叶链顺序扫描到 $>80$ 为止，只需一次树内定位，之后全是顺序读。
• B 树：没有叶链，必须回到树内中序遍历，在内部结点之间反复切换，往往要多次随机 I/O。

这就是"B+ 树更适合范围扫描"的直接原因。

为什么适合外存

若一个结点大小与磁盘页相近，一次 I/O 可读取数十乃至数百个索引项。分支因子增大后，包含海量记录的树仍可能只有少数几层。CPU 在页内多做几次比较，通常比再进行一次随机 I/O 便宜得多。

这也是 B+ 树常用于数据库索引的原因：内部结点扇出高，所有查询路径长度稳定，叶链又适合范围扫描。关于存储层次如何改变结构选型，可回看内存视角。

O(·)复杂度 · B 树与外存访问

设结点大小为磁盘页，分支因子 $m$，关键字总数 $n$。查找约需 ${\log }_{m}n$ 次结点访问（每次一次 I/O）。$m$ 越大，层数越少，I/O 次数越少。结点内关键字比较为 $O(\log m)$，通常远小于一次磁盘 I/O 的代价。

易错点

• "m 阶"表示最多 $m$ 个孩子，不是最多 $m$ 个关键字。
• 非根结点下限不能直接套到根结点；根有单独规则。
• 插入关键字先进入最底层，分裂时中间关键字可能上移到内部结点。
• 删除内部关键字最终会在最底层减少一个关键字。
• 借键要经过父分隔关键字，不能只在兄弟之间横向移动。
• B 树结点之间没有 B+ 树那样的叶链；顺序与范围访问是 B+ 树的突出优势。
• B+ 树的关键字/孩子计数存在教材口径差异，做题时以题干定义为准。

WARN易错点 · 混淆"m 阶"与"m 个关键字"

"m 阶 B 树"指一个结点最多 $m$ 个孩子，从而最多 $m-1$ 个关键字。把"m 阶"误读成"最多 m 个关键字"，会让所有上下界和分裂位置全错。$m$ 阶 B 树的关键字上限是 $m-1$。

小结

B 树用多路分支降低高度，并通过分裂、借键和合并保持所有叶结点同层。B+ 树进一步把记录集中到叶结点，用更高扇出和叶链优化索引与范围访问。分析这类题时，先写出阶数对应的上下界，再检查根例外和高度口径，复杂操作就会清晰许多。

练习

1. 写出 5 阶 B 树中根、非根结点的孩子数和关键字数范围。
2. 高度为 4 的 4 阶 B 树最少和最多可含多少关键字？明确高度口径后推导。
3. 向空 4 阶 B 树依次插入 5, 6, 9, 13, 8, 2, 12, 15，画出每次分裂并写出最终根关键字。
4. 构造一个删除后先向兄弟借键、再构造一个必须合并的 5 阶 B 树局部例子。
5. 为什么 B+ 树内部结点只保存索引后，通常能比同页大小的 B 树拥有更大扇出？这怎样影响 I/O 次数？