模型Model

外存 / I/O 模型

施工中 · 内容逐步修订

External-memory model · I/O model · Aggarwal–Vitter model

只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。

形式陈述

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

\operatorname{Scan}(N)=\Theta\!\left(\frac NB\right).

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

\operatorname{Sort}(N)=\Theta\!\left( \frac NB\log_{M/B}\frac NB \right),

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

直觉

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

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

一次 I/O 将外存中的完整 B 元素块传入可容纳 M 元素的内存 — 完整块传输与内存容量

例子与边界

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

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

该模型把跨层搬运单独计费，实际 CPU 时间和磁盘寻道延迟可在实现评估中另行测量。某些 cache-oblivious 结果还需要 tall-cache 假设，例如 $M=\Omega(B^2)$ ；这是具体定理的附加条件。若资料以字节或记录分别计量 $M,B$ ，比较公式前要先按记录大小统一单位。

推论与应用

外存分析为数据库索引、文件排序、图处理和科学计算提供统一成本语言。渐近记号在这里计的是块传输而非指令；同一算法可以拥有良好的 CPU 时间却产生糟糕的 I/O 模式。缓存无关模型保留分层传输的分析目标，却要求算法不显式读取 $B$ 与 $M$ ；外存排序则把扫描、分批与多路归并组织成可达到排序 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.

关系图谱25 个相邻概念 · 2 类关系

正在载入交互图谱…

前置三跳
前置二跳
前置一跳
当前条目
后续一跳
后续二跳
后续三跳

文字版关系按与当前条目的最短距离分组

类型化关系

被这些条目使用

外存排序 I/O 下界

“对外存中的比较排序，在两层外存模型中假设 $N M\ge2B$、只有一个磁盘（$P=1$），内部内存容纳 $M$ 个不可拆分的原子记录，一次 I/O 搬运 $B$ 个记录，且内部计算免费。对…”

线性哈希：分裂指针与溢出链

“哈希表需要把键映到候选桶并处理碰撞；线性哈希让主桶数一次只增加1。采用外存页模型，每个主桶页最多放C条定长记录，额外记录串入该主桶专属的溢出页，每溢出页容量同为C。单线程完成更新，无并发、事…”

外存排序

“在外存模型中，输入是外存中连续存放的 $N\ge1$ 个定长记录，内存容量为 $M$ 项，每块为 $B\ge1$ 项。取 $M/B$ 至少为一个足以容纳多个输入块、输出块和控制状态的固定常数…”

Buffer Tree

“在参数为 $(M,B)$ 的外存模型中，以B tree式高扇出层级为骨架，假设 $M/B$ 至少为实现所需的固定常数，取扇出 $\Theta(M/B)$ 的多路树。每个内部节点除分隔键外还维…”

B+ 树

“本页固定 separator（分隔键）$k i$ 等于右子树最小键的约定：小于 $k i$ 的键在其左侧，等于 $k i$ 的键向右走。关键不变量是每个子指针负责的键区间互不冲突并覆盖该节点…”

B 树

“若一个节点恰好装入一个外存块，树高为 $O(\log t N)$，搜索、插入和删除沿根叶路径只需 $O(1+\log t(N+1))$ 次 I/O；常数项覆盖空树及单个根页。节点内部的比较次…”

行存、列存与延迟取列

“为比较布局，在块传输模型中固定页有效载荷128字节，八行，每行四个16字节字段a,b,c,d，无NULL、压缩或额外元数据。行存一页容纳两行，共4页；列存每列一页，共4页。列存的字段位置i对…”

外存优先队列

“外存优先队列维护键值项，核心支持 insert、find min 与 delete min；常见扩展还有 decrease key 和批量输出。所选外存模型有内存容量 (M) 与块大小 (B…”

数据库物理计划的页与内存账本

“本页把I/O模型实例化为可手算的DB 4：每页有效载荷128B，每个输入槽64B（含固定元数据及预留链指针），输出槽128B。算子独占4个128B数据帧，另有本例专用64B控制区放有限游标、…”

数据库缓冲池：pin、latch与脏页

“缓冲池把按块传输的数据库页缓存在固定大小的帧中。页表映射pageID到frameID，帧至少记录页号、装载状态、pin计数、dirty标记和短期保护状态。槽页的RID先定位页，再在驻留帧内查…”

平均访存时间及其模型边界

“I/O模型常只计块传输数，AMAT则在一个简化时序模型中给它们加权。两者都是有边界的分析工具，并不是未经测量的真实CPU性能预测。”

平衡搜索树

““平衡”一词必须点明保证类型。AVL 与红黑树给出最坏情形界；随机顺序插入下普通 BST 的期望高度是 $O(\log n)$，却不是最坏保证；伸展树单次操作可达 $\Theta(n)$，提…”

可扩展哈希目录与局部分裂

“沿用哈希表的精确键值查询：哈希只定位候选，桶内仍比较完整键。这里改用按页传输的模型，每个物理桶是一页，可放最多 $C\ge1$ 条定长记录。单线程完成每次操作，无并发和崩溃；唯一键的重复pu…”

缓存无关模型

“它沿用外存模型的缓存 (M) 与块 (B)，再假设全相联和最优替换；算法代码不知道 (M,B)，分析仍以二者计 cache misses。Tall cache 如 (M=\Omega(B^2…”

缓存块、标记与直接映射

“外存模型按块传输计费，却未施加这里的直接映射约束；理想缓存又允许全相联和最优替换。不能拿理想缓存中可同时驻留的两个块，直接断言它们在此映射下不会冲突。”

凸包

“凸包适用于任意点集，每个成员由有限凸组合见证。Carathéodory 定理保证，在 $\mathbb R^d$ 中至多用 $d+1$ 个原始点即可表示任一凸包点。凸包未必闭，例如 $(0,…”

时间复杂度

“具体任务会换用更贴近瓶颈的模型。Word RAM按机器字操作计费，外存模型统计块传输，数据流模型同时约束遍数与存储，Work–Depth 模型把总工作和关键路径分开。相同算法在这些模型中的数…”

空间复杂度

“工程模型还需说明计量单位：$n$ 个机器字占 $\Theta(nw)$ 位。简洁数据结构比较信息论最少位数与冗余，线性 Sketch还报告失败概率，外存模型则区分内存容量、磁盘空间和块传输。”

形式陈述 ​

反向链接

形式陈述