教案 23外部排序External Sorting · 工程级一、问题模型必须精确定义给定一个包含 (N) 条记录的数据集单条记录大小为 ® 字节主存RAM可用容量为 (M) 字节磁盘以**块block**为单位读写每块大小为 (B) 字节。目标对全部数据按某键排序。约束[N⋅R≫M][ N \cdot R \gg M ][N⋅R≫M]即数据无法一次性装入内存。二、评价指标I/O 复杂度外部排序的瓶颈不是 CPU而是磁盘 I/O 次数。标准度量为[I/O cost读块数写块数][ \text{I/O cost} \text{读块数} \text{写块数} ][I/O cost读块数写块数]我们以“扫描全数据一次”的 I/O 代价为基准[Θ!(NRB)][ \Theta!\left(\frac{N R}{B}\right) ][Θ!(BNR​)]三、两阶段多路归并TPMMS外部排序的标准算法是Two-Phase Multiway Merge Sort (TPMMS)Phase 1生成初始有序段runs每次读入至多 (M) 字节约 (M/R) 条记录在内存中排序任意内部排序算法写回磁盘形成一个有序段run得到有序段数量[r≈⌈NRM⌉][ r \approx \left\lceil \frac{N R}{M} \right\rceil ][r≈⌈MNR​⌉]Phase 2多路归并k-way merge同时打开 (k) 个有序段为每个段分配一个输入缓冲区为输出分配一个输出缓冲区使用最小堆优先队列维护当前各段的最小元素反复输出最小元素直到完成四、关键参数归并路数 (k)设每个缓冲区大小为 (B)需要(k) 个输入缓冲1 个输出缓冲内存约束[(k1)⋅B≤M⇒k≤⌊MB⌋−1][ (k 1) \cdot B \le M \Rightarrow k \le \left\lfloor \frac{M}{B} \right\rfloor - 1 ][(k1)⋅B≤M⇒k≤⌊BM​⌋−1]五、归并轮数passes若一次不能归并完即 (r k)需多轮归并。归并轮数约为[⌈log⁡kr⌉][ \left\lceil \log_k r \right\rceil ][⌈logk​r⌉]六、总 I/O 复杂度Phase 1读一遍 写一遍[2⋅Θ!(NRB)][ 2 \cdot \Theta!\left(\frac{N R}{B}\right) ][2⋅Θ!(BNR​)]Phase 2每一轮归并读写一遍总计[Θ!(NRB)⋅(1⌈log⁡kr⌉)⋅2][ \Theta!\left(\frac{N R}{B}\right) \cdot \left(1 \left\lceil \log_k r \right\rceil \right) \cdot 2 ][Θ!(BNR​)⋅(1⌈logk​r⌉)⋅2]简化表达忽略常数[O!(NBlog⁡MBNM)][ O!\left(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{M}\right) ][O!(BN​logBM​​MN​)]这就是外部排序的经典 I/O 复杂度。七、Phase 1 优化替换选择Replacement Selection目标让初始有序段更长减少 ®。方法使用最小堆维护当前可输出元素新读入元素若 (\ge) 上一次输出则继续当前 run否则标记为“下一 run”结果在随机输入下平均 run 长度约为[≈2M][ \approx 2M ][≈2M]于是[r≈NR2M][ r \approx \frac{N R}{2M} ][r≈2MNR​] 直接减少一半的段数从而减少归并轮数。八、归并实现细节可落地1. 缓冲区设计每个输入 run 分配 1 个 block 缓冲输出 1 个 block 缓冲I/O 采用顺序读写避免随机 I/O2. 数据结构最小堆大小为 (k)每个堆元素记录当前值 来源 run 的标识3. 流程各 run 读入首块到输入缓冲将各缓冲的首元素入堆反复弹出最小值写入输出缓冲从对应 run 的缓冲取下一个元素入堆若该缓冲耗尽则读入该 run 的下一块九、工程优化要点1. 增大 (k)[k↑⇒归并轮数↓][ k \uparrow \Rightarrow \text{归并轮数} \downarrow ][k↑⇒归并轮数↓]但受限于 (M/B)。2. 顺序 I/O避免随机读写性能数量级差异文件按 run 连续存储3. 压缩 / 列式存储场景相关减少 ®从而减少 I/O 量。4. 并行化多磁盘并行读写MapReduce / SparkMap生成局部有序段Shuffle按 key 分区Reduce分区内归并十、与内存排序的本质差异维度内存排序外部排序资源瓶颈CPUI/O访问模式随机访问顺序访问优先优化目标比较次数I/O 次数十一、适用场景TB / PB 级日志排序数据仓库ETL 排序阶段数据库 ORDER BY / GROUP BY大规模去重结合外部排序 归并去重十二、结论性表述外部排序通过将数据划分为可内存处理的有序段并以多路归并的方式逐步合并在受限内存条件下以最小化 I/O 次数为目标完成全局排序其性能由块大小、内存容量与归并路数共同决定。