CLRS 习题精解：B 树基本操作（B-TREE-INSERT、查找最值与前驱）与复杂度分析

• 文档
• 教程
• 教育

本文以《算法导论（第三版）》第 18 章 18.2 节"B 树的基本操作"为骨架，围绕 CLRS 开源题解仓库 docs/Chap18/18.2.md 中的七道课后习题（18.2-1 至 18.2-7），完整讲解 B 树插入流程中DISK-READ/DISK-WRITE的访问语义、最值与前驱查找的伪代码实现、递增序列插入后的节点规模上界，以及磁盘页大小与最小度 $t$ 的工程权衡。读者读完可以掌握 B 树基本操作在算法层面与磁盘 I/O 层面的完整分析思路，并能直接复用到数据库索引与文件系统等以 B 树为核心结构的场景。

该章节在仓库 mkdocs.yml 的导航中对应 "18.2 Basic operations on B-trees"，与 18.1 Definition of B-trees、18.3 Deleting a key from a B-tree 共同构成 B 树的"定义—基本操作—删除"完整知识链；章末问题 18-2 Joining and splitting 2-3-4 trees 与 18-1 Stacks on secondary storage 则在此基础上考察 join/split 与磁盘栈等延伸应用。仓库文档使用 KaTeX 渲染数学公式（见 docs/js/katex.js 中的$$/$定界符配置），因此下文沿用$与$$书写行内与行间公式。

一、回顾：B 树的定义与基本操作框架

在进入习题之前，先回顾 B 树的关键定义。B 树是为磁盘等慢速二级存储设计的多路平衡查找树，其核心参数是最小度 $t$：

• 除根以外的每个节点至少包含 $t-1$ 个键，至多包含 $2t-1$ 个键；
• 除根以外的每个内部节点至少有 $t$ 个孩子，至多有 $2t$ 个孩子；
• 所有叶节点处于同一深度（树高 $h$ 满足 $h \le \log_t \frac{n+1}{2}$）；
• 节点内部键升序排列，键把子树区间切分成 $2t$ 个孩子区间。

仓库 18.1.md 的习题 18.1-1 还专门讨论了一个容易忽视的点：为什么不允许 $t = 1$？因为 $t=1$ 意味着除根外每个节点至少 $0$ 个键、每个内部节点至少 $1$ 个孩子——"只有 1 个孩子"的内部节点与"0 个键"的节点在 B 树中都不存在，因此最小度最小只能取 $t = 2$（即 2-3-4 树）。习题 18.1-5 也从红黑树吸收红孩子后节点含 $1\sim3$ 个键、所有叶子同深度的性质，得出红黑树等价于 $t=2$ 的 B 树。这些定义性质是理解 18.2 节所有操作的基础。

本节的基本操作包括：

• B-TREE-SEARCH：在节点内线性扫描，沿根到叶的路径查找；
• B-TREE-CREATE：创建仅含一个根节点的空 B 树；
• B-TREE-INSERT：先分裂路径上的满节点（分裂沿查找路径"预下行"进行），再把新键插入叶节点，全程只需自顶向下一次遍历；
• B-TREE-SPLIT-CHILD：分裂满节点 $y$ 为其父节点 $x$ 的某个孩子，中键上移。

删除操作（B-TREE-DELETE）则在 18.3.md 中给出递归伪代码框架。下面逐题展开 18.2 节的解答。

二、18.2-1：最小度 2 空 B 树的插入过程演示

题目要求：按顺序把键 $F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E$ 插入一棵最小度 $2$ 的空 B 树，画出每次节点即将分裂之前的树形配置，以及最终的配置。

仓库文档对此题标注为(Omit!)，即该题解答在 docs/Chap18/18.2.md 中被省略。虽然仓库未给出逐步图示，但我们仍可根据 B-TREE-INSERT 的机制推导其过程要点，供读者自行画图验证：

1. 空树先创建一个根节点（B-TREE-CREATE），前两个键 $F, S$ 直接放入根节点，不触发分裂；
2. 插入 $Q$ 时根节点达到 $2t-1 = 3$ 个键（$F, Q, S$），第 4 个键 $K$ 到来前，根必须先行分裂：中键 $Q$ 上浮成为新根，左右两个孩子各含 $1$ 个键；
3. 此后每次遇到"目标叶节点已满"的情况，都沿查找路径先分裂再下行（B-TREE-SPLIT-CHILD 预分裂策略），保证插入过程只有一次自顶向下的遍历；
4. 由于 $t = 2$，任何节点超过 $3$ 个键就分裂，中键上浮，两个孩子各分得 $1$ 个键（也可能出现"借一个键"形成 $2$ 键孩子的情况，取决于中键位置与键的排列）。

最终的树所有叶子都在同一深度，且除根外每个节点含 $1 \sim 3$ 个键。该题的核心价值在于直观展示"分裂发生在满节点被再次访问之前"这一 B 树插入的核心不变量。

三、18.2-2：B-TREE-INSERT 执行过程中的冗余 DISK-READ / DISK-WRITE

题目定义：冗余的 DISK-READ 是指对已经驻留内存的页再次发起读盘；冗余的 DISK-WRITE 是指把与磁盘上已有内容完全相同的一页重新写回。

结论：在执行一次 B-TREE-INSERT 的过程中，永远不会产生冗余的 DISK-READ 或 DISK-WRITE。

3.1 为什么不会有冗余的 DISK-READ

B-TREE-INSERT 自顶向下处理：要访问某个节点 $x$ 的孩子之前，算法先递归/循环地保证 $x$ 已经在内存中（B-TREE-INSERT 的第 7 行会 DISK-READ(x) 读取节点 $x$），随后对孩子节点进行 DISK-READ。在整条根到叶的路径上，每个节点至多被读取一次，且读取时机恰好是在它被访问的当刻。当一个节点被读入内存后，该次调用对它的后续访问（如分裂后重新调整父节点指针、向叶节点写入键）都直接命中内存，不会重复发起读盘。因此不存在"对已在内存中的页再次 DISK-READ"的情况。

3.2 为什么不会有冗余的 DISK-WRITE

在向一个"子节点已满但父节点未满"的节点插入键时，需要的操作序列是：

1. DISK-READ：定位键应放入的页（把满子节点读入内存）；
2. DISK-WRITE：把分裂后产生的新节点写回磁盘；
3. DISK-READ：回溯到父节点（父节点此时已在内存，这一步是为了把中键合并入父节点后的状态写盘做准备）；
4. DISK-WRITE：把填入中键后的父节点写回磁盘。

注意第 2 步写入的"新节点"是刚刚由分裂产生的新页，磁盘上此前并不存在该页的等价内容，因此不是冗余写；第 4 步写回的父节点因为新纳入了中键，内容已经发生变化，同样不是冗余写。

若父节点也恰好是满的，过程类似，只是需要把上述"分裂子节点"的步骤沿路径重复上推，直至根；每一步分裂都会产生一个内容全新的节点页，不存在与磁盘旧内容完全相同的写回。

3.3 关键洞察

从 18.2-2 的解答中可以提炼出 B 树插入的两个设计精髓：

• 预分裂（splitting on the way down）：与其在递归返回时发现满节点再分裂，不如在自上而下查找时就分裂沿途遇到的满节点。这一设计保证了单次插入始终只遍历一条根到叶路径，也保证每一次 DISK-WRITE 的对象都是"内容发生了真实变化"的页；
• 页粒度一致性：每个 DISK-READ / DISK-WRITE 都以整页为单位，算法只在页边界切换时才发生 I/O，这与 18-1 Stacks on secondary storage 中讨论的"磁盘访问按页计数"的代价模型一致——那里同样指出，页内多次操作可以摊销为 $O(1/m)$ 次磁盘访问（$m$ 为每页字数）。

四、18.2-3：在 B 树中查找最小键与给定键的前驱

题目要求：说明如何在 B 树中查找最小键，以及如何查找给定键 $x.key_i$ 的前驱。

4.1 查找最小键：B-TREE-FIND-MIN

最小键的查找与二叉搜索树完全同构：从根出发，一路沿最左孩子下行直到叶节点，叶节点的第一个键即为整棵树的最小键。伪代码如下（顶层的调用为B-TREE-FIND-MIN(T.root)，前置条件 $x$ 是 B 树 $T$ 上的一个节点，后置条件FCTVAL是 $x$ 子树中的最小键）：

B-TREE-FIND-MIN(x) if x == NIL // T is empty return NIL else if x.leaf // x is leaf return x.key[1] // return the minimum key of x else DISK-READ(x.c[1]) return B-TREE-FIND-MIN(x.c[1])

沿最左路径下行时，每访问一个非叶节点都伴随一次DISK-READ(x.c[1])，把最左孩子读入内存。由于树高 $h \le \log_t \frac{n+1}{2}$，该过程执行 $O(h) = O(\log_t n)$ 次 DISK-READ，CPU 时间同理为 $O(h)$。

4.2 查找最大键：B-TREE-FIND-MAX

仓库给出的配套过程B-TREE-FIND-MAX与最小键对称，沿最右孩子下行：

B-TREE-FIND-MAX(x) if x == NIL // T is empty return NIL else if x.leaf // x is leaf return x.[x.n] // return the maximum key of x else DISK-READ(x.c[x.n + 1]) return B-TREE-FIND-MIN(x.c[x.n + 1])

注：仓库原文最末一行写作return B-TREE-FIND-MIN(x.c[x.n + 1])，从语义上判断应为B-TREE-FIND-MAX（找最大键应沿最右孩子递归查找最大值），可视为原文档的一处笔误。读者阅读时注意甄别。

4.3 查找前驱：B-TREE-FIND-PREDECESSOR

给定节点 $x$ 中的键 $x.key_i$，其前驱按如下三条规则确定：

1. $x$ 不是叶节点：返回 $x$ 的第 $i$ 个孩子子树 $x.c_i$ 中的最大键（即 $x.key_i$ 左侧紧邻子树中的最大值）；
2. $x$ 是叶节点且 $i > 1$：返回 $x$ 的第 $i-1$ 个键 $x.key_{i-1}$（同一节点内的左侧邻居）；
3. 否则（叶节点且 $i = 1$）：自底向上回溯，找到最后一个满足"$x.key_i$ 位于 $y.c_j$ 的最左位置"的祖先节点 $y$ 与下标 $j$；若 $j = 1$，说明 $x.key_i$ 就是整棵树的最小键，前驱为NIL；否则返回 $y.key_{j-1}$。

伪代码如下（前置条件：$x$ 是 B 树 $T$ 上的节点，$i$ 是键的下标；后置条件：FCTVAL是 $x.key_i$ 的前驱）：

B-TREE-FIND-PREDECESSOR(x, i) if !x.leaf DISK-READ(x.c[i]) return B-TREE-FIND-MAX(x.c[i]) else if i > 1 // x is a leaf and i > 1 return x.key[i - 1] else z = x while true if z.p == NIL // z is root return NIL // z.key[i] is the minimum key in T; no predecessor y = z.p j = 1 DISK-READ(y.c[1]) while y.c[j] != x j = j + 1 DISK-READ(y.c[j]) if j == 1 z = y else return y.key[j - 1]

规则 3 的循环体体现了"沿右脊回溯"的经典技巧：从叶节点 $x$ 出发，逐层向上定位 $x$ 是其父节点的第几个孩子；一旦发现它不是父节点的最左孩子（$j > 1$），其父节点的第 $j-1$ 个键就是前驱。若一直回溯到根且始终处于最左位置（$j = 1$），则说明该键是全局最小键，不存在前驱。每轮回溯中while y.c[j] != x的线性扫描至多检查 $2t$ 个孩子指针，配合每步的 DISK-READ，总代价仍为 $O(h) \cdot t = O(t \log_t n)$。

五、18.2-4：向最小度 2 的空 B 树插入 $\{1, 2, \ldots, n\}$ 后的节点数量

题目（$\star$ 难题）：把键 $1, 2, \ldots, n$ 依次插入最小度 $t=2$ 的空 B 树，最终树有多少个节点？

5.1 上界：最多 $n - 1$ 个节点

最终树最多有 $n-1$ 个节点。原因很直观：除非 $n = 1$，否则永远不可能出现 $n$ 个节点——因为我们从不把一个键插入空节点（B-TREE-INSERT 总是把键插入到非空叶节点，或通过分裂产生新节点），所以树中始终存在至少一个含 $2$ 个键的节点（含 2 键意味着 $n$ 个键不可能恰好分配到 $n$ 个单键节点中）。

5.2 结构观察：非右脊节点永远只有 1 个键

由于插入的键 $1, 2, \ldots, n$严格递增，每个新键都比树中所有既有键大，因此每次插入都发生在树的最右脊（right spine，从根到最右下叶的路径）上。由此推出两个事实：

• 非右脊节点只能是分裂的产物，而 $t = 2$ 时每次分裂产生的两个子节点各含 $1$ 个键，所以非右脊节点恰好含 $1$ 个键；
• 右脊上的节点则可能累积多个键（直到满 $3$ 个键才分裂）。

5.3 下界：右脊节点全满时节点数最少

节点数最少的极端情况是右脊上的每个节点都恰好含 $3$ 个键（分裂拖延到极限）。此时可推得 $n = 2h + 2^{h+1} - 1$（$h$ 为树高），对应节点数为 $2^{h+1} - 1$。由于上界 $n-1$ 与下界 $2^{h+1}-1$ 在渐进意义上是同一量级，最终结论是：

$$ \text{节点数} = \Theta(n). $$

也就是说，用递增序列构造一棵 $t=2$ 的 B 树，节点数随 $n$ 线性增长，树高则保持 $O(\log n)$。这与二叉搜索树退化为链的极端行为形成鲜明对比——B 树的"分裂保底"机制保证了结构不会退化。

六、18.2-5：叶节点与内部节点采用不同最小度 $t$ 的改造

题目背景：叶节点不需要存储孩子指针，因此在相同的磁盘页大小下，叶节点理论上可以采用更大的 $t$ 值（同一页能容纳更多键）。题目要求说明如何修改创建与插入过程以支持这种差异。

仓库解答给出的改造思路如下：

1. 修改 B-TREE-INSERT 的节点分裂判定：先判断目标节点是否为叶节点；
2. 若是叶节点，只有当其键数达到"预期最大值的两倍"时才分裂（例如内部节点按 $2t_{in}-1$ 满判定，而叶子按 $2t_{leaf}-1$ 满判定，其中 $t_{leaf} > t_{in}$）；
3. 当需要向一个"已满的叶子"插入元素时，把该叶子分裂成两个叶子，每个叶子中的键数都保持在合理范围内，且所有叶子依旧处于同一深度。

这一改动背后是 B 树设计的一处经典工程权衡：磁盘页大小是硬约束（页越大，单次读写的字节数越多但 I/O 次数越少），而 $t$ 决定单页可容纳的键数。叶子页没有孩子指针的额外开销，同样的页大小可以容纳更大的 $t_{leaf}$，从而降低树高、减少查找路径上的磁盘访问次数。该思路与 18.2-7 的"页大小与 $t$ 联合优化"互相呼应，也体现了教材在定义中把叶节点与内部节点"键数下限/上限"分别约束的用意。

七、18.2-6：节点内二分搜索使 CPU 时间变为 $O(\lg n)$

题目：如果把 B-TREE-SEARCH 的节点内线性搜索改为二分搜索，证明 CPU 时间变为 $O(\lg n)$，且与 $t$ 如何随 $n$ 取值无关。

证明的关键是把 CPU 时间拆成"路径开销 × 节点内开销"两部分：

1. 路径开销：与二叉搜索树的 TREE-SEARCH 一样，递归过程中访问的节点构成一条从根向下的简单路径，因此 B-TREE-SEARCH 沿路径的 CPU 时间为 $O(h) = O(\log_t n)$，其中 $h$ 为树高，$n$ 为键数，且已知 $h \le \log_t \frac{n+1}{2}$；
2. 节点内开销：每个节点的键数小于 $2t-1$，节点内二分搜索耗时 $O(\lg t)$。

两者相乘，利用对数换底公式：

$$ \begin{aligned} O(\lg t \cdot \log_t n) & = O\left(\lg t \cdot \frac{\lg n}{\lg t}\right) && \text{（换底公式）} \ & = O(\lg n). \end{aligned} $$

因此节点内二分搜索使得 B-TREE-SEARCH 的总 CPU 时间为 $O(\lg n)$，与 $t$ 的选取完全无关。这一结论也解释了为什么教材的标准 B-TREE-SEARCH 默认使用线性搜索：当 $t$ 不大（如 $t=2\sim100$）时，节点内线性扫描的常数极小，二分搜索带来的 $O(\lg n)$ 理论优势主要体现为更少的键比较次数，但代价是额外的分支判断与索引计算；若 $t$ 随 $n$ 增长（如巨型节点），二分搜索则是保持 CPU 时间不随 $t$ 恶化的关键。

八、18.2-7：根据磁盘页读写时间选择最优最小度 $t$

题目：假设磁盘硬件允许任意选择磁盘页大小，读取一页耗时 $a + bt$（$a$、$b$ 为给定常数，$t$ 为所选页大小对应的 B 树最小度）。请选择 $t$ 使 B 树搜索时间（近似）最小，并给出 $a = 5$ 毫秒、$b = 10$ 微秒时的建议取值。

8.1 目标函数与求导

一次搜索需要沿路径访问 $O(\log_t n)$ 个节点，每访问一个节点读一页耗时 $a + bt$，故总搜索时间近似为：

$$ T(t) = \log_t n \cdot (a + bt) = \frac{a + bt}{\ln t} \cdot \ln n. $$

由于 $\ln n$ 是常数因子，只需最小化 $f(t) = \dfrac{a + bt}{\ln t}$。对 $t$ 求导：

$$ \frac{\partial}{\partial t}\left(\frac{a + bt}{\ln t}\right) = -\frac{a + bt - bt \ln t}{t \ln^2 t}. $$

令导数为零，得驻点条件：

$$ a + bt = bt \ln t. $$

8.2 用 Lambert W 函数求闭式解

令 $u = \ln t$，则 $t = e^u$，驻点方程变为：

$$ a + b e^u = b e^u u \iff \frac{a}{b} = e^u (u - 1). $$

两边同乘 $e^{-1}$ 并整理，可化为 Lambert W 函数的标准形式。代入题目数值 $a = 5,\text{ms}$、$b = 10,\mu\text{s} = 0.01,\text{ms}$（统一单位后 $a/b = 500$，或按原文档直接代入毫秒级单位），原文档给出的是：

$$ 5 + 10t = 10t \ln t \qquad\Longrightarrow\qquad t = e^{W\left(\frac{1}{2e}\right) + 1}, $$

其中 $W$ 为 Lambert W 函数（满足 $W(z)e^{W(z)} = z$ 的反函数）。数值计算 $W(1/(2e)) \approx 0.164$，于是 $t \approx e^{1.164} \approx 3.20$。由于 $t$ 必须是 $\ge 2$ 的整数，建议取值 $t = 3$。

8.3 工程含义

该题的结论极具工程价值：最小度 $t$ 并非越大越好。$t$ 增大的收益是树高 $\log_t n$ 降低、路径上读页次数减少；代价是单页容量增大、每页读写耗时 $a + bt$ 线性上升。最优 $t$ 恰好落在"再增大 $t$ 所节省的页访问次数，抵不过单页读写成本的增加"这一平衡点上。实际数据库（如 InnoDB 的 16 KiB 页）与文件系统通常依据介质特性（机械盘的 $a$ 远大于 $b$，而 SSD 的 $a$、$b$ 都更小）选取不同的页大小与节点容量，正是这一权衡的工业实践。

九、与同章内容的衔接：从基本操作到删除与 join/split

18.2 节的基本操作与 B 树其他主题环环相扣，仓库中可对照阅读：

• 定义篇：$t$ 的合法取值（18.1-1、18.1-2）、高度 $h$ 下的最大键数 $(2t)^{h+1}-1$（18.1-4）、红黑树与 2-3-4 树的等价关系（18.1-5）——这些性质为 18.2 节的复杂度分析提供了全部前提；
• 删除篇：B-TREE-DELETE 递归伪代码（18.3-2）与逐例删除演示（18.3-1，含仓库 img/18.3-1-*.png 系列图示）。删除过程同样依赖前驱/后继查找（与 18.2-3 的 B-TREE-FIND-PREDECESSOR 直接相关），且需要在下降过程中通过借键、合并保持节点键数不低于 $t-1$；
• 章末问题 18-2：在 2-3-4 树上实现 join 与 split。其解答利用"沿根到键 $k$ 的路径把树拆成一系列子树与键"，再通过 telescoping 求和证明 join 代价 $O(1 + |h' - h''|)$、split 总代价 $O(\lg n)$——这可以看作 18.2 节"沿路径自顶向下遍历 + 分裂调整"思想在更复杂操作上的延伸；
• 章末问题 18-1：讨论二级存储上的栈实现，用势能法把磁盘访问摊销到 $O(1/m)$，与 18.2-2 的页粒度 I/O 模型一脉相承。

综上，18.2 节七道习题从"插入时的磁盘 I/O 语义""最值与前驱查询的伪代码实现""递增序列构造的节点规模""叶子独立 $t$ 的扩展""二分搜索的 CPU 时间""页大小与最小度的工程权衡"六个维度，把 B 树基本操作从算法正确性讲到磁盘代价模型。建议读者按 18.1 → 18.2 → 18.3 的顺序逐章阅读，并结合章末两道 Problems 进行实战推演。

• 文档
• 教程
• 教育