日期：2026-07-11
标签：#面试 #八股 #后端 #外部排序 #场景题
一句话答案
使用外部归并排序：分批读入内存排序生成有序段，再通过多路归并顺序读写磁盘得到最终结果。
面试口语版
500G 放不进 4G 内存，所以先预留程序和缓冲区空间，例如每次读取 2G 数据，在内存排序后写成一个有序临时文件，得到约 250 个有序段。第二阶段用最小堆做 K 路归并，每个文件只保留一小块读缓冲，堆中保存各段当前最小元素，反复弹出并补充，写入输出缓冲。若一次无法打开这么多文件或内存不足，就分多轮归并。瓶颈主要是磁盘 I/O，应尽量顺序读写、使用大块缓冲和多盘并行。
原理拆解
flowchart LR
A[500G输入] --> B[分块读取]
B --> C[内存排序]
C --> D[多个有序段]
D --> E[K路最小堆归并]
E --> F[最终有序文件]- 生成初始段复杂度约为各分块排序之和。
- K 路归并每条记录进行一次
log K堆操作。 - 可使用置换选择生成平均更长的初始有序段，减少归并轮数。
关键细节
- 先问记录大小、排序 Key、稳定性、磁盘数量和允许耗时。
- 临时空间通常至少需要接近一份输入大小，必须评估磁盘容量。
- 数据倾斜对范围分区并行排序影响很大，需采样确定分区边界。
- 分布式场景可使用 MapReduce/Spark 的 Shuffle Sort，但原理仍是分区加外部归并。
面试官追问
- K 取多大合适？
- 如何减少归并轮数？
- 排序过程中机器宕机如何恢复？
- 多块磁盘如何并行？
面试官追问参考答案
1. K 取多大合适？
受可用内存、每路读缓冲、输出缓冲、文件句柄和堆操作成本共同限制。K 越大归并轮数越少，但每路缓冲更小且随机切换更多；应先保证足够大的顺序读缓冲，再在文件句柄上限内压测选择。
2. 如何减少归并轮数？
增大初始内存块、用置换选择生成更长有序段、提高单次归并路数，或用更多机器按范围分区并行排序。核心是减少初始段数量和提高每轮合并规模，但不能牺牲顺序 I/O 效率。
3. 排序过程中机器宕机如何恢复？
每个有序段写临时文件，完成刷盘和校验后原子登记到任务清单；归并输出也按阶段生成新文件并记录输入列表。重启后删除未完成临时文件，从最近完整阶段继续，最终文件通过原子重命名或元数据切换发布。
4. 多块磁盘如何并行？
将输入段和临时段均匀分布到不同磁盘，独立线程做顺序读写，避免同一磁盘同时承担读写热点。归并时从多盘并行预取到缓冲区，输出写另一块磁盘；并发度以磁盘实际带宽和队列延迟为准。
学习清单
- 能画出“分块排序 + 多路归并”流程。
- 能分析内存、临时磁盘和文件句柄约束。
Maintained by · YihuiEdit on GitHub