外存优先队列

缓冲为何改变吞吐 ​

内部内存二叉堆理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。一次 insert 或 delete-min 最坏沿 $O(\log (N+1))$ 个节点移动；具体操作也可能提前停止。堆数组虽然紧凑，但根叶路径跨越许多远隔块，直接放到磁盘上会产生大量随机 I/O。

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

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

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

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

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

海量事件流轨迹 ​

设磁盘上要调度事件

括号首项是时间戳。五次 insert 先进入根缓冲，不逐个访问叶。根缓冲达到阈值后按时间范围分为早、中、晚三批，并以连续块写入对应子结构。

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

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

摊还账本 ​

把一次满缓冲 flush 的 $O(M/B)$ I/O 平分给被移动的 $\mathrm{\Theta }(M)$ 项，每项每下降一层付 $O(1/B)$。当最大驻留规模为 $N\ge M$ 时，高扇出层数约为

因此得到 Sort 级的摊还主项。delete-min 的 refill 也要把读取、合并与后续写回计入同一摊还账本理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。。

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

适用范围与相邻结构 ​

Buffer Tree理路Buffer Treebuffer tree · 缓冲树在高扇出树节点积累操作并批量下推，以排序量级 I/O 支持批量动态操作。提供“积累操作再分组下推”的通用技术，外存优先队列还需保证全局最小端可及时访问。B-tree 擅长点查询和有序范围扫描，逐项 insert 加查最小键并不自动达到同样的批处理界。

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

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