外存优先队列 | Codeboy's Blog

接口与成本单位

外存优先队列维护键值项，至少支持 insert 与 delete-min；常见扩展还有 find-min、decrease-key 和批量输出。模型有内存容量 (M) 与块大小 (B)，一次 I/O 搬运一个块，CPU 比较不计为 I/O。

对 (N) 项，一类典型目标是让操作成本达到外存排序的单位摊还量。若 [ \operatorname{Sort}(N) =\Theta!\left( \frac{N}{B}\left(1+\log_{M/B}\frac{N}{B}\right)\right), ] 则目标可写成每操作摊还 (O(\operatorname{Sort}(N)/N)) I/O，也就是大规模区间内的 (O((1/B)\log_{M/B}(N/B))) 主项。文献中的最坏、摊还、insert 与 delete-min 界并不完全相同，引用结果时必须保留原量词。

缓冲为何改变吞吐

内部内存二叉堆一次 insert 或 delete-min 沿 (\Theta(\log N)) 个节点移动。堆数组虽然紧凑，但根叶路径跨越许多远隔块，直接放到磁盘上会产生大量随机 I/O。

外存结构把更新先写入内存或根缓冲。缓冲积累到 (\Theta(M)) 项后，按键区间或目标层分组，以 (\Theta(M/B)) 个整块下推。一次 flush 的 I/O 被 (\Theta(M)) 项共同承担；单项不再为每层独占一次块传输。

内部节点维护分隔键、缓冲范围和必要的最小值摘要。flush 后的结构不变量是：每项仍归属于覆盖其键区间的唯一逻辑路径，父层尚未下推的项与子层已有项共同组成当前集合，任何重复项都不能在两处被重复输出。

delete-min 必须物化输出前沿

insert 可以延迟，delete-min 却必须知道全局最小项。常见设计在靠近输出端维护一个已排序的小批次或最小项缓冲；当它耗尽时，从若干候选缓冲中抽取下一批，合并后只物化最小前缀，其余项留在较高层。

如果一次 refill 输出 (K) 个最小项，读取候选、合并和写回的成本应摊到这 (K) 次 delete-min。所谓 output-sensitive flush 正是按实际产出的最小项数量收费；只分析内部重排而漏掉把结果交给调用者的 (K/B) 个输出块，会低估批处理成本。

海量事件流轨迹

设磁盘上要调度事件 [ (40,a),(12,b),(35,c),(7,d),(28,e), ] 括号首项是时间戳。五次 insert 先进入根缓冲，不逐个访问叶。根缓冲达到阈值后按时间范围分为早、中、晚三批，并以连续块写入对应子结构。

第一次 delete-min 发现输出前沿为空，于是读取早期候选批，将 ((7,d),(12,b)) 排成一个小输出缓冲，返回 ((7,d))。第二次调用直接返回仍在内存中的 ((12,b))。若此时插入 ((5,f))，它位于更高层缓冲，逻辑最小值已改变；实现要么让 find-min 同时比较各层摘要，要么先把它并入输出前沿，不能继续机械返回 35。

这条轨迹展示了延迟写入的核心正确性条件：尚未 flush 不等于尚未生效。所有层的缓冲、叶存储与输出前沿共同定义当前优先队列状态。

摊还账本

把一次满缓冲 flush 的 (O(M/B)) I/O 平分给被移动的 (\Theta(M)) 项，每项每下降一层付 (O(1/B))。高扇出层数约为 [ O!\left(\log_{M/B}(N/B)\right), ] 因此得到 Sort 级的摊还主项。delete-min 的 refill 也要把读取、合并与后续写回计入同一势能账本。

摊还界允许某一次操作触发级联 flush。要求低尾延迟或实时截止期时，应采用去摊还结构并报告最坏界；不能把平均每项的小数 I/O 解释成每次调用都少于一次物理读盘。

适用范围与相邻结构

Buffer Tree提供“积累操作再分组下推”的通用技术，外存优先队列还需保证全局最小端可及时访问。B-tree 擅长点查询和有序范围扫描，逐项 insert 加查最小键并不自动达到同样的批处理界。

重复键需要稳定次序或显式句柄。decrease-key 若旧键无法按句柄定位，可记录删除标记加新键，但 delete-min 必须过滤失效副本并把清理成本计入。内存放不下所有顶层缓冲、键记录跨块、或每个 flush 只写少量项时，(1/B) 的摊薄都会消失。

经典 I/O 模型也不包含 SSD 写放大、并发锁、崩溃恢复和操作系统页缓存的双重缓冲。这些是工程层约束，不应悄悄混入或替代块传输复杂度。

参考资料

Lars Arge, The Buffer Tree: A New Technique for Optimal I/O Algorithms, WADS, 1995.
Gerth Stølting Brodal and Jyrki Katajainen, Worst-Case Efficient External-Memory Priority Queues, SWAT, 1998.
Jeffrey Scott Vitter, External Memory Algorithms and Data Structures, ACM Computing Surveys, 2001.

接口与成本单位 ​

缓冲为何改变吞吐 ​

delete-min 必须物化输出前沿 ​

海量事件流轨迹 ​

摊还账本 ​