外存排序 I/O 下界

定理 ​

在两层外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。中，假设 $N>M\ge 2B$、只有一个磁盘（$P=1$），内部内存容纳 $M$ 个不可拆分的原子记录，一次 I/O 搬运 $B$ 个记录，且内部计算免费。在比较/置换模型下，对 $N$ 个不同键排序的最优块传输次数为

$$\mathrm{Sort}(N)=\mathrm{\Theta }(\frac{N}{B}max\{1,{\log }_{M/B}\frac{N}{B}\}).$$

其中 $\mathrm{\Theta }$ 的下界来自排序或置换的信息计数，上界由多路归并排序达到。$max\{1,\cdot \}$ 把必须读写输入的扫描量保留在同一公式内，避免在对数小于 $1$ 的参数区间机械引用一个过低的界。

信息计数图像 ​

排序必须区分 $N!$ 个输入排列。某一时刻内存只有 $M$ 个记录；一次读入新块能选择哪些记录进入哪些内存位置，能新增的可区分布局受 $B$ 与已有 $M$ 限制。把每次 I/O 可扩大的排列状态数连乘，再要求覆盖 $N!$，取对数后得到上述下界。严谨证明用 I/O 图或 counting argument 处理块内容和磁盘位置，不能直接照搬二叉比较树的 $\log N!$。

为什么底数是 M/B ​

多路归并在内存中为约 $M/B$ 个 run 各留一块输入缓冲，再留输出缓冲；一轮扫描把 run 数缩小约 $M/B$ 倍，需 ${\log }_{M/B}(N/B)$ 轮。下界说明在模型假设内，这种利用全部缓冲扇出的算法已达最优量级。

边界 ​

本页定理固定 $N>M\ge 2B$；若另取 $N\le M$，数据一次读入后可在内存免费排序，只需扫描 I/O。整数键允许 radix、压缩记录、批量编码或字操作时，indivisibility/比较模型改变；并行磁盘 $P>1$ 也改变每轮带宽。下界计传输次数，不模拟寻道、预取或 CPU 时间，不能跨模型宣称所有外排都受同一公式限制。

Permuting 与 sorting ​

下界常先证明 permuting：把记录重排到任意指定顺序需要多少 I/O，再用排序产生的键次序编码排列。若记录可以拆成比原子更小片段或压缩许多键进一字，状态计数改变。反之，带 payload 的数据库记录排序通常正符合原子/indivisibility 假设。

$\mathrm{Sort}(N)$ 的 max 项正是在统一表达这个边界。当 $M/B$ 很大时，对数项可能低于 $1$，但每轮仍需读写 $\mathrm{\Theta }(N/B)$ 块；不能只看归并层数缩短而漏掉扫描输入的成本。

一个 I/O 能产生多少新排列 ​

内部内存一次容纳 $M/B$ 个块。读入一个新块后，算法可把其中 $B$ 个记录与内存中至多 $M$ 个记录重排，再选择 $B$ 个写出；单次 I/O 可区分的组合数量受大约 $(\genfrac{}{}{0ex}{}{M+B}{B})$ 控制。把所需区分的 $N!$ 个输入排列与每次 I/O 的分支能力比较，并同时保留输入扫描下界，得到

$$\mathrm{\Omega }(\frac{N}{B}max\{1,{\log }_{M/B}\frac{N}{B}\})$$

的 comparison-based 排序下界。

当 $N\le M$，数据一次装入内存，式子应退化到扫描输入输出的 $\mathrm{\Theta }(N/B)$，不能机械保留负数或小于 1 的对数。允许整数分桶、压缩键、多个独立磁盘或并行 I/O 时，决策能力改变，必须重新声明模型而非继续引用此下界。

下界衡量块传输，不计算内存内部比较次数。一个算法可以达到最优 I/O 却做更多 CPU 工作；外排序实践还要同时报告顺序读写、寻道和归并缓冲配置。

参考资料

• Alok Aggarwal and Jeffrey S. Vitter, “The Input/Output Complexity of Sorting and Related Problems,” Communications of the ACM 31(9), 1988, pp. 1116–1127；§2 给出含 $N,M,B,P$ 的 I/O 模型，Theorem 3.1 给出 sorting/FFT 界，本页取单磁盘特例 $P=1$。
• Jeffrey S. Vitter, Algorithms and Data Structures for External Memory, Foundations and Trends in Theoretical Computer Science 2(4), 2008, pp. 305–474；Chapter 5 “External Sorting and Related Problems”及 Theorem 5.1 给出排序上界，Chapter 6 定位匹配下界。