12.6. 外部排序¶
12.6.1. 外部排序¶
我们现在考虑对太大而无法放入主存的记录集合进行排序的问题。 由于记录必须驻留在辅助存储器或外部存储器中， 这种排序方法被称为 外部排序。 这与 内部排序（internal sort） 形成对比， 后者假设要排序的记录存储在主存中。 对大量记录集合进行排序对许多应用至关重要， 例如处理工资单和其他大型业务数据库。 因此，已经设计了许多外部排序算法。 多年前，排序算法设计者试图优化 特定硬件配置的使用，例如多个磁带或 磁盘驱动器。 如今的大多数计算都在具有相对强大 CPU 但只有一两个磁盘驱动器的个人计算机和低端工作站上完成。 这里介绍的技术针对单个磁盘驱动器上的优化处理。 这种方法使我们能够涵盖外部排序中最重要的问题， 同时跳过许多不太重要的与机器相关的细节。
当记录集合太大而无法放入 主存 时，唯一的实际排序方法是从磁盘读取一些记录，进行一些重新排列，然后将其写回磁盘。此过程重复直到文件排序完成，每条记录可能被多次读取。鉴于 磁盘 I/O 的高成本，外部排序算法的主要目标是最小化必须从磁盘读取或写入磁盘的信息次数，这应该不足为奇。一定量的额外 CPU 处理可以有利地换取磁盘访问的减少。
在讨论外部排序技术之前，让我们再次考虑从磁盘访问信息的基本模型。待排序的文件被程序员视为一系列固定大小的 块。为简单起见，假设每个块包含相同数量的固定大小数据记录。根据应用程序的不同，记录可能只有几个字节—主要由关键字组成或几乎没有更多内容—或者可能有几百字节，关键字字段相对较小。假设记录不跨越块边界。对于专用排序应用程序可以放宽这些假设，但忽略这些复杂性使原理更清晰。
回忆一下，扇区 是 I/O 的基本单位。 换句话说，所有磁盘读写都是针对一个或多个完整扇区的。 扇区大小通常是 2 的幂，范围在 512 到 16K 字节之间， 取决于操作系统和磁盘驱动器的大小和速度。 外部排序算法使用的块大小应等于或为扇区大小的倍数。
在此模型下，排序算法将数据块读入主存中的缓冲区， 对其进行处理，然后在未来的某个时间将其写回磁盘。 回想一下 从磁盘读取或写入块 比内存访问大约慢一百万倍。 根据这一事实，我们可以合理预期， 单个块中包含的记录可以由内部排序算法 （如 快速排序（Quicksort）） 在读取或写入块所需时间内完成排序。
在良好条件下，按顺序从文件读取比随机读取块更高效。考虑到寻道时间对磁盘访问的显著影响，顺序处理更快似乎是显而易见的。然而，理解顺序文件处理实际上在什么情况下比随机访问更快很重要，因为这影响我们设计外部排序算法的方法。
高效的顺序访问依赖于将寻道时间保持在最低限度。第一个要求是组成文件的块实际上在磁盘上按顺序存储且彼此靠近，最好填充少量连续的磁道。至少，组成文件的区段数量应该很少。用户通常无法控制文件在磁盘上的布局，但一次按顺序写入文件到具有高百分比自由空间的磁盘驱动器会增加这种排列的可能性。
第二个要求是在顺序处理期间磁盘驱动器的 I/O 头保持在文件上方。如果存在对 I/O 头的任何竞争，这将不会发生。例如，在多用户分时计算机上，排序过程可能与其他用户的进程竞争 I/O 头。即使排序过程单独控制 I/O 头，顺序处理仍然不太可能高效。想象一下所有处理都在单个磁盘驱动器上进行的情况，典型安排是一组一起移动的读/写头堆叠在盘片上。如果排序过程涉及从输入文件读取，然后交替写入输出文件，则 I/O 头将在输入文件和输出文件之间不断寻道。类似地，如果同时处理两个输入文件（例如在合并过程中），则 I/O 头将在这些文件之间不断寻道。
结论是，对于单个磁盘驱动器，数据文件的高效顺序处理通常是不存在的。因此，如果排序算法执行较少的非顺序磁盘操作而不是较多的逻辑顺序磁盘操作（实际上需要大量寻道），可能会更高效。
如前所述，与关键字大小相比，记录大小可能相当大。例如，大型企业的工资单条目可能存储数百字节的信息，包括每个员工的姓名、ID、地址和职位。排序关键字可能是 ID 号，只需要几个字节。最简单的排序算法可能是将这些记录作为整体处理，处理时读取整个记录。然而，这将大大增加所需的 I/O 量，因为只有相对较少的记录能放入单个磁盘块中。另一种选择是执行 关键字排序。在此方法下，所有关键字被读取并存储在 索引文件 中，其中每个关键字与一个指针一起存储，该指针指示相应记录在原始数据文件中的位置。关键字和指针的组合应比原始记录的大小小得多；因此，索引文件将比完整数据文件小得多。然后对索引文件进行排序，需要更少的 I/O，因为索引记录比完整记录小。
索引文件排序后，可以重新排列原始数据库文件中的记录。这通常不执行，原因有两个。首先，从记录文件中按排序顺序读取记录需要对每条记录进行随机访问。这可能花费大量时间，只有在需要按排序顺序查看或处理完整记录集合时才有价值（而不是搜索选定的记录）。其次，数据库系统通常允许对多个关键字进行搜索。例如，今天的处理可能按 ID 号顺序进行。明天，老板可能想要按薪水排序的信息。因此，完整记录可能没有单一的"排序"顺序。相反，通常维护多个索引文件，每个排序关键字一个。这些思想在 索引 章中有进一步探讨。
12.6.1.1. 外部排序的简单方法¶
如果你的操作系统支持虚拟内存，最简单的"外部"排序是将整个文件读入虚拟内存并运行快速排序等内部排序方法。这种方法允许虚拟内存管理器使用其正常的缓冲池机制来控制磁盘访问。不幸的是，这可能并非总是可行的选择。一个潜在的缺点是虚拟内存的大小通常限制在比可用磁盘空间小得多的范围内。因此，你的输入文件可能无法放入虚拟内存。有限的虚拟内存可以通过调整内部排序方法来使用自己的缓冲池来克服。
将内部排序算法调整为外部排序的另一个更普遍的问题是它不太可能与专门设计用于最小化磁盘 I/O 的新算法一样高效。考虑快速排序使用缓冲池的简单调整。快速排序首先处理整个记录数组，第一个分区步骤从两端向内移动索引。这可以使用缓冲池高效实现。然而，下一步是处理每个子数组，然后是子子数组，依此类推。随着子数组变小，处理迅速接近对磁盘驱动器的随机访问。即使最大限度地使用缓冲池，快速排序仍然必须平均读取和写入每条记录 \(\log n\) 次。我们可以做得更好。最后，即使虚拟内存管理器可以使用标准快速排序提供良好的性能，这将以使用大量系统工作内存为代价，这意味着系统无法将此空间用于其他工作。更好的方法可以在使用更少内存的同时节省时间。
我们的外部排序方法源自归并排序算法。最简单的外部归并排序形式执行一系列顺序遍历记录，每次遍历合并越来越大的子列表。第一次遍历将大小为 1 的子列表合并为大小为 2 的子列表；第二次遍历将大小为 2 的子列表合并为大小为 4 的子列表；依此类推。已排序的子列表称为一个 初始归并段。因此，每次遍历将一对归并段合并以形成更长的归并段。每次遍历将文件的内容复制到另一个文件。以下是算法的概要。
将原始文件分成两个等大小的 归并段文件。
从每个归并段文件读取一个块到输入缓冲区。
从每个输入缓冲区取出第一条记录， 按排序顺序将长度为 2 的归并段写入输出缓冲区。
从每个输入缓冲区取出下一条记录， 按排序顺序将长度为 2 的归并段写入第二个输出缓冲区。
重复直到完成，在两个输出归并段缓冲区之间交替输出。 每当到达输入块的末尾时，从相应的输入文件读取下一个块。当输出缓冲区满时，将其写入相应的输出文件。
重复步骤 2 到 5，使用原始输出文件作为输入文件。 在第二次遍历中，每个输入归并段文件的前两条记录已经排序。因此，可以将这两个归并段合并并作为单个四元素归并段输出。
每次遍历归并段文件会提供越来越大的归并段， 直到只剩下一个归并段。
此算法可以轻松利用 双缓冲。请注意，各次遍历按顺序读取输入归并段文件并按顺序写入输出归并段文件。但是，要使顺序处理和双缓冲有效，必须为每个文件提供单独的 I/O 头。这通常意味着每个输入和输出文件必须在单独的磁盘驱动器上，总共需要四个磁盘驱动器才能达到最高效率。
12.6.1.2. 提高性能¶
刚才描述的外部归并排序算法需要 \(\log n\) 次遍历来对 \(n\) 条记录的文件进行排序。因此，每条记录必须从磁盘读取和写入磁盘 \(\log n\) 次。通过观察不需要对小归并段使用归并排序，可以显著减少遍历次数。一个简单的修改是读入一个数据块，在内存中排序（可能使用快速排序），然后将其作为单个已排序的归并段输出。
我们可以扩展这个概念以进一步提高性能。可用的主存通常比一个块大得多。如果我们处理更大的初始归并段，则归并排序所需的遍历次数进一步减少。例如，大多数现代计算机可以为排序程序提供数十甚至数百兆字节的 RAM。如果所有这些内存（减去用于缓冲区和局部变量的少量）都用于构建尽可能大的初始归并段，则可以在很少的遍历中处理相当大的文件。下一节介绍一种产生大归并段的技术，通常是能直接放入主存的大小的两倍。
减少所需遍历次数的另一种方法是增加每次遍历中合并的归并段数量。虽然标准归并排序算法一次合并两个归并段，但没有理由将合并限制在此方式。下面我们将讨论多路合并技术。
多年来，已经提出了许多外部排序的变体，但都基于以下两个步骤：
将文件分成大的初始归并段。
将归并段合并在一起形成单个排序文件。
12.6.1.3. 替代选择¶
本节讨论从磁盘文件创建尽可能大的初始归并段的问题，假设固定数量的 RAM 可用于处理。如前所述，简单的方法是将尽可能多的 RAM 分配给大数组，从磁盘填充此数组，然后使用快速排序对数组进行排序。因此，如果可用于数组的内存大小为 \(M\) 条记录，则输入文件可以分成长度为 M 的初始归并段。更好的方法是使用一种叫做 替代选择 的算法，它平均创建 \(2M\) 条记录长度的归并段。替代选择实际上是堆排序算法的轻微变体。堆排序比快速排序慢这一事实在此上下文中无关紧要，因为 I/O 时间将主导任何合理外部排序算法的总运行时间。构建更长的初始归并段将减少所需的总 I/O 时间。
替代选择将 RAM 视为由一个大小为 \(M\) 的数组以及输入缓冲区和输出缓冲区组成。（如果操作系统支持双缓冲，可能需要额外的 I/O 缓冲区，因为替代选择对其输入和输出都进行顺序处理。）想象输入和输出文件是记录流。替代选择在需要时从输入流中按顺序取出下一条记录，并一次一条地将归并段输出到输出流。使用缓冲来执行磁盘 I/O，一次一个块。最初读取一块记录并保存在输入缓冲区中。替代选择一次从输入缓冲区中取出一条记录，直到缓冲区为空。此时读入下一块记录。输出到缓冲区类似：一旦缓冲区满，就作为一个单元写入磁盘。此过程如图 12.6.1 所示。
替代选择的工作原理如下。假设主要处理在大小为 \(M\) 条记录的数组中进行。
从磁盘填充数组。设置
LAST = M-1。构建一个最小堆。 （回想一下，最小堆的定义是每个节点的记录的键值 小于 其子节点的键值。）
重复直到数组为空：
将键值最小的记录（根）发送到输出缓冲区。
令 \(R\) 为输入缓冲区中的下一条记录。如果 \(R\) 的键值大于刚输出的键值……
则将 \(R\) 放在根位置。
否则用数组位置
LAST的记录替换根，并将 \(R\) 放在位置LAST。设置LAST = LAST - 1。
将根向下筛选以重新排列堆。
当步骤 3(b) 的测试成功时，新记录被添加到堆中，最终作为归并段的一部分输出。只要来自输入文件的记录具有大于最后输出到归并段的键值，它们就可以安全地添加到堆中。具有较小键值的记录不能作为当前归并段的一部分输出，因为它们不会按排序顺序排列。这些值必须存储在某处以供将来作为另一个归并段的一部分处理。然而，因为堆在这种情况下将缩小一个元素，所以现在有一个空闲空间，堆的最后一个元素曾经在此！因此，替代选择将慢慢缩小堆，同时使用丢弃的堆空间存储下一条归并段的记录。一旦第一条归并段完成（即堆变空），数组将充满准备为第二条归并段处理的记录。以下是显示通过替代选择创建归并段的可视化。
应该清楚的是，如果堆的大小为 \(M\)，则归并段的最小长度将是 \(M\) 条记录，因为堆中原来就有的那些记录至少会成为归并段的一部分。在良好的条件下（例如，如果输入已排序），则可能产生任意长的归并段。实际上，整个文件可以作为一个归并段处理。如果条件不好（例如，如果输入是反向排序的），则只产生大小为 \(M\) 的归并段。
替代选择产生的归并段的预期长度是多少？可以从一个叫做 雪铲论证 的类比推导出来。想象一辆雪铲在圆形轨道上行驶，正在下大雪但雪势稳定。雪铲至少绕一圈后，轨道上的雪必须如下所述。雪铲正后方的轨道是空的，因为刚被清理过。轨道上积雪最多的地方在雪铲正前方，因为这是最近一次被清理的地方。在任何时刻，轨道上有一定量的雪 \(S\)。整个轨道上不断以稳定速率降雪，一些雪落在雪铲"前面"，一些落在"后面"。（在圆形轨道上，所有东西实际上都在雪铲"前面"，但图说明了这个想法。）在雪铲的下一圈旋转中，轨道上所有的雪 \(S\) 被清除，再加上降下的一半雪。因为一切都处于稳定状态，一圈之后轨道上仍有 \(S\) 的雪，所以一圈期间降下 \(2S\) 的雪，一圈期间清除 \(2S\) 的雪（留下 \(S\) 的雪）。
在替代选择开始时，来自输入文件的几乎所有值都大于（即"在雪铲前面"）此归并段最新输出的键值，因为归并段的初始键值应该较小。随着归并段的进行，最新输出的键值变得更大，因此来自输入文件的新键值更可能太小（即"在雪铲后面"）；这些记录进入数组底部。归并段的总长度预计是数组大小的两倍。当然，这假设传入的键值在键范围内均匀分布（就雪铲类比而言，我们假设雪在整个轨道上均匀降下）。已排序和反向排序的输入不满足此预期，因此会改变归并段的长度。
12.6.2. 多路合并¶
典型外部排序算法的第二阶段合并第一阶段产生的归并段。假设我们有 \(R\) 个归并段要合并。如果使用简单的两路合并，则 \(R\) 个归并段（无论其大小如何）将需要 \(\log R\) 次文件遍历。虽然 \(R\) 应该远小于记录总数（因为初始归并段每个都应包含许多记录），但我们希望进一步减少合并归并段所需的遍历次数。请注意，两路合并没有很好地利用可用内存。因为合并是两个归并段上的顺序过程，每个归并段只需要一个记录块在内存中。在任何时候将归并段的多个块保存在内存中不会减少合并过程所需的磁盘 I/O （尽管如果一次从文件读取多个块，至少它们利用了顺序访问）。因此，刚才用于替代选择的堆（通常有多个块长）的大部分空间没有被合并过程使用。
如果我们一次合并几个归并段，我们可以更好地利用这个空间，同时大大减少合并归并段所需的遍历次数。多路合并类似于两路合并。如果我们有 \(B\) 个归并段要合并，每个归并段有一个块在内存中可用，则 \(B\) 路合并算法只需查看 \(B\) 个值（每个输入归并段的最前面的值）并选择最小的一个输出。该值从其归并段中移除，过程重复。当任何归并段的当前块耗尽时，从该归并段从磁盘读取下一个块。以下幻灯片展示了多路合并。
概念上，多路合并假设每个归并段存储在单独的文件中。然而，实际上这并非必要。我们只需要知道每个归并段在单个文件中的位置，并在需要从特定归并段获取新数据时使用 seek 移动到相应的块。当然，这种方法破坏了对输入文件进行顺序处理的能力。但是，如果所有归并段都存储在单个磁盘驱动器上，则处理本来就不会是真正顺序的，因为 I/O 头将在归并段之间交替。因此，多路合并用单次随机访问遍历替换了多次（可能）顺序遍历。如果处理本来就不会是顺序的（例如所有处理都在单个磁盘驱动器上），这样做不会浪费时间。
多路合并可以大大减少所需的遍历次数。如果内存中有空间为每个归并段存储一个块，则所有归并段可以在一次遍历中合并。因此，替代选择可以在一次遍历中构建初始归并段，多路合并可以在一次遍历中合并所有归并段，总成本为两次遍历。然而，对于真正的大文件，可能有太多归并段以至于每个归并段都无法获得内存中的一个块。如果空间可以分配 \(B\) 个块用于 \(B\) 路合并，且归并段数量 \(R\) 大于 \(B\)，则需要进行多次合并遍历。换句话说，合并前 \(B\) 个归并段，然后是下一个 \(B\) 个，依此类推。这些超级归并段随后由后续遍历合并，一次 \(B\) 个超级归并段。
一次合并可以处理多大的文件？假设为替换选择在堆上分配了 \(B\) 个块（所得游程的平均长度为 \(2B\) 个块），随后进行一次 \(B\) 路合并，那么一次多路合并平均可以处理大小为 (2B^2) 个块的文件。平均而言， \(k\) 次 \(B\) 路合并可以处理 \(2B^{k+1}\) 个块。为了更直观地体会这种增长速度，假设我们有 0.5MB 的工作内存，块大小为 4KB，则工作内存中可容纳 128 个块。游程的平均大小为 1MB（工作内存大小的两倍）。一次合并可以合并 128 个游程。因此，仅需 0.5MB 的工作内存，大小为 128MB 的文件就可以在两趟中处理完（一趟构建游程，一趟完成合并）。再举一个例子，假设块长为 1KB，工作内存为 1MB（ \(=\) 1024 个块），那么 1024 个平均长度为 2MB（约 2GB）的游程可以在一次合并中完成合并。对于固定大小的工作内存，更大的块大小会减小一次合并所能处理的文件大小；更小的块大小或更大的工作内存则会增大一次合并所能处理的文件大小。两次合并可以处理大得多的文件。使用 0.5MB 的工作内存和 4KB 的块，大小为 16~吉字节 的文件可以在两次合并中处理完，这对大多数应用来说已经足够大了。因此，对于单磁盘驱动器的外部排序来说，这是一种非常有效的算法。
12.6.2.1. 实验结果¶
表 12.6.1 显示了对以下实现的不同大小文件的排序运行时间比较： (1) 标准归并排序，两个输入归并段和两个输出归并段， (2) 两路归并排序，初始归并段较大（受可用内存大小限制）， (3) 生成大初始归并段后执行的 \(R\) 路归并排序。在每种情况下，文件由一系列四字节记录组成（两字节关键字和两字节数据值），即每兆字节文件大小 256K 条记录。从此表中我们可以看到，即使用于创建初始归并段的适度内存大小（两个块）也会带来巨大的时间节省。对归并段进行 4 路合并提供了另一个相当大的加速，然而，对于 \(R\) 超过约 4 或 8 个归并段的大规模多路合并没有太大帮助，因为大量时间花在确定 \(R\) 个归并段中哪个是下一个最小元素上。
从此实验中我们看到，构建大的初始归并段将运行时间减少到标准归并排序的三分之一多一点，具体取决于文件和内存大小。使用多路合并进一步将时间减少近一半。
12.6.2.2. 总结¶
总之，一个好的外部排序算法将寻求做到以下几点：
使初始归并段尽可能长。
在所有阶段，尽可能重叠输入、处理和输出。
使用尽可能多的工作内存。 应用更多内存通常会加速处理。实际上，更多的内存比更快的磁盘影响更大。更快的 CPU 不太可能对外部排序的运行时间产生太大改善，因为磁盘 I/O 速度是限制因素。
如果可能，使用额外的磁盘驱动器来 更多地重叠处理和 I/O，并允许顺序文件处理。
