给 20GB 文件“排排坐”——详解外部排序

给你一个 20GB 的大文件，里面每行是一个字符串，要求你对这个文件进行排序。

你的第一反应可能是：“简单！读进内存，调用 Collections.sort()​ 或者 Arrays.sort()​ 搞定！” 但等等... 20GB！你的服务器有多少内存？8GB? 16GB? 64GB? 除非你有“钞能力”配置的超级服务器，否则想把 20GB 的文件一次性读入内存进行排序，大概率会收获一个 OutOfMemoryError​ 大礼包。

这时候，我们就需要请出处理大数据排序的“杀手锏”——外部排序 (External Sorting)。

一、困境：当数据大到内存装不下

外部排序的核心思想很简单，既然不能“一口吃成胖子”（一次性载入内存），那就分而治之。它的基本逻辑是：

1. 分割 (Split / Chunk): 将大文件切割成若干个小块（chunk），每个小块的大小要能舒服地放入内存。
2. 内部排序 (Internal Sort): 对每个小块分别在内存中进行排序。
3. 归并 (Merge): 将所有排好序的小块，通过一种高效的方式合并（merge）成一个最终的、完全有序的大文件。

类比： 想象你要整理几万张扑克牌（20GB 文件），但你只有一个小小的牌桌（有限内存）。你没法把所有牌都摊在桌上整理。怎么办？

1. 你每次从牌堆里拿出一小叠（chunk）放在桌上（内存）。
2. 把桌上的这一小叠牌整理好顺序（内部排序）。
3. 把整理好的这叠牌放到一边（写回磁盘的临时文件）。
4. 重复这个过程，直到所有牌都变成了若干个有序的小叠。
5. 最后，你需要一个方法，把这些有序的小叠合并成一个完全有序的大牌堆（归并）。

二、执行步骤详解

阶段一：分割与内部排序 (Creating Sorted Runs)

• 确定块大小 (Chunk Size): 根据你可用的内存大小 X​ 来决定。比如，你有 2GB 可用内存，为了保险起见（留些余地给程序本身、缓冲区等），你可以设定块大小为 1GB。

• 处理过程：

  1. 从 20GB 的大文件中读取前 1GB 的数据到内存中。
  2. 使用高效的内存排序算法（如快速排序 QuickSort 或归并排序 MergeSort）对这 1GB 的字符串进行排序。
  3. 将排好序的这 1GB 数据写入磁盘上的一个临时文件（例如 temp_run_1.sorted​）。
  4. 继续读取下一个 1GB 的数据块，重复内存排序，并写入下一个临时文件 (temp_run_2.sorted​)。
  5. ... 以此类推，直到原始的 20GB 文件被完全处理完。

• 结果： 现在磁盘上有了大约 20 个（20GB / 1GB = 20​）排好序的临时文件（也称为 "runs"）。

阶段二：多路归并 (K-Way Merge) - 合并有序块

这是外部排序最关键、也最巧妙的一步。我们现在有 20 个已经排好序的文件，如何将它们合并成一个最终的有序大文件，同时避免将所有文件再次加载到内存？

• 核心武器：最小堆 (Min-Heap)

• 方法 (K-Way Merge, K=20):

  1. 为最终的排好序的输出文件 final_sorted.txt​ 创建一个写入流。

  2. 为每一个临时排好序的文件 (temp_run_1.sorted​ 到 temp_run_20.sorted​) 创建一个读取流/缓冲区。

  3. 创建一个最小堆 (Min-Heap)，其容量为 K (这里是 20)。堆中存储的对象需要包含两部分信息：字符串本身 和 它来自哪个临时文件。堆根据字符串进行排序。

  4. 初始化堆： 从每个临时文件 (run_1​ 到 run_20​) 中读取第一个字符串，将这 20 个字符串（连同它们的来源文件信息）加入最小堆。

  5. 循环归并：

     • 从最小堆中提取（poll()​ 或 extractMin()​） 具有最小字符串值的元素。这个元素就是当前所有待合并元素中最小的那个。
     • 将这个最小字符串写入最终的输出文件 final_sorted.txt​。
     • 查看这个最小字符串是来自哪个临时文件（比如 run_i​）。
     • 从 run_i​ 文件中读取下一个字符串。
     • 如果 run_i​ 文件还有数据，则将新读取的字符串（及其来源 run_i​）加入（add()​ 或 insert()​） 最小堆。
     • 如果 run_i​ 文件已经读完，则不向堆中添加任何内容。

  6. 终止条件： 重复步骤 5，直到最小堆变为空。此时，所有临时文件的数据都已被读取、比较并写入最终输出文件。

  7. 关闭所有文件流。删除临时文件（可选）。

类比（续）：

现在你有 20 个有序的小牌叠。你拿出 20 个指示器（堆）。

1. 从每个牌叠最上面拿一张牌，放在对应的指示器上。
2. 你看一下所有指示器上的牌，找出最小的那张。把它放到最终的有序大牌堆的最上面。
3. 看这张最小的牌是来自哪个小牌叠的，就从那个小牌叠再拿最上面一张牌，放到空出来的那个指示器上。
4. 重复比较指示器上的牌，找出最小的，放到大牌堆，然后从来源补充一张新牌到指示器... 直到所有小牌叠都空了。

三、关键点与考量

• I/O 是瓶颈： 外部排序涉及大量的磁盘读写操作（读原始文件、写临时文件、读临时文件、写最终文件）。因此，其性能主要受限于磁盘 I/O 速度，而非 CPU 计算速度。优化读写缓冲区大小、使用 SSD 等可以提升性能。
• 内存大小决定效率： 可用内存 X​ 越大，初始排序的块就越大，产生的临时文件数量 K 就越少。K 越小，后续 K-Way Merge 阶段的效率通常越高（堆操作和同时打开的文件句柄数更少）。
• K-Way Merge 的实现： 使用最小堆是实现高效 K-Way Merge 的标准方法。它保证了每次都能以 O(log K) 的时间复杂度找到全局最小的元素。
• 字符串比较： 注意字符串排序的规则（字典序）和可能的 Locale 问题。

四、知识体系卡片

• 外部排序 (External Sorting): 用于对无法完全载入内存的数据集进行排序的核心算法框架。
• 内部排序 (Internal Sorting): 在内存中对数据进行排序的算法（如 QuickSort, MergeSort, HeapSort）。外部排序的第一阶段使用内部排序。
• 分而治之 (Divide and Conquer): 将大问题分解为小问题处理的通用策略。
• K-Way Merge: 将 K 个已排序的序列合并为一个有序序列的过程。
• 最小堆 (Min-Heap): 支持快速查找最小值、插入和删除最小值的数据结构，是实现 K-Way Merge 的理想工具。

---

掌握外部排序，意味着你拥有了处理远超内存限制的大规模数据的基本能力。虽然原理不复杂，但其思想和技巧在数据库、大数据处理框架等领域有着广泛的应用。希望这篇讲解能帮助你理解这个强大的工具！