06 篇按键比较次数解释平衡树，09 篇用堆选择最小元素。若数据访问必须按整块搬运，相同数量的比较可能带来完全不同的块传输。一次装入多个相邻键，比沿许多互不相邻的指针访问更能利用这次传输。

本篇把 CPU 工作和块传输分开计量。块模型中的节省不自动对应某台机器的加速比；教学程序把磁盘表示成 Python 对象，统计逻辑块搬运，不进行真实磁盘性能测试。

先声明哪一层内存有界

令 N 为记录数，B 为每块容纳的记录数，M 为快存可容纳的记录数。一次块传输移动至多 B 条记录；尾块未满也计一次。快存中的比较不计为 I/O，但仍有 CPU 成本。块传输数不是系统调用数，也不是磁盘寻道次数。

归并模拟把快存容量写成 m 个块，M=mB。至少保留一个输出块；若每个输入有序段各需一个输入块，归并路数至多 m−1。堆中的段号、当前位置和最小候选还需要元数据空间：实际按字节规划内存时必须留出这部分，不能把所有可用字节都分给数据缓冲。

多路节点怎样减少点查传输

B 树把多个分隔键放在一个节点内。若一个节点放入常数个块、非根节点保持常数比例占用，分支数为 Θ(B)，高度才是 O(log_B N)。只扩大节点上限而不维持占用下限，不足以证明这个高度界。

B+ 式索引把记录集中在叶子，内部节点只引导搜索；叶子按键顺序串联。找到范围起点后，沿叶子顺序读取，不需要对每条输出记录重新从根查询。对输出 K 条记录，典型传输界是 O(1+log_B N+K/B)，前提包括块化叶存储与占用保证。

教学实现将静态批量建立与动态维护分开：它可以验证查找和扫描的块访问，但不据此宣称已实现插入分裂或删除合并。内部条目包含分隔键和指针，一个条目与一个叶记录可能大小不同；以同一个 B 表示容量是抽象模型，真实页面设计应分别计算。

初始有序段与归并趟

初始阶段每次读入至多 M 条记录，在快存排序后写为一个有序段。设段数 R=ceil(N/M)，之后每趟至多合并 m−1 个段，段数依次缩为 ceil(R/(m−1))，直到只剩一个。N 为 0 时没有段，也没有传输；只有一个初始段时不需要额外归并趟。

一次归并维持每段尚未输出的最小记录，用09篇优先队列思想选择全局最小者。输出后只推进该段。每个输入段本身有序，所以任何尚未进入候选的记录都不小于该段当前候选；候选最小值就是全部剩余记录的最小值。归纳可知输出有序且不丢失重复记录。

每趟读写不能总是简单写成精确的 2 ceil(N/B)：每个有序段都可能有独立尾块，应分别对段长向上取整后求和。渐近公式可以忽略常数与边界，实验计数不能。

失效边界

仅有两个缓冲块时，一个用于输出，只剩一个输入槽，不能用这套方案同时推进两路。把归并路数写成 m 而不保留输出块，会超出声明的数据缓冲上限。

若 B+ 索引叶只存记录 ID，完整记录分散在不同堆页，返回 K 条记录还可能产生 Θ(K) 次回表读取。索引叶扫描的 K/B 项不能直接代表整个数据库查询。叶中保留排序键的教学例没有这项回表成本。

静态索引的契约与证明

blocked_index.py 的 BlockedIndex(keys,B) 接受不同整数键，内部排序后批量装入；B 至少为 2，重复键拒绝。point(key)返回是否存在及读块数，range(lo,hi)返回半开区间内排序键列表及读块数；lo 大于 hi 抛 ValueError，相等时为空结果、零读块。空索引也不产生读块。

每个内部条目保存一个孩子的最大键。找到第一个最大键不小于目标的孩子，目标若存在只能位于它覆盖的区间；目标超过全部最大键时走最右孩子以确认不存在。对子树递归这一划分，最终只需在叶内查找。范围查询从 lo 的候选叶开始，顺序输出小于 hi 的键，遇到首个不小于 hi 的键停止；叶内与叶间有序保证不会漏项。

批量构造使每层节点数按向上取整除以 B 缩减，最后一组允许不足 B。因此本实现的对数高度由分组过程直接得到，不依赖它没有实现的动态删除占用规则。查询采用冷缓存，每次都从根计费；只保留一个当前逻辑节点块。结果列表占 O(K) 空间，不能计为常数查询内存。构造输入和模拟磁盘都在 Python 内存中，不是实际超内存索引。

怎样读取归并统计

external_sort.py 的 external_sort(values,block_size,memory_blocks)返回排序列表和统计字典。B 必须为正整数，m 至少为 3，输入记录为整数；非法类型抛 TypeError，非法容量值抛 ValueError。统计分别保存初始阶段和每趟归并的段长、读块、写块、逻辑缓冲峰值。初始模拟磁盘构造和最后结果列表物化不计入传输。

设 P 为归并趟数。初始排序 CPU 工作为 O(N log(M+1))，每趟使用堆选择候选的 CPU 工作为 O(N log(m))，共 O(N log(M+1)+PN log(m))；任意精度整数还需计比较位成本。块传输上界可写为 O(ceil(N/B)(1+P))，N=0 单独为零。这里初始完整段长为 mB，归并保持完整组块对齐，只有尾段可能不足块，因此非空样例每阶段恰读写 ceil(N/B) 块；这个精确等式不能推广到任意切段策略。

当 N 大于 M，P 随 log_{m−1}(ceil(N/M)) 增长；N 不大于 M 时 P=0。常见外排序公式的对数项应配扫描项并处理小输入，不能令小于 1 的对数产生负成本。所有传输上界均是给定模型与缓冲策略的确定性界，不是期望或高概率界。

N=100，B=4，m=3
初始段数：9
归并后段数：5 -> 3 -> 2 -> 1
阶段：初始生成 + 4 趟归并
每阶段：读25块，写25块
合计：读125块，写125块

上述数字来自实际模拟运行，逻辑缓冲峰值为 3 个块。每趟里剩下的单段组也读写一次，保持统一逐趟计数；这是一项明确的实现选择，可以优化跳过，不能无说明地混合两种计费方式。

独立参照与实际覆盖

1 2	`python3 examples/advanced-algorithms/check_blocked_index.py python3 examples/advanced-algorithms/check_external_sort.py`

本轮块索引检查通过：60 棵树、1950 次点查、70805 次范围查和 5 个异常检查。输入 0 到 127、B=8、查询 [16,48) 输出 32 个键：范围查询读 7 块，相同 32 个键分别冷缓存点查共读 96 块。7 块包括路径上的 2 个内部块、4 个结果叶和 1 个用于发现终止条件的边界叶。这个固定轨迹不证明所有范围都比点查划算。

外归并检查与独立 sorted 参照一致：9837 组穷举配置、324 组边界配置和 4 个非法参数检查通过。每阶段块数还与段长分别向上取整的独立公式对照，缓冲峰值不超过声明的 m 个数据块。结果文件为 results/blocked_index.json 与 results/external_sort.json，位于教学代码目录。

这是有限教学模拟，没有测量磁盘吞吐、缓存预取或墙上时间。逻辑磁盘、排序临时空间和输出物化仍消耗 Python 内存，不能把此运行描述为真正处理了装不进内存的数据。一般正确性依赖前面的分区与归并不变量，有限检查负责发现实现偏离。

接口与计数边界

练习

取 N=25、B=4、m=3，列出初始段长、每趟段长和读写块数。若跳过每趟单段组的物理重写，哪些计数需要改变？
给出一个索引叶只存 ID、记录散布在不同数据页的范围查询。分别计算索引扫描与回表成本，说明何时 K/B 不再描述总读取量。

参考资料

MIT 6.851 第 7 讲：PDF 第 1–2 页的外存模型、B 树与多路归并。本文不采用讲义的历史硬件延迟数字。
CMU 15-445 B+ 树讲义：PDF 第 1–3 页的叶存储、聚簇索引与扫描；范围传输式在本文列明条件下推导。