文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文以《算法导论第三版》第 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{n1}{2}$节点内部键升序排列键把子树区间切分成 $2t$ 个孩子区间。仓库 18.1.md 的习题 18.1-1 还专门讨论了一个容易忽视的点为什么不允许 $t 1$因为 $t1$ 意味着除根外每个节点至少 $0$ 个键、每个内部节点至少 $1$ 个孩子——只有 1 个孩子的内部节点与0 个键的节点在 B 树中都不存在因此最小度最小只能取 $t 2$即 2-3-4 树。习题 18.1-5 也从红黑树吸收红孩子后节点含 $1\sim3$ 个键、所有叶子同深度的性质得出红黑树等价于 $t2$ 的 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 的机制推导其过程要点供读者自行画图验证空树先创建一个根节点B-TREE-CREATE前两个键 $F, S$ 直接放入根节点不触发分裂插入 $Q$ 时根节点达到 $2t-1 3$ 个键$F, Q, S$第 4 个键 $K$ 到来前根必须先行分裂中键 $Q$ 上浮成为新根左右两个孩子各含 $1$ 个键此后每次遇到目标叶节点已满的情况都沿查找路径先分裂再下行B-TREE-SPLIT-CHILD 预分裂策略保证插入过程只有一次自顶向下的遍历由于 $t 2$任何节点超过 $3$ 个键就分裂中键上浮两个孩子各分得 $1$ 个键也可能出现借一个键形成 $2$ 键孩子的情况取决于中键位置与键的排列。最终的树所有叶子都在同一深度且除根外每个节点含 $1 \sim 3$ 个键。该题的核心价值在于直观展示分裂发生在满节点被再次访问之前这一 B 树插入的核心不变量。三、18.2-2B-TREE-INSERT 执行过程中的冗余 DISK-READ / DISK-WRITE题目定义冗余的 DISK-READ 是指对已经驻留内存的页再次发起读盘冗余的 DISK-WRITE 是指把与磁盘上已有内容完全相同的一页重新写回。结论在执行一次 B-TREE-INSERT 的过程中永远不会产生冗余的 DISK-READ 或 DISK-WRITE。3.1 为什么不会有冗余的 DISK-READB-TREE-INSERT 自顶向下处理要访问某个节点 $x$ 的孩子之前算法先递归/循环地保证 $x$ 已经在内存中B-TREE-INSERT 的第 7 行会 DISK-READ(x) 读取节点 $x$随后对孩子节点进行 DISK-READ。在整条根到叶的路径上每个节点至多被读取一次且读取时机恰好是在它被访问的当刻。当一个节点被读入内存后该次调用对它的后续访问如分裂后重新调整父节点指针、向叶节点写入键都直接命中内存不会重复发起读盘。因此不存在对已在内存中的页再次 DISK-READ的情况。3.2 为什么不会有冗余的 DISK-WRITE在向一个子节点已满但父节点未满的节点插入键时需要的操作序列是DISK-READ定位键应放入的页把满子节点读入内存DISK-WRITE把分裂后产生的新节点写回磁盘DISK-READ回溯到父节点父节点此时已在内存这一步是为了把中键合并入父节点后的状态写盘做准备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{n1}{2}$该过程执行 $O(h) O(\log_t n)$ 次 DISK-READCPU 时间同理为 $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$其前驱按如下三条规则确定$x$ 不是叶节点返回 $x$ 的第 $i$ 个孩子子树 $x.c_i$ 中的最大键即 $x.key_i$ 左侧紧邻子树中的最大值$x$ 是叶节点且 $i 1$返回 $x$ 的第 $i-1$ 个键 $x.key_{i-1}$同一节点内的左侧邻居否则叶节点且 $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$ 依次插入最小度 $t2$ 的空 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^{h1} - 1$$h$ 为树高对应节点数为 $2^{h1} - 1$。由于上界 $n-1$ 与下界 $2^{h1}-1$ 在渐进意义上是同一量级最终结论是$$ \text{节点数} \Theta(n). $$也就是说用递增序列构造一棵 $t2$ 的 B 树节点数随 $n$ 线性增长树高则保持 $O(\log n)$。这与二叉搜索树退化为链的极端行为形成鲜明对比——B 树的分裂保底机制保证了结构不会退化。六、18.2-5叶节点与内部节点采用不同最小度 $t$ 的改造题目背景叶节点不需要存储孩子指针因此在相同的磁盘页大小下叶节点理论上可以采用更大的 $t$ 值同一页能容纳更多键。题目要求说明如何修改创建与插入过程以支持这种差异。仓库解答给出的改造思路如下修改 B-TREE-INSERT 的节点分裂判定先判断目标节点是否为叶节点若是叶节点只有当其键数达到预期最大值的两倍时才分裂例如内部节点按 $2t_{in}-1$ 满判定而叶子按 $2t_{leaf}-1$ 满判定其中 $t_{leaf} t_{in}$当需要向一个已满的叶子插入元素时把该叶子分裂成两个叶子每个叶子中的键数都保持在合理范围内且所有叶子依旧处于同一深度。这一改动背后是 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 时间拆成路径开销 × 节点内开销两部分路径开销与二叉搜索树的 TREE-SEARCH 一样递归过程中访问的节点构成一条从根向下的简单路径因此 B-TREE-SEARCH 沿路径的 CPU 时间为 $O(h) O(\log_t n)$其中 $h$ 为树高$n$ 为键数且已知 $h \le \log_t \frac{n1}{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$ 不大如 $t2\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/split18.2 节的基本操作与 B 树其他主题环环相扣仓库中可对照阅读定义篇$t$ 的合法取值18.1-1、18.1-2、高度 $h$ 下的最大键数 $(2t)^{h1}-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 进行实战推演。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第18章 B 树深入解析B-TREE-INSERT 插入操作与磁盘 I/O 优化18.2 节全解CLRS 第18章 B 树深入解析B TREE INSERT 插入操作与磁盘 I/O 优化18.2 节全解 导读 本文以《算法导论》CLRS第 18文档教程示例工程CLRS 第12章二叉搜索树核心操作精解TREE-INSERT 与 TREE-DELETE 习题剖析及 C 实现对照CLRS 第12章二叉搜索树核心操作精解TREE INSERT 与 TREE DELETE 习题剖析及 C 实现对照 本篇技术指南以《算法导论》CLRS文档教程示例工程CLRS 算法导论 12.2 节精讲二叉搜索树查询操作TREE-MINIMUM / TREE-MAXIMUM / TREE-SUCCESSOR / TREE-PREDECESSOR与习题全解析CLRS 算法导论 12.2 节精讲二叉搜索树查询操作TREE MINIMUM / TREE MAXIMUM / TREE SUCCESSOR / TREE文档教程示例工程上一篇5个专业技巧怎样用SuperPNG高效优化Photoshop PNG导出工作流下一篇SMAPI模组清单配置终极实战指南从零到精通的5个关键步骤创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考