磁盘排序分析

因为内存空间有限，所以每次进入内存中参与排序的只是完整文件的一部分。对于磁盘排序：在排序开始之后，首先需要根据内存空间的大小，将完整文件划分成若干个长度为l的子文件（子文件又称为段）；然后将这些子文件依次读入内存中，使用内部排序方法为每一个子文件排序后，再重新写回外存，此时已各自有序的子文件称为归并段或者顺串；之后对这些归并段进行归并，直到所有归并段组成有序的完整文件为止。如图1所示为一次完整的磁盘排序过程。

图1 磁盘排序过程示意

由图1可以看出，文件F首先从外存被读入内存，在内存中经内存排序处理之后，生成归并段重新写回外存，此时的每个归并段都是有序的，且归并段之间的相对次序也是确定的；之后使用某种归并方法对归并段进行归并排序，这一过程仍要借助内存来完成，其间同样有读/写操作发生。

假设现有一待排序文件F，F中包含6000条记录。若内存WA依次最多能对600条记录进行排序，内存每次读/写包含200条记录的物理块。那么内存每次读入3个物理块，并对读入的物理块进行内排序，生成一个初始归并段。因此文件F被分为10个归并段，每个归并段中包含600条记录，记为F1~F10。若使用2-路归并排序对这10个归并段进行归并，由图2可知，经过4次归并，这10个归并段被归并为一个有序文件。

图2 归并段的2-路归并过程

在生成归并段之前，F中的6000条记录先分块被扫描一遍，经过读操作进入内存。已知每个物理块包含200条记录，那么扫描完毕时文件F被读/写各30次，其间每读入一个物理块，这些数据便在内存中被排序，排序完毕的数据被重新写回外存，成为一个归并段。

之后对生成的归并段F1~F10进行归并排序。此时将内存分为3块，每块能容纳200条记录，其中两块作为输入缓冲区，用来存放读入内存的记录；另外一块作为输出缓冲区，用来存放归并过程中排好序的记录，当输出缓冲区存满时，进行一次写操作，将其中的记录写到外存。

假设生成一个初始归并段（内部排序）耗费的时间为tg，内存从外存读或者向外存写一个物理块耗费的时间为tIO，对u条记录进行内部归并耗费的时间为ut，归并的轮数为s，归并段的数量为m，信息读写次数为r，那么进行一次磁盘排序所需的时间为：

相比而言，内部排序耗费的时间远小于内外存之间的读写时间，又因为生成初始归并段的时间确定（因为物理块大小确定），所以若要提高外部排序效率，应该尽量减少读写的次数r。

那么该如何减少读写次数呢？由以上分析可知，读写操作主要发生在归并的过程中，读写次数也就与归并排序中归并的轮数有关，归并的轮数越少，读写的次数也就越少。若归并段的数量为m，假设使用k-路归并排序进行归并，那么归并的轮数，归并轮数n与初始归并段数量m成正比，与k成反比，也就是说，初始归并段的数量越少，或者归并时的k值越大，归并的轮数就越少。

分析图2中的2-路归并排序：第一次归并过程，所有记录都被扫描一遍，经过30次读操作和30次写操作，归并段的数量减少为5个；第二次归并过程中，归并段F1′~F4′各被扫描一遍，经过48次读/写操作，归并段的数量减少为3个；第三次归并过程中，归并段F1″和F2″各被扫描一遍，经过48次读/写操作，归并段的数量减少为2个；最后一次归并过程中，当前仅有的两个归并段各被扫描一遍，经过60次读/写操作，这两个归并段被归并为一个有序文件。整个过程读写次数为276次。

若使用4-路归并对这10个归并段进行归并，由图9-55可知，归并执行的轮数为2。两轮归并最多将文件F扫描三遍，那么读写次数不超过180次。

图3 归并段的4-路归并过程

若初始归并段只有2个，那么仅需一次归并排序即可完成外排序，归并中读写总次数为60，但是初始归并段的数量受到内存容量的限制，所以只能在合适的范围内调整。