外部排序的方法

在实际应用中，由于外存设备的不同，通常又可分配磁盘文件排序和磁带文件排序两大类。磁带排序和磁盘排序的基本步骤相类似，主要的不同之处在于初始归并段在外存介质中的分布方式，磁盘是直接存储设备，磁带是顺序存储设备。下面以磁盘为例进行说明。

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读写的机械动作所需时间远远超过内存运算的时间（相比而言，可以忽略不计）。因此，在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外部排序通常采用归并排序方法。它包括两个相对独立的阶段：首先，根据内存缓冲区的大小，将外存上含n个记录的文件分成若干个长度为h的子文件，依次读入内存并利用有效的内存排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，通常称这些有序子文件为归并段或顺串；然后，对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小到大，直至得到整个有序文件为止。

例如，一个含有2000个记录的文件，每个磁盘可容纳250个记录，则该文件包含8个磁盘块。然后对该文件作二路归并排序，每次往内存读入两个磁盘块，排序后再写回磁盘。若把内存工作区等分为3个缓冲区。其中的两个为输入缓冲区。一个为输出缓冲区，在内存中利用简单二路归并merge函数实现二路归并。

首先，从参加归并排序的两个输入归并段R1和R2中分别读入一个块，放入输入缓冲区1和输入缓冲区2中。然后，在内存中进行二路归并，归并出来的对象顺序存放在输出缓冲区中。若输出缓冲区存满，则将其内的对象顺序写到归并段（R1'）中，再将该输出缓冲区清空，继续存放归并后的对象。若某一个输入缓冲区的对象取空，则从对应的输入归并段中再读取下一块（这种情况在第一趟归并时不会出现），继续参加归并。如此继续，直到两个输入归并段中对象全部读入内存并都归并完成为止。当R1和R2归并完后，再归并R3和R4、R5和R6、最后归并R7和R8，这算作一趟归并。再把上一趟的结果R1'、R2'、R3'、R4'两两归并，这又是一趟归并。最后把R1''和R2"两两归并，这又是一趟归并。最后把R1"和R2"两两归并段归并，结果得到最终的有序文件，一共进行了3趟归并。

在外部排序中实现两两归并时，不仅要调用merge过程，而且要进行外存的读写；由于不可能将两个有序段及归并结果段同时存放在内存中，需要不停地将数据读出、写入磁盘，这将耗费大量的时间。一般情况下：

Tes=R*Tis+d*Tio+S*(n-1)*Tmg

其中，r是初始归并段个数，Tis是对每一个初始归并段进行内部排序的时间，d是访问外存块的次数，Tio是每一个块的存取时间，S是归并趟数，n是每趟参加二路归并的记录个数，Tmg是每作一次内部归并，取得一个关键字最小记录的时间。显然磁盘存取的时间远远大于内部排序和内部归并的时间，因此要提高外排序的速度，应着力减少d,即I/O次数。

由于外存上信息的读写是以“物理块”为单位的，且每个物理块可容纳250个记录，可知每一趟归并需要进行8次读和8次写，3趟归并加上内部排序时所需进行的读写使得在外排中总共需要进行16*4=64次的读写。故上述二路归并排序的总时间为：

8*Tis+64*Tio+3*2000Tmg

对于上例，若采用思路归并排序只需要2趟归并，外排时总的读写次数便减至2*16+16=48.因此，增大归并路数，可以减少归并趟数，从而减少总的I/O次数。

一般地，对r个初始归并段，作m路平衡归并，归并树可用严格m叉树（即只有度为m与度为0的结点的m叉树）来表示。第一趟可将r个初始并段归并为[r/m]个归并段，以后每一趟归并将L个归并段归并成【L/m】(向下取整)个归并段，直到最后形成一个大的归并段为止。树的高度=【logm r】（向下取整）=归并趟数S.

可见只要增大归并路m，或减少初始归并段个数r，都能减少归并趟数S，以减少读写磁盘次数d，达到提高外部排序速度的目的。