外部排序的基本问题

外部排序用于处理无法一次全部装入内存的大文件。和内部排序不同，外部排序的主要瓶颈不是 CPU 比较，而是磁盘 I/O。

外部排序时间通常分为三部分：

$$
\text{外部排序时间}
=\text{读写外存时间}+\text{内部排序时间}+\text{内部归并时间}
$$

其中最重要的是读写外存时间。磁盘是慢速设备，并且通常按块读写：要修改外存中的某个记录，必须先把所在块读入内存，在内存中处理，再把块写回外存。

核心概念

概念 含义
磁盘块 外存读写的基本单位
缓冲区 内存中暂存磁盘块内容的区域
输入缓冲区 从某个归并段读入一块数据
输出缓冲区 暂存归并结果，满了再写回外存
初始归并段 第一阶段生成的若干有序子文件
归并趟数 从初始归并段到最终有序文件需要进行几轮归并

外部归并排序过程

外部排序常用归并思想。整体过程分两阶段：

  1. 生成初始归并段：每次读入内存能容纳的一批记录，在内存中用内部排序排好，再写回外存，形成一个有序归并段。
  2. 逐趟归并：每趟把若干个归并段合并为更长的归并段，直到只剩一个有序文件。

若文件共有 $B$ 个磁盘块，生成初始归并段要把所有块读入一次、写出一次，所以 I/O 次数是：

$$
2B
$$

之后每一趟归并也要把所有块读入一次、写出一次，所以每趟归并的 I/O 次数仍是：

$$
2B
$$

如果归并趟数为 $S$，则总磁盘 I/O 次数为：

$$
2B(S+1)
$$

其中 $+1$ 表示生成初始归并段这一阶段。

二路归并的缓冲区

二路外部归并至少需要三个缓冲区：

  • 归并段 1 的输入缓冲区；
  • 归并段 2 的输入缓冲区；
  • 输出缓冲区。

归并时只比较两个输入缓冲区当前最小记录，把较小者送入输出缓冲区。

情况 处理
某个输入缓冲区空 立即从对应归并段读入下一块
输出缓冲区满 立即写回外存
某个归并段已经读完 继续输出另一个归并段剩余记录

归并趟数

若有 $r$ 个初始归并段，采用 $k$ 路归并，则归并趟数为：

$$
S=\lceil \log_k r\rceil
$$

例如有 $8$ 个初始归并段：

归并方式 归并趟数
二路归并 $\lceil\log_2 8\rceil=3$
四路归并 $\lceil\log_4 8\rceil=2$

所以减少磁盘 I/O 的两个方向是：

  • 增大归并路数 $k$，减少归并趟数；
  • 增大初始归并段长度，减少初始归并段数量 $r$。

这两个方向分别对应多路归并与败者树和置换-选择排序。

小结

考点 记法
外部排序瓶颈 磁盘 I/O
基本方法 先生成初始归并段，再多趟归并
二路归并最少缓冲区 两个输入缓冲区 + 一个输出缓冲区
归并趟数 $S=\lceil \log_k r\rceil$
总 I/O 次数 $2B(S+1)$
优化方向 增大 $k$，减小 $r$