外部排序与多路归并磁盘IO优化

可视化演示

外部排序用于处理无法全部装入内存的海量数据，通过多路归并和败者树优化磁盘I/O。本文讲解外部排序的基本流程与初... 切换模式查看不同维度。

外部排序概述

你站在巨大的仓库中央，望着满坑满谷的编号箱子，再看看手里那张小小的工作台——一次只能摆下几十个箱子。聪明的你很快想通：既然一口气理不完，那就分批理。先把一角仓库的箱子搬到工作台上排好序，放回原位；再搬下一角……等到每个角落的箱子都各自有序后，再考虑怎么把这些“小有序”合并成“大有序”。至于每一角落搬多少趟、怎么合并最省力气，就是外部排序要回答的问题。

把这个画面搬进计算机：磁盘是那个大仓库，内存是工作台。当待排序数据总量 N 远超内存容量 M 时，快速排序、堆排序这类内部排序算法全部失灵——它们的前提是数据能同时驻留内存。外部排序采用两阶段策略：第一阶段“生成初始归并段”，分块读入数据、段内排序、写回磁盘；第二阶段“多路归并”，把若干有序段逐层合并，直到只剩一段。

两阶段中，磁盘与内存之间的数据搬运量是决定性能的关键。磁盘随机访问比顺序访问慢几个数量级，而内存读写比磁盘快几个数量级，所以外部排序的一切优化都围绕“减少搬运次数、让搬运更有序”。假设初始归并段数为 m，多路归并路数为 k，归并趟数约等于 log 以 k 为底 m 的对数，那么总搬运量可近似表示为：

回到仓库的比喻：如果你把仓库分成 10 个小堆，每次把 2 个小堆合并成 1 个有序大堆，大约需要 4 趟才能把 10 堆合成 1 堆。每趟你都要把所有箱子从仓库搬到工作台再搬回去，这就是"2N"的含义。理解了搬运量，你就抓住了外部排序的命脉。

初始归并段

整理仓库的第一步，是先把仓库划分成几个区块。你画好格子线，每个格子的大小正好等于工作台的容量，把每个格子里的箱子搬到工作台上排好序、放回原处。这样，仓库里就出现了若干堆内部有序的“小堆”，每堆大小约等于工作台容量。这些有序小堆，在外部排序中叫做“初始归并段”。

初始归并段生成的关键是等长划分：以内存容量 M 为一把“标准尺”，把输入数据流切成若干长度为 M 的块。对每个块，读入内存后用快速排序或堆排序排好，再整块写回磁盘。一个块对应一个归并段文件。段与段之间互不重叠、各自有序，这正是后续归并的前提——就像你必须先保证每个小堆内部有序，才能谈得上把多个小堆合并成一个大堆。

归并段的数量直接决定后续工作量。设数据总量为 N、内存容量为 M，则段数：

等长划分简单粗暴但有一个缺点：段的数量被内存容量“锁死”。如果内存只有 1GB 而数据有 100GB，就会产生约 100 个归并段，后续归并时要来回搬运很多趟。后文介绍的替换选择算法，正是为了打破这个“每段长度=M”的紧箍咒。

多路归并

仓库里已经有十几堆各自有序的箱子，现在要把它们合并成一堆完全有序的箱子。你可以两堆两堆地合，但那样要来回跑很多趟。更聪明的做法是：同时摊开 k 堆箱子，每堆顶部露出最小的那个编号，比较这 k 个编号，取出最小者放到新堆中；然后从它所属的那堆再露出下一个编号，继续比较……这就是“k 路归并”，你也因此理解为什么打扑克牌时大家喜欢把牌按大小排好再一张张比。

k 路归并中，每输出一个元素，都要从 k 个队头中选出最小值。用最朴素的方法——扫描全部 k 个队头——每选一次要比较 k−1 次。数据总量为 N，一趟归并总共要输出 N 个元素，所以一趟的比较次数为 (k−1)×N。而归并的趟数取决于初始归并段数 m 和路数 k：

想象你是扑克裁判，要同时盯 100 堆牌、每轮从 100 个顶牌中找最小——用“肉眼扫描”当然费劲，这正是多路归并的第一重代价。如果路数少，扫起来轻松但趟数多、搬运多；路数多，趟数少了但每轮比较累。要摆脱这个两难，就需要一个“自动选出最小牌”的记分牌：败者树。

败者树优化

多路归并的每一轮，就像一场小型淘汰赛：k 个队头选手同台比大小，胜出者是最小值。朴素扫描相当于每轮重新把所有选手叫上台比一遍。有没有办法让上一轮的比赛信息保留下来，下一轮只让新上场的选手和“历届输家”比？有——这就是败者树。

败者树是一棵完全二叉树，叶子节点对应 k 个归并段的队头，内部节点记录“败者”（比较中较大的那个值）来自哪一路，根节点则记录整场比赛的“冠军”（最小值）来自哪一路。当某一路的最小值被输出后，新元素顶替它的叶子位置，只需沿着从该叶子到根的一条路径，与沿途记录的历史败者逐一比较——每层比较一次，重复的比较被彻底避免。

淘汰赛的妙处在于：老选手之间的胜负关系已经记录在内部节点里，新选手只需要一路“过关斩将”挑战历史败者。每轮选出最小值的时间从不超 O(k) 降为树高：

对比朴素的“每轮全量扫描”，败者树就像考场里保留了一份历次考试的排名表：新同学来挑战，不必和所有人重新比，只要沿着排名依次挑战即可。归并段路数越大、数据量越大，这份“排名表”省下的力气就越可观。

替换选择算法

等长划分生成的归并段，长度被内存容量 M 死死锁住。可你有没有想过：如果整理箱子时，一边整理一边从仓库门口源源不断地补货，是不是能让每个有序小堆比工作台容量更大？这正是替换选择算法的核心思想——它把生成归并段从“分批静态整理”变成“流水线动态整理”。

算法维护一个能容纳 M 个元素的内存工作区。初始时从输入读入 M 个元素；接着反复执行：从工作区中选出一个“大于当前段末尾且最小”的元素，输出到当前归并段；每输出一个元素，立即从输入读入一个新元素补进工作区。如果工作区里所有元素都小于当前段末尾，说明当前段“到头了”，开启一个新的归并段，从头再来。

为什么这样能生成超长归并段？因为只要新补进来的元素恰好比当前段尾大，就能继续“接龙”。对于均匀随机数据，新元素有大约 1/2 的概率比已输出的最大值还大，所以顺串可以不断延续。数学期望上，随机输入下替换选择生成的归并段长度为：

替换选择的最大价值在于：它没有增加任何内存，却让归并段数量几乎减半，归并趟数随之降低。这就像聪明的仓库管理员在传达带旁安排了一个“预备区”——整理到一半时，新来的箱子如果编号够大，就直接排进当前这堆，大大延长了每次整理的成果。

磁盘IO优化

搬运是外部排序最昂贵的开销。同样搬 100 个箱子，用小车一次推 20 个，比一次抱 2 个来回跑 50 趟省力得多。磁盘 I/O 优化的第一原则就是把“小碎步”变成“大跨步”：以大的数据块为单位批量读写，避免频繁的小块随机访问。一次读 1MB 比读 100 次 10KB 要快得多，因为磁盘顺序读有很高的带宽利用率。

第二板斧是缓冲区管理。归并时，每个输入归并段都要在内存里有自己的缓冲区，专门存放从磁盘预读的一段数据。当缓冲区的数据被消费完，再触发下一次磁盘读。缓冲区太小，磁盘会被频繁“唤醒”；缓冲区太多，又会挤占内存。工程上常用“双缓冲”技巧：为每个输入段准备两个缓冲区，归并进程处理 A 缓冲区时，磁盘异步向 B 缓冲区填充下一批数据——计算与 I/O 重叠进行，磁盘延迟被彻底隐藏。

从 I/O 总量看，优化前后的对比非常直观。设每趟归并读写各 N 个元素，归并趟数为 S：

回到仓库场景：聪明的管理员会先规划好搬运路线，用大推车一次性多装些，还会在门口设两个暂存台——一个台上正在整理，另一个台已经被传送带悄然填满。整理想法与磁盘读写的交错重叠，就是双缓冲的精髓。

并行归并策略

一个人整理整个大仓库太慢了，为什么不叫几个帮手分头行动？并行归并的核心思路同样是“人多力量大”，但难点在于如何分工、如何汇总。常见的并行策略有两种：多磁盘并行——把不同归并段分散到多块磁盘上，让 I/O 请求可以同时在不同磁盘上执行；多线程归并——把归并任务拆成多个子任务，每个线程负责一组归并段的合并，最后再做一次总的归并。

并行不是没有代价的。多个线程同时读写磁盘，会产生 I/O 竞争；多个线程同时占用内存带宽，也会互相干扰。此外，如果各归并子任务的数据量严重不均，有的线程忙死、有的线程空闲，总耗时反而被“短板”拖累。所以负载均衡是并行归并的必修课——尽量让每个归并任务的数据量、I/O 量大致相当。

并行加速比遵循阿姆达尔定律。设可并行部分的占比为 f，并行度为 p，则理论上限：

请一堆帮手看似简单，但帮手越多，碰头商量（串行汇总）的时间也越长。聪明的仓库主管会让每个帮手各管一块区域、互不干扰，最后只做一次汇总——这正是并行归并追求的理想状态。

应用与性能

外部排序在海量数据场景无处不在。数据库执行 ORDER BY 时，如果待排序数据超过内存的 sort buffer，就会自动切换到外部排序；MapReduce 的 Shuffle 阶段，Map 端输出的中间结果按 key 分区排序后落盘，Reduce 端拉取后也要做归并排序——外部排序是分布式框架的“隐形基建”；Linux 下对大文本文件执行 sort，底层同样是外部排序的教科书式实现。

从各项指标回看整个过程：初始归并段的生成需要一次全量读取和一次全量写回；每趟归并又各读写一次；多路归并与败者树负责压低比较成本；替换选择负责减少段数；双缓冲和并行负责让 I/O 与计算重叠。综合来看，外部排序处于两股力量的拉扯之中：一边是磁盘搬运，一边是内存比较。

最终的整体性能可以概括为：

仓库整理的大工程终于收尾：比较就像整理动作，败者树让每个动作更利落；I/O 就像搬运，趟数决定要跑多少趟。真正的大数据工程师，既懂得把整理动作做得干脆（算法优化），更懂得把搬运路线规划得经济（I/O 优化）——两者齐头并进，才是外部排序的至高心法。

---

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-# 外部排序演示: 分块排序(生成初始归并段) + 堆式k路归并import osimport randomimport tempfileimport heapq  def generate_data(path, count):    # 生成count个随机整数写入文件, 每行一个    with open(path, 'w') as f:        for _ in range(count):            f.write(str(random.randint(0, 1000000)) + '\n')  def create_runs(input_path, mem_size, run_dir):    # 阶段1: 分块读入内存排序, 写出为多个归并段文件    runs = []    with open(input_path, 'r') as f:        block = []        for line in f:            block.append(int(line))            if len(block) >= mem_size:                block.sort()                run_path = os.path.join(run_dir, 'run_%d.txt' % len(runs))                with open(run_path, 'w') as rf:                    rf.write('\n'.join(map(str, block)) + '\n')                runs.append(run_path)                block = []        if block:            block.sort()            run_path = os.path.join(run_dir, 'run_%d.txt' % len(runs))            with open(run_path, 'w') as rf:                rf.write('\n'.join(map(str, block)) + '\n')            runs.append(run_path)    return runs  def merge_runs(run_paths, output_path):    # 阶段2: 使用最小堆做全部路数的一次归并    heap = []    readers = []    for rid, rp in enumerate(run_paths):        rd = open(rp, 'r')        readers.append(rd)        first = rd.readline()        if first:            heapq.heappush(heap, (int(first), rid))    with open(output_path, 'w') as out:        while heap:            val, rid = heapq.heappop(heap)            out.write(str(val) + '\n')            nxt = readers[rid].readline()            if nxt:                heapq.heappush(heap, (int(nxt), rid))    for rd in readers:        rd.close()  def verify_sorted(path):    # 校验输出文件是否全局有序    prev = -1    with open(path) as f:        for line in f:            v = int(line)            if v < prev:                return False            prev = v    return True  def main():    work_dir = tempfile.mkdtemp(prefix='ext_sort_')    input_path = os.path.join(work_dir, 'input.txt')    output_path = os.path.join(work_dir, 'output.txt')    run_dir = os.path.join(work_dir, 'runs')    os.makedirs(run_dir)     N = 10000      # 总数据量    M = 1000       # 内存块大小(即初始归并段容量)     generate_data(input_path, N)    runs = create_runs(input_path, M, run_dir)    print('初始归并段数量:', len(runs))    for i, rp in enumerate(runs):        size = sum(1 for _ in open(rp))        print('  段 %d 长度: %d' % (i, size))     merge_runs(runs, output_path)    print('输出全局有序:', verify_sorted(output_path))    print('结果文件大小: %d bytes' % os.path.getsize(output_path))  if __name__ == '__main__':    main()

1. block.sort()每个内存块内的排序，对应内部排序生成有序归并段
2. heapq.heappush(heap, (int(first), rid))最小堆维护各归并段的当前队头，堆顶永远是最小值
3. val, rid = heapq.heappop(heap)弹出全局最小值并记录来自哪一段
4. readers[rid].readline()从刚被取走元素的归并段补读下一个元素进堆
5. runs = create_runs(...)生成初始归并段，段数约等于 N/M，与正文公式对应

常见误区

面试题