算法与数据结构

外部排序与 Top-K：超内存规模的处理

05-排序与检索进阶预计 20 分钟外部排序Top-K海量数据多路归并
学习状态：

一句话定义

当数据超出内存时，外部排序（External Sort）用「分块造有序 run → k 路归并」把 IO 次数压到 O(log_k(N/M)) 趟；流式 Top-K 用大小 K 的小顶堆以 O(n log K) 找前 K 大——两者的组合拳是「单机放不下的数据」这一类面试与工程题的标准解法。

为什么重要

「10GB 文件、1GB 内存，怎么排序 / 怎么找前 100 个高频词」是工程面试的常青题，考的不是背结论，而是把 kp-014（堆）、kp-020（归并）、kp-021（计数）按 IO 约束重新组装的能力。它也是数据库 ORDER BY、日志分析、排行榜的真实底层逻辑。

前置知识

kp-014（堆与 Top-K）；kp-020（归并）；磁盘顺序读远快于随机读的常识。

核心概念

  • 外存模型：内存 M、磁盘块大小 B；代价按「块传输次数」计，与 kp-015 的 IO 思想同源。
  • 两阶段：①每次读 M 大小的数据，内排序成有序 run 写回磁盘；②用 k 路归并（k ≈ M/B 个缓冲区）反复合并 run 直到只剩一个。
  • 多路归并的引擎：k 路各留一个「当前头」，用小顶堆（或败者树）取全局最小——取走后从同一路补下一个，堆操作 O(log k)。
  • 趟数公式：初始 run 数 N/M，每趟归并最多 k 路 ⇒ 趟数 ⌈log_k (N/M)⌉；增大 k（多缓冲）或造更长初始 run（置换选择排序）都能减趟。
  • 流式 Top-K：小顶堆容量 K；新元素 > 堆顶才替换，O(n log K)，内存 O(K) 与数据总量无关。
  • 海量词频：哈希分片（同一词必落同片）→ 每片独立计数 + 局部 Top-K → 汇总归并。

原理与机制

外排的机制是「把 IO 代价摊成趟数」：阶段一每次装满内存排序成一个有序 run 写回磁盘；阶段二用小顶堆做 k 路归并——堆顶即 k 路当前头中的全局最小，取走后从同一路补下一个，输出流天然全局有序。Top-K 的机制是「守门员」：容量 K 的小顶堆堆顶是当前候选中的最弱者，新元素赢过它才入堆。分片计数的机制靠哈希确定性：同键必落同片，片内统计即可全局汇总。

直观类比

外部排序像整理一屋子散落的档案但桌上只摊得开一部分：先把每摊整理成有序的一叠（run），再把 K 叠归并成更大的叠，反复几轮全部有序。Top-K 像选秀「预定的 N 强席」：席位只有 K 个，新人想上台必须打败当前席上最弱的——堆顶就是那个最弱的。

公式或模型

  • 趟数与 IO：N=10GB、M=1GB、B=4KB ⇒ 初始 run 10 个；若 k=10 则 1 趟归并完成；k 小则 ⌈log_k 10⌉ 趟。每趟读写全量 ⇒ IO ≈ 2·(N/B)·趟数。
  • Top-K：T(n) = n 次「比较 + 至多替换」= O(n log K)；全排序对照 O(n log n)——K≪n 时差距显著。
  • 海量词频总代价：分片 O(n) + 片内计数 O(n) + 汇总 O(K·片数)，总体近似线性。

图示

两阶段外排（N=10GB, M=1GB）:
阶段1 造 run: [1GB→排序→run1][run2]…[run10]（各自有序，写回磁盘）
阶段2 归并:   run1 ─┐
              run2 ─┤ 小顶堆取最小 → 输出全局有序
               …    │  （每路缓冲一个「当前头」）
              run10 ─┘
流式 Top-K（K=100）:
  新元素 > 堆顶? → 弹堆顶、压入新元素、下沉 ; 否则丢弃

实例或案例

  • 「1GB 内存找 10GB 日志中前 100 个高频 IP」：哈希分片 20 片 → 片内 HashMap 计数 + 小顶堆 Top-100 → 20 份候选归并出全局 Top-100。
  • 数据库 ORDER BY 超过 work_mem 时正是外排：造 run + 多路归并（PostgreSQL/MySQL 均如此）。
  • 排行榜实时更新：Redis ZSet（跳表 + 哈希）或对流式数据用堆近似。
  • 相似延伸：Count-Min Sketch 可在固定内存内估计高频项（与堆组合成「Heavy Hitters」方案）。

常见误区

  • 把 10GB「先读进内存再排序」：题目条件即不允许；任何方案必须显式写出 run 与归并。
  • Top-K 用全排序：O(n log n) 且内存 O(n)；正确姿势是 K 元小顶堆 O(n log K)。
  • 求前 K 大用大顶堆：逻辑可行但需全量 O(n) 内存；小顶堆只留 K 个。
  • 分片用随机哈希：分片函数必须对键确定（同一键同片），否则计数被拆散；也不能按「行号 mod k」分。
  • 忽略 k 路归并的缓冲区约束：k 太大则每路缓冲过小、随机化读取加剧，k ≈ M/B 附近取。

自测题

  1. 设计「1GB 内存排序 100GB 整数」方案并估算趟数（B=4KB，可并行读 100 路）。

答案要点：每次读 1GB 排序成 run ⇒ 100 个 run；100 路归并 1 趟完成（k=100 ≤ M/B≈25 万的缓冲上限，实际受缓冲区大小限制，可行）；总 IO ≈ 2 趟全量读写。

  1. 为什么 k 路归并要用堆而不是两两归并？

答案要点：两两归并趟数 log₂k，每趟全量 IO；堆式 k 路一趟完成，IO 少一个对数因子，代价仅每次取最小 O(log k)。

  1. 流式求最大 K 个：为什么堆顶是「最小」的堆？

答案要点：需要快速拿到「K 个候选中最弱者」来决定淘汰谁，小顶堆顶恰是它，替换 O(log K)。

与其他知识点的关系

kp-014 堆是本节两个主角（归并引擎与 Top-K）的共同零件；kp-015 LSM 的分层合并与 run 归并同构；kp-021 的基数排序可替换内排序阶段处理整数；kp-010 的布隆/概要思想是本节的概率化延伸。

延伸阅读

《编程珠玑》开篇专栏（位图排序与「问题定义先于算法」）；《算法导论》关于多路归并与置换选择排序的章节；Database Internals 关于外排的工程细节。

前置知识点

相关知识点