外存 / I/O 模型

形式陈述 ​

Aggarwal–Vitter 外存模型把数据分置于两层：内部存储可容纳 $M$ 个元素，外部存储按连续块组织，每块含 $B$ 个元素。一次 I/O 在两层之间传输一个完整块，内部计算免费；算法复杂度是 I/O 次数。输入规模为 $N$ 个元素，并通常假设 $1\le B\le M/2$、$N>M$，且 $M,B,N$ 使用同一计量单位。若数据已在外存连续排列，完整读取的最优量级为

$$\mathrm{Scan}(N)=\mathrm{\Theta }\left(\frac{N}{B}\right).$$

在比较模型的标准参数范围内，外排的量级为

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

其中当 $N\le M$ 或对数小于常数时应把表达式理解为至少一次扫描的成本。上界由多路归并达到：内存同时缓冲约 $M/B$ 个有序段，每轮把段数缩小同一因子；下界来自一次 I/O 可实现的排列信息有限。

直觉 ​

数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。在 RAM 分析中连续读取 $N$ 项仍算 $N$ 次操作，随机读取也可能同阶；I/O 模型则把真正稀缺的跨层传输单独计价。一次块传输既然已经付费，算法应尽量使用块内全部 $B$ 个元素。顺序扫描因此只花约 $N/B$ 次 I/O，而反复触碰相距很远的位置可能每个元素都触发一次传输。

$M/B$ 表示内存能同时驻留多少块，也决定外排可进行多少路归并。B 树采用与块相称的高扇出，是同一原则在动态索引中的体现：每次读入一个节点便获得大量分支信息，而不是按二叉树深度逐层付费。

例子与边界 ​

若 $N={10}^9$ 个记录、每块容纳 $B=4096$ 个记录，连续扫描约需 $2.45\times {10}^5$ 次块传输，而按随机位置读取每条记录最坏可接近 ${10}^9$ 次。这里的数字不是换一组参数后的装饰：两种访问次序在 RAM 中同为 $\mathrm{\Theta }(N)$，在 I/O 模型中却相差约一个块因子，直接揭示模型要捕捉的瓶颈。

多路归并排序先在内存中形成大小约 $M$ 的有序段，再为每个输入段保留一块缓冲并批量输出。若每轮只能做二路归并，会忽略内存可同时容纳许多块的能力，增加不必要的轮数。相反，若整个输入已装入内存，则读入和写回各一次扫描即可，外排公式中的对数阶段不再出现。

该模型不是对机械硬盘寻道时间的逐周期仿真，也不声称 CPU 工作真的免费；它有意隔离数据搬运下界。某些 cache-oblivious 结果另需 tall-cache 假设，例如 $M=\mathrm{\Omega }(B^2)$，不能把该条件倒灌成所有外存算法的定义。若一个作者以字节计 $M,B$、另一个以记录计，比较公式前还必须固定记录大小。

推论与应用 ​

外存分析为数据库索引、文件排序、图处理和科学计算提供统一成本语言。渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。在这里计的是块传输而非指令；同一算法可以拥有良好的 CPU 时间却产生糟糕的 I/O 模式。B 树、B+ 树、缓冲树与外存归并正是通过批处理和高扇出逼近这些模型界。

模型还提醒实现者区分“顺序工作量”和“数据移动量”。把循环常数优化到更小，无法弥补访问顺序导致的额外块传输；只有重排计算、分块或改变数据布局，才能触及 I/O 复杂度的主项。

参考资料

• 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.
• Jeffrey S. Vitter, Algorithms and Data Structures for External Memory, Now Publishers, 2008, Chs. 2–3.