文件与外部排序：当内存装不下数据时
说实话，很多学数据结构的人，一听到「外部排序」就头大。我当年也一样。直到我在一个嵌入式数据采集项目里，遇到了一个尴尬的场景——SD卡里存了上千万条传感器记录，内存只有256KB。嗯，这时候你不得不面对一个问题：数据太多，内存装不下。
这一章，我们就来聊聊文件的结构，以及怎么在磁盘上完成排序。说白了，就是教你怎么用有限的内存，搞定海量数据的排序问题。
文件的逻辑结构与物理结构
先搞清楚一个基本概念：文件在程序眼里是什么样，在磁盘上又是什么样。
逻辑结构，就是程序员看到的样子。比如一个二进制文件，你把它当成一个连续的字节流；或者一个文本文件，你按行读取。这是抽象出来的视图。
物理结构，是磁盘上真实存储的方式。可能是连续的一块区域（连续文件），也可能东一块西一块（链式文件），或者用索引表来管理（索引文件）。
核心要点：逻辑结构决定你怎么编程，物理结构决定性能。我在项目中见过有人把逻辑结构当物理结构用，结果频繁随机读写，性能惨不忍睹。
举个例子。你写一个程序，打开文件，fseek到第1000个字节，然后读取。逻辑上很简单。但物理上，如果文件是链式存储，你得顺着链表一个个找，那速度就慢得离谱了。
顺序文件与索引文件
实际工程中，最常用的两种文件组织形式：顺序文件和索引文件。
顺序文件
顺序文件，就是记录一个挨一个地存。读的时候也只能从头往后读。听起来很笨？但它的优势是：顺序读写速度极快。磁盘的机械结构决定了，顺序读写比随机读写快一个数量级。
我在做日志系统时，就用的顺序文件。每条日志追加到末尾，读取时按时间顺序扫描。简单、可靠、性能好。
小技巧：如果你需要频繁追加数据，且读取时也是按顺序的，顺序文件是最佳选择。别搞复杂了。
索引文件
但顺序文件有个致命问题：查找慢。你想找第1000条记录，得从头读到第1000条。这时候就需要索引文件了。
索引文件，说白了就是给数据建一个「目录」。目录里记录每条记录的关键字和位置。查找时先查目录，再根据位置直接读取。
我曾经在一个项目里，用索引文件管理几十万条设备配置记录。查找速度从原来的秒级降到了毫秒级。嗯，这就是索引的威力。
| 文件类型 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 顺序文件 | 顺序读写快，实现简单 | 随机查找慢 | 日志、归档数据 |
| 索引文件 | 随机查找快 | 需要额外空间维护索引 | 数据库、配置管理 |
多路归并排序与败者树
好了，文件结构讲完了。现在进入正题：当数据量大到内存放不下时，怎么排序？
答案是：外部排序。核心思想就两步：
- 把大文件切分成若干个小块，每个小块都能装进内存。对每个小块内部排序，写回磁盘。这些小块叫「归并段」。
- 把这些归并段合并成一个有序的大文件。这就是「多路归并」。
你想想看，如果只有两路归并，那很简单：每次从两个段里各取一个最小的，比较后输出。但如果有k路呢？每次比较k个元素，找出最小的那个。如果k很大，这个比较的开销就上来了。
这时候，败者树就派上用场了。
败者树是什么？
败者树是一种树形结构，用来快速找出k个元素中的最小值。它的特点是：每个非叶子节点记录的是「败者」，也就是比较中输掉的那个。而胜者一路向上传递，最终根节点就是全局最小值。
我刚开始学的时候也觉得绕。后来自己手写了一遍，才明白它的巧妙之处。
关键点：败者树每次选出最小值后，只需要沿着路径更新一次，时间复杂度是O(log k)。而普通的选择法每次要比较k次，时间复杂度是O(k)。当k很大时，差距非常明显。
下面是一个败者树的简单实现，用于多路归并中的选择最小元素：
#define K 8 // 归并路数
// 败者树节点，存储的是段索引
int loser_tree[K];
// 每个段的当前值
int current_value[K];
// 初始化败者树
void init_loser_tree() {
int i;
// 先给每个段赋一个最小值
for (i = 0; i < K; i++) {
current_value[i] = read_next_from_segment(i);
}
// 初始化所有败者节点为K（表示空）
for (i = 0; i < K; i++) {
loser_tree[i] = K;
}
// 从最后一个段开始调整
for (i = K - 1; i >= 0; i--) {
adjust(i);
}
}
// 调整败者树，从叶子节点s开始向上调整
void adjust(int s) {
int parent = (s + K) / 2; // 父节点位置
while (parent > 0) {
if (current_value[s] > current_value[loser_tree[parent]]) {
// 当前节点输了，交换
int temp = s;
s = loser_tree[parent];
loser_tree[parent] = temp;
}
parent /= 2;
}
// 根节点记录最终的胜者
loser_tree[0] = s;
}
// 获取当前最小值所在的段
int get_min_segment() {
return loser_tree[0];
}
// 更新某个段的值后，重新调整
void update_segment(int seg) {
current_value[seg] = read_next_from_segment(seg);
adjust(seg);
}注意：上面的代码是简化版。实际项目中，你还需要处理段结束的情况（用无穷大表示）。我曾经在这个细节上栽过跟头——段读完了没处理，结果排序结果里多了一堆垃圾数据。
多路归并的整体流程
有了败者树，多路归并就变得很清晰了：
- 初始化：从k个归并段中各读一条记录，构建败者树。
- 循环：从败者树中取出最小值，写入输出文件。然后从该段读取下一条记录，更新败者树。
- 重复步骤2，直到所有段都读完。
你可能会问：k越大越好吗？理论上是的，k越大，归并的趟数越少。但k大了，内存中需要同时维护的缓冲区也大了。我个人的经验是，k取16到64之间比较合适，具体要看你的内存大小和记录长度。
知识体系总览
下面这张图，把本章的核心内容串起来了。你可以看到，文件结构是基础，外部排序是目标，败者树是关键技术。
避坑指南
最后，分享几个我踩过的坑：
- 缓冲区大小要匹配磁盘块大小。我曾经随便设了个缓冲区大小，结果每次读写都要跨磁盘块，性能直接腰斩。后来改成磁盘块大小的整数倍，速度就上来了。
- 归并段的数量不是越多越好。k太大，内存中维护的缓冲区太多，反而会因为内存不足导致频繁换入换出。我一般控制在16到32路。
- 注意处理段结束的情况。败者树中，某个段读完后，要给它赋一个无穷大的值，让它永远「输」。否则它会一直参与比较，导致排序结果错误。
- 文件读写用二进制模式。文本模式会有额外的转换开销，而且容易出问题。我习惯用fread/fwrite，简单直接。
个人建议：如果你刚开始接触外部排序，先用手写一个两路归并练手。跑通了，再改成多路，加上败者树。一步到位容易出bug，而且调试起来很痛苦。
好了，这一章的内容就到这里。文件结构是基础，外部排序是实战，败者树是优化手段。三者结合起来，你就能在内存受限的环境下，搞定海量数据的排序问题。
公众号:蓝海资料掘金营，微信deep3321