目录一、 外部排序的基本概念1.1 内存与外存的矛盾1.2 核心衡量指标二、 外部排序的基本方法2.1 排序-归并策略 (Sort-Merge)2.2 归并趟数分析三、 多路平衡归并与败者树 (Loser Tree)3.1 增加归并路数的痛点3.2 败者树的原理3.3 性能提升四、 置换-选择排序 (Replacement-Selection Sort)4.1 减少初始归并段数量的痛点4.2 算法执行过程五、 最佳归并树 (Optimal Merge Tree)5.1 痛点与哈夫曼树的引入5.2 补充“虚段”六、 总结前言 在内存中内部排序一旦面对远超内存容量的数据时所有 O(n log n) 算法都失效。你不可能将整个 10GB 的日志文件一次性调入 1GB 的内存进行排序。此时排序的主战场从内存移到了磁盘核心矛盾也从比较次数变成了磁盘 I/O 次数。本文将深入拆解外部排序的完整技术栈从宏观的排序-归并策略到微观的败者树多路归并优化再到置换-选择排序生成超长初始归并段最后用最佳归并树将磁盘读写代价压缩到理论极限。掌握这些你才能真正理解大数据处理底层的排序哲学。一、 外部排序的基本概念1.1 内存与外存的矛盾外部排序专指待排序文件过大无法全部装入内存必须借助外存通常是磁盘进行排序的场景。内存与外存之间的速度鸿沟是外部排序一切优化的出发点访问速度差异内存的随机访问时间在纳秒级而磁盘的寻道和旋转延迟通常在毫秒级相差 5~6 个数量级。磁盘顺序读写的吞吐也远低于内存带宽。数据处理方式内部排序可以随意访问任何一个元素外部排序中的数据必须以块为单位从磁盘读入内存缓冲区处理完后再成块写回磁盘。单次 I/O 操作的时间远大于内存中数千次比较的时间。因此外部排序的目标不是减少元素间的比较次数而是竭尽所能地减少读写磁盘的趟数。1.2 核心衡量指标一个完整的外部排序过程的时间可以拆解为三部分内部排序时间将可以装入内存的数据块排成有序段的时间。内部归并时间在内存中对若干个有序段进行多路归并时选择最小元素、调整数据结构等因素消耗的 CPU 时间。外部读写I/O时间将数据从磁盘读入内存、将有序段写回磁盘的时间。这三者之中I/O 时间是绝对的主导因子。外部排序的总时间近似为总时间 趟数 × (读/写整个文件的 I/O 时间) 内部处理时间因为每次归并趟都需要将全部数据读写一遍至少读一次所有归并段写一次更大的归并段减少趟数就能成比例地削减总 I/O 时间。后面所有高级技术——多路归并、置换-选择、最佳归并树——最终都指向同一个目标让归并趟数尽可能小甚至只需一趟归并。二、 外部排序的基本方法2.1 排序-归并策略 (Sort-Merge)最经典的外部排序策略分为两个阶段生成初始归并段和归并。阶段一生成初始归并段将含有 n 个记录的大文件按内存缓冲区的大小 M可容纳的记录数划分为⌈ n / M ⌉ \lceil n/M \rceil⌈n/M⌉个大小相同的块。每次读取一个块进入内存用快速排序或堆排序等内部排序算法将其排好序然后作为一个有序段称为一个“归并段”或“Run”写回磁盘。这样磁盘上就留下了若干个独立的有序子文件。阶段二多路归并仿照归并排序的合并思想将这若干个有序归并段逐步合并成一个更大的有序段。由于内存空间有限一次只能同时打开有限数目的归并段进行归并这个数目记为k通常 k 远小于总的归并段数 m。整个过程需要对所有数据进行多趟归并第一趟将 m 个归并段归并成约m/k个更大的段第二趟再对这些段进行归并直到最终剩余一个有序文件。2.2 归并趟数分析假设初始归并段总数为 m采用 k 路平衡归并则归并的趟数 S 严格满足S ⌈ log ⁡ k m ⌉ S \lceil \log_k m \rceilS⌈logk​m⌉显然要减小 S只能走两条路增大归并路数 k —— 但这会引入新的问题在 k 个元素中挑选最小值所需的比较次数会随之增加。减小初始归并段数量 m —— 在总记录数固定的情况下就是要让每个初始归并段更长突破内存大小的物理限制。这两条优化路径分别引出了法败者树。和置换-选择排序这两种关键技术。三、 多路平衡归并与败者树 (Loser Tree)3.1 增加归并路数的痛点采用 k 路归并时每次需要从 k 个归并段各自的当前最小记录中选出全局最小的那一个放入输出文件。最朴素的做法是采用k-1次比较来逐一筛选这样每一趟归并的 CPU 时间将正比于k * 记录总数增加 k 虽然减少了 I/O 趟数但会让内部归并时间线性增长甚至可能得不偿失。要让增大 k 变得真正有利可图必须将每次“挑选最小值”的代价从 O(k) 降至 O(log k)。败者树就是为此而生的一种精巧数据结构。3.2 败者树的原理败者树可以被理解为一场淘汰赛的记分牌。它是一棵完全二叉树其中叶子结点对应 k 个归并段中各自待比较的当前记录或者记录的关键码。叶子结点存放的是“参赛者”自身。非叶结点存放的是其左右子树比赛中的“败者”即较大者的索引而“胜者”较小者则继续向上一层参与比较直到最终根结点产生全局最小者。与新元素“比赛”时不必重新进行全部比较只需让新元素沿着原来胜者走过路径与那些记录的“败者”重新比赛即可。调整过程仅涉及树高log₂k次比较。考虑一个具体例子假设有 5 个归并段叶结点为 b0, b1, b2, b3, b4当前待比较的关键字分别为 10, 9, 20, 6, 12。构建败者树时b3(6) 与 b4(12) 比较b4 为败者将其段号 4 写入父结点ls[4]胜者 b3 上升。b1(9) 与 b2(20) 比较b2 为败者将其段号 2 写入父结点ls[3]胜者 b1 上升。胜者 b3(6) 与 b0(10) 比较b0 为败者将段号 0 写入父结点ls[2]胜者 b3 继续上升。左右子树的胜者 b3(6) 与 b1(9) 比较b1 为败者将段号 1 写入父结点ls[1]。确定全局冠军将最终胜者 b3 的段号 3 写入根节点ls[0]表明当前最小关键字来自第 3 段。输出 b3 中的冠军关键字 6 后从第 3 段读入下一个关键字如 15并更新 b3随后沿路径向上重新调整败者树。此时新元素只需与沿途原有的败者依次为 b4、b0、b1重新比赛并更新结点即可快速确定新的全局最小调整过程仅需极少的比较次数。3.3 性能提升使用败者树后每选取一个最小记录并进行调整只需要 O(log k) 次比较与内部归并过程中的记录总数 n 相乘总的内部归并时间复杂度为 O(n log k)。外部归并的时间开销则主要是每趟涉及的 I/O。由于 k 可以增大到数百甚至上千从而让归并趟数 S 急剧减小这通常是完全值得的。现代大规模外部排序中k 的选择主要受到操作系统允许同时打开的文件数以及内存用于缓冲区的总量限制而不太受比较开销的制约。四、 置换-选择排序 (Replacement-Selection Sort)4.1 减少初始归并段数量的痛点传统方法中每个初始归并段的大小就等于内存工作区的容量 W可容纳的记录数。若文件总记录数为 n则初始段数 m ⌈n/W⌉。如果想进一步减小 m就必须打破“一段的大小不能超过内存容量”的限制。置换-选择排序可在同样的 W 大小内存中产生平均长度约为 2W 的归并段有时甚至更长从而使 m 大幅减小。4.2 算法执行过程置换-选择排序利用一个内存工作区通常采用最小堆来管理动态地“一边输出、一边输入”像一条流水线不断生产当前归并段的记录。核心规则如下从磁盘读取 W 个记录填满内存工作区。从工作区中选出关键字最小的记录输出到当前归并段文件。从输入文件再读入一个记录填充空出的位置。如果新读入的记录关键字小于刚刚输出的记录关键字则它不能放在当前归并段中否则会破坏顺序将其“冻结”标记暂时不参与最小值的竞争等到当前归并段结束时再解冻参与下一段。重复步骤 2~4直到工作区中所有记录都被冻结当前归并段结束。此时解冻所有冻结的记录开启一个新的归并段继续这个过程。利用最小堆可以高效地实现冻结与解冻操作将冻结的记录视为具有无穷大关键字或通过一个阈值标记直到当前段产出完毕。考虑一个具体例子设待排文件输入流为FI {17, 21, 05, 44, 10, 12, 56, 32, 29}内存工作区WA的容量为 3。执行过程如下初始化从 FI 读入 3 个记录填满工作区此时WA {17, 21, 05}。生成第一个归并段选出最小记录05输出。从 FI 读入 44 补充WA {17, 21, 44}。选出 WA 中不小于 05 的最小记录17输出。从 FI 读入 10 补充。因为 10 17破坏了递增顺序所以将 10“冻结”WA {10(冻结), 21, 44}。选出未被冻结的最小记录21输出。从 FI 读入 12 补充。因为 12 2112 被冻结WA {10(冻), 12(冻), 44}。选出仅剩的未冻结记录44输出。从 FI 读入 56 补充。因为 56 ≥ 44正常加入竞争WA {10(冻), 12(冻), 56}。输出未冻结记录56。从 FI 读入 32 补充。因为 32 5632 被冻结此时 WA 中的元素{10, 12, 32}已经全部被冻结。段 1 结束输出序列为{05, 17, 21, 44, 56}段长度达到了 5成功突破了内存容量 3 的限制。生成第二个归并段解除 WA 中所有元素的冻结状态开始新一段的生成此时WA {10, 12, 32}。输出10从 FI 读入最后剩下的 29WA {29, 12, 32}。依次选出最小记录并输出输出12FI 已空无新元素补入输出29输出32。段 2 结束输出序列为{10, 12, 29, 32}。置换-选择排序产生的初始归并段长度不是固定的而是呈现“参差不齐”的特征。这恰恰引出了下一个问题如何组织这些长度不一的归并段的归并顺序使得总 I/O 代价最小。五、 最佳归并树 (Optimal Merge Tree)5.1 痛点与哈夫曼树的引入在置换-选择排序之后磁盘上存在 m 个长度各不相同的初始归并段。如果机械地按顺序两两归并会出现某些长段被反复读写多次的情况白白增加 I/O。这类似于构建最优编码树的思想——哈夫曼树。将每个归并段的长度占用的磁盘块数视为带权叶子归并过程可以表示为一棵 k 叉树。其中叶子代表初始归并段内部结点代表一次归并操作。从根到叶子的路径长度乘以叶子权值累加起来就是该归并方案总的磁盘读写块数带权路径长度 WPL。要使总 I/O 最小只需构造一棵以归并段长度为权值的哈夫曼树k 叉哈夫曼树。考虑一个 3 路归并的具体例子假设经过置换-选择排序后得到 9 个初始归并段长度占用的磁盘块数依次为9, 30, 12, 18, 3, 17, 2, 6, 24。普通 3 路平衡归并若直接按顺序每 3 个归并例如先归并 9,30,12再归并 18,3,17 等得到的归并树带权路径长度 WPL 为 242总 I/O 次数读写各一次即 2 × WPL为484。最佳归并树3 叉哈夫曼树将段长作为权值每次挑选权值最小的 3 个结点进行合并选出最小的 2, 3, 6 合并为新段 11。在剩余段{9, 11, 12, 17, 18, 24, 30}中选出 9, 11, 12 合并为新段 32。选出 17, 18, 24 合并为新段 59。最后将剩余的 30, 32, 59 合并为根结点 121。按照此最佳方案长段如 30离根节点更近参与归并的趟数更少。计算得出此时总 I/O 次数降为446显著减少了读写开销。5.2 补充“虚段”构建 k 叉哈夫曼树时存在一个严格的约束条件对于 k 路归并若初始归并段数目 m 不满足(m - 1) % (k - 1) 0则最后一轮归并将不足 k 个段导致生成的哈夫曼树不是“满 k 叉树”可能将权值大的结点推向较深的位置破坏最优性。解决方法十分精妙添加长度为 0 的虚段。虚段不占用任何磁盘块但填充了哈夫曼树的空缺确保每次归并都恰好是 k 个段合并。添加虚段的数目为( ( k − 1 ) − ( ( m − 1 ) m o d ( k − 1 ) ) ) m o d ( k − 1 ) ((k - 1) - ((m - 1) \bmod (k - 1))) \bmod (k - 1)((k−1)−((m−1)mod(k−1)))mod(k−1)加上虚段后再按哈夫曼算法逐步合并权值最小的 k 个结点生成的归并树即为真正的最佳归并树。此时最长的那些初始归并段一定会离根结点最近从而以最少的 I/O 次数完成全局排序。考虑同样是 3 路k 3 k3k3归并但如果只有8个初始归并段假设删去上述例子中长度为 30 的段长度为{2, 3, 6, 9, 12, 17, 18, 24}。判定并计算虚段数设初始段数为n 0 8 n_08n0​8。根据公式计算余数( n 0 − 1 ) % ( k − 1 ) ( 8 − 1 ) % 2 1 (n_0 - 1) \% (k - 1) (8 - 1) \% 2 1(n0​−1)%(k−1)(8−1)%21。因为余数不为 0说明不能构成严格的 3 叉树。需要补充的虚段数为( k − 1 ) − 余数 2 − 1 1 (k - 1) - 余数 2 - 1 1(k−1)−余数2−11个。构建带虚段的最佳归并树加入 1 个长度为 0 的虚段后参与构建哈夫曼树的叶子结点变为{0, 2, 3, 6, 9, 12, 17, 18, 24}。首先选出最小的 0, 2, 3 合并为 5由于虚段长度为 0它一定会和其他长度最短的段一起被安排在树的最深处。接着选出 5, 6, 9 合并为 20。选出 12, 17, 18 合并为 47。最后将剩余的 20, 24, 47 合并为根结点 91。通过引入虚段填充空缺保证了每次归并都能处理 3 个段避免了让长度较大的段过早参与归并从而构造出真正的最佳归并树。六、 总结外部排序是计算机科学中“因地制宜”设计算法的典范将磁盘 I/O 的制约转化为可控的成本基础框架排序-归并策略定义了分块内部排序与多趟归并的骨架。归并优化败者树让多路归并的内部比较开销降至对数级解除了 k 增大的后顾之忧。段生成优化置换-选择排序突破了内存大小对归并段长度的限制让初始归并段数 m 显著下降。归并顺序优化最佳归并树利用哈夫曼思想为长度不一的归并段定制了读写次数最少的合并路径。在大数据时代这些思想早已渗透进 MapReduce 框架的 Shuffle 与 Sort 阶段分布式外部排序、Teradata 等数据库系统的排序实现无一不是这些经典算法的扩展与变形。