多路有序归并K-way merge
从多个已有序输入中逐次选择最小候选，生成有序输出。
- 核心约束
- 各输入有序，当前候选来自每个输入尚未输出的头部。
- 适用问题
- SST 压实、排序流合并与分片结果聚合。
- 边界与取舍
- 选择候选之外，还需计入 I/O、版本过滤与去重成本。
时间与空间#
N 为全部输入记录数，k 为非空有序输入路数。
- 时间复杂度
- 辅助空间
- ，不含输出及各输入 I/O 缓冲区
用最小堆保存每路头项，输出后替换该路候选；每条输入已经按同一顺序排列。两路归并为 。记录比较或解码不是常数时需另计。
工程中的应用#
1 个案例 · 附源码RocksDB 的分层压实选择若干有序 SST，归并为新文件，在维护读取语义的同时清理可回收记录。
附源码片段 · 存储与数据放置
基础原理参考资料
Princeton · Multiway索引最小堆维护多路输入头项的归并实现。