外部排序（External Sort）详解

外部排序是专门针对数据量超过内存容量的场景设计的排序算法，核心思想是：将无法一次性载入内存的海量数据，拆分为多个能载入内存的小数据块，分别在内存中排序（称为生成归并段），再通过多轮归并操作，将有序的归并段合并为最终的有序数据。

外部排序的核心依赖归并排序的分治思想，区别在于：归并排序是内存内的排序，而外部排序需要频繁与外存（磁盘、SSD等）进行IO交互，因此减少IO次数是外部排序优化的核心目标。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

核心特点

• 适用场景：数据量远大于内存容量（如TB级日志、数据库表、大数据文件）
• 核心操作：划分归并段 + 多轮归并
• 性能瓶颈：外存IO速度（远慢于内存操作）
• 常用算法：多路归并排序（k-way Merge Sort）

---

算法原理（经典多路归并流程）

外部排序分为 两个核心阶段：生成初始归并段 和 多轮归并排序。
假设内存容量为 M，待排序数据总大小为 N（N >> M）。

1. 阶段1：生成初始归并段（Run Generation）

• 步骤1：将外存中的海量数据，按内存容量 M 划分为多个数据块，每个数据块大小 ≤ M。
• 步骤2：依次将每个数据块载入内存，用内存排序算法（如快速排序、堆排序）排序，生成有序归并段（Run），写入外存。
• 结果：外存中生成 k = ⌈N/M⌉ 个有序归并段。

示例：

• 内存容量 M=2，待排序数据 [9,3,7,1,8,2,5,4]（大小 N=8）。
• 划分4个数据块：[9,3]、[7,1]、[8,2]、[5,4]。
• 内存排序后生成4个有序归并段：[3,9]、[1,7]、[2,8]、[4,5]。

2. 阶段2：多轮归并排序（k-way Merge）

将多个有序归并段合并为一个有序大文件，分为 多路归并 和 多轮归并 两层逻辑：

• 多路归并：每次从 k 个归并段中各取一个元素，用败者树/堆找到最小值，写入结果归并段，重复直到所有归并段遍历完毕。
• 多轮归并：若归并段数量过多，无法一次合并，则分多轮进行（每轮合并生成更大的有序归并段），直到最终合并为1个有序归并段。

核心优化：败者树（Loser Tree）
多路归并的性能瓶颈是“找最小值”，若用普通比较需 k-1 次比较，用败者树可将比较次数降至 log₂k，大幅减少内存操作次数。

---

代码实现（模拟多路归并，Python）

以下代码模拟外部排序的核心流程（忽略真实外存IO，用列表模拟归并段）：

import heapq

def external_sort(data, memory_size):
    """
    模拟外部排序
    :param data: 待排序的海量数据（列表）
    :param memory_size: 内存容量（每次最多排序memory_size个元素）
    :return: 排序后的结果
    """
    # ========== 阶段1：生成初始归并段 ==========
    runs = []
    n = len(data)
    # 划分数据块，生成有序归并段
    for i in range(0, n, memory_size):
        # 取一个数据块（大小≤memory_size）
        block = data[i:i+memory_size]
        # 内存排序（用快速排序）
        block.sort()
        # 加入归并段列表
        runs.append(block)
    
    # ========== 阶段2：多路归并 ==========
    # 用优先队列（小顶堆）实现多路归并
    # 堆中元素格式：(当前元素值, 归并段索引, 元素在归并段中的索引)
    heap = []
    for run_idx, run in enumerate(runs):
        if run:
            # 每个归并段取第一个元素入堆
            heapq.heappush(heap, (run[0], run_idx, 0))
    
    sorted_result = []
    while heap:
        # 取出堆顶（最小值）
        val, run_idx, elem_idx = heapq.heappop(heap)
        sorted_result.append(val)
        # 取下一个元素入堆（若归并段未遍历完）
        next_elem_idx = elem_idx + 1
        if next_elem_idx < len(runs[run_idx]):
            next_val = runs[run_idx][next_elem_idx]
            heapq.heappush(heap, (next_val, run_idx, next_elem_idx))
    
    return sorted_result

# 测试示例
if __name__ == "__main__":
    # 待排序数据（模拟海量数据）
    large_data = [9, 3, 7, 1, 8, 2, 5, 4, 10, 6, 12, 11]
    # 内存容量：每次最多排序3个元素
    memory_size = 3
    sorted_data = external_sort(large_data, memory_size)
    print("原始数据：", large_data)
    print("排序后数据：", sorted_data)
    # 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

---

关键优化策略

外部排序的性能优化围绕 减少外存IO次数 和 提高归并效率 展开，核心优化点如下：

1. 增大归并路数 k

• 归并路数 k 越大，归并轮数越少，IO次数越少。
• 限制 k 的因素：内存容量（需缓存 k 个归并段的当前元素）、CPU计算能力（败者树的比较开销）。
• 工业界常用 k=1024 或更高的路数。

2. 败者树替代小顶堆

• 小顶堆的调整时间复杂度为 O(log k)，败者树在初始化后，每次调整的时间复杂度更优（适合高路数归并）。
• 败者树的核心思想：记录每轮比较的“败者”，减少下一轮的重复比较。

3. 生成更长的初始归并段

• 置换选择排序（Replacement Selection Sort）：生成初始归并段时，利用内存中的“优先队列”，生成长度远超内存容量的归并段（平均长度为 2M），减少归并段数量。
• 优势：归并段数量减少 → 归并轮数减少 → IO次数大幅降低。

4. 磁盘IO优化

• 顺序IO优先：磁盘的顺序读写速度远高于随机读写，因此归并段的读写需尽量采用顺序IO。
• 分块存储：将归并段存储在不同的磁盘分区，利用多磁盘并行IO，提高读写速度。

---

与内部排序的核心对比

特性	外部排序	内部排序（如快速/归并）
数据规模	远超内存容量（TB/PB级）	可完全载入内存（GB级）
存储介质	外存（磁盘/SSD）为主	内存为主
性能瓶颈	外存IO速度	CPU计算速度
核心算法	多路归并+置换选择排序	快速/归并/堆排序
优化目标	减少IO次数	减少比较/交换次数

---

适用场景

• 大数据排序：如TB级日志文件、数据库全表排序、数据仓库ETL流程。
• 分布式排序：如MapReduce的Shuffle阶段、Spark的SortBy操作（本质是分布式外部排序）。
• 磁盘受限场景：数据量超过内存，但需有序输出的场景（如报表生成、数据导出）。

不适用场景：

• 数据量可完全载入内存的场景（内部排序效率更高）；
• 对实时性要求极高的场景（外部排序IO开销大，延迟较高）。

---

拓展：分布式外部排序（MapReduce示例）

在分布式系统中，外部排序被扩展为分布式排序，以MapReduce为例：

1. Map阶段：将数据分片，每个Map任务对分片数据进行内存排序，生成有序归并段。
2. Shuffle阶段：将Map输出的有序归并段，按Key的范围分发到不同的Reduce节点。
3. Reduce阶段：每个Reduce节点对收到的多个有序归并段执行多路归并，生成最终的有序结果。

这一流程是大数据平台（Hadoop/Spark）实现海量数据排序的核心。