外存 / 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 模式。缓存无关模型公理库缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。保留分层传输的分析目标，却要求算法不显式读取 $B$ 与 $M$；外存排序公理库外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。则把扫描、分批与多路归并组织成可达到排序 I/O 界的具体过程。B 树、B+ 树与缓冲树沿另一条路线用高扇出和批处理控制索引更新。

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