李云清 杨庆红 揭安全第 11章 外排序在排序操作中，当待排序数据量很大而内存中无法存储所有的数据时，仅仅使用内排序是无法完成排序任务的，此时需要使用外存储器进行外排序。
11.1外存储器简介
11.1.1磁盘存储器
11.1.2磁带存储器
11.2 文件简介
11.2.1 文件的逻辑结构
11.2.2文件的存储结构
11.3 外排序 ------磁盘排序
11.3 外排序 ------磁盘排序外排序中的主要方法是归并排序法。这种排序方法主要由两大步骤构成。
第一步，根据内存可用空间的大小将待排序文件分成若干个子文件逐个调入内存，保证每个子文件都能利用选定的内排序算法进行排序，并将排序后的所有有序子文件再依次写入外存。这些已排序的子文件称为初始有序串。
第二步，对这些有序串进行逐趟归并，使有序串的长度不断增大，而有序串的个数不断减少。反复执行第二步，直至得到整个有序文件为止。第一步的实质是内排序，第二步是外排序的主要内容。
11.3.1 磁盘排序外排序中使用的外存是磁盘存储器称为磁盘排序。
磁盘排序的思想用一个实例说明。
设有一个待排序文件含有 54000个记录,R1，
R2,……,R54000。计算机系统中现有可用内存空间可以对 9000个记录进行排序。待排序文件存放在磁盘上，设盘上每个块可存放 300个记录，排序过程如下所述。
首先，从磁盘上读入 30个块共 9000个记录放入内存，在内存中进行内排序，得到一个有序串，反复进行，整个文件每 9000个记录作一次内排序，可以得到
6个有序串 S1,S2,S3,S4,S5,S6。
每个初始有序串有 30个块组成，其中每个初始有序串在图示中用 3个小方框表示，每个小方框代表
10个块。
其次，取 3个内存块，每块可放 300个记录。用其中两块作为输入缓冲区，另一块作为输出缓冲区。先对有序串 S1和 S2进行归并，为此，可把这两个有序串中各自的第一个块读入分别写入两个输入缓冲区，这两个输入缓冲区的记录分别是有序的。利用上一章讲述的归并排序方法的思路，对两个输入缓冲区的记录进行归并，
将归并结果写入输出缓冲区。归并过程中，当输出缓冲区满时，就将输出缓冲区中的内容写入磁盘；当一个输入缓冲区腾空时，便把同一有序串的一下块读入，这样不断进行，直到有序串 S1和有序串 S2的归并完成。
用同样的方法将 S3和 S4,S5和 S6分别归并。这样整个文件经这一趟归并后可以得到 3个有序串。这趟归并需要对整个文件中的所有记录读写一次（即从磁盘上读入内存一次，并从内存写到磁盘一次），并在内存中参加一次归并。反复对每两个有序串进行归并，
最后得到一个有序串，即为排序结果。归并过程见图
11.3.2 多路归并 (略 )
11.1外存储器简介
11.1.1磁盘存储器
11.1.2磁带存储器
11.2 文件简介
11.2.1 文件的逻辑结构
11.2.2文件的存储结构
11.3 外排序 ------磁盘排序
11.3 外排序 ------磁盘排序外排序中的主要方法是归并排序法。这种排序方法主要由两大步骤构成。
第一步，根据内存可用空间的大小将待排序文件分成若干个子文件逐个调入内存，保证每个子文件都能利用选定的内排序算法进行排序，并将排序后的所有有序子文件再依次写入外存。这些已排序的子文件称为初始有序串。
第二步，对这些有序串进行逐趟归并，使有序串的长度不断增大，而有序串的个数不断减少。反复执行第二步，直至得到整个有序文件为止。第一步的实质是内排序，第二步是外排序的主要内容。
11.3.1 磁盘排序外排序中使用的外存是磁盘存储器称为磁盘排序。
磁盘排序的思想用一个实例说明。
设有一个待排序文件含有 54000个记录,R1，
R2,……,R54000。计算机系统中现有可用内存空间可以对 9000个记录进行排序。待排序文件存放在磁盘上，设盘上每个块可存放 300个记录，排序过程如下所述。
首先，从磁盘上读入 30个块共 9000个记录放入内存，在内存中进行内排序，得到一个有序串，反复进行，整个文件每 9000个记录作一次内排序，可以得到
6个有序串 S1,S2,S3,S4,S5,S6。
每个初始有序串有 30个块组成，其中每个初始有序串在图示中用 3个小方框表示，每个小方框代表
10个块。
其次，取 3个内存块，每块可放 300个记录。用其中两块作为输入缓冲区，另一块作为输出缓冲区。先对有序串 S1和 S2进行归并，为此，可把这两个有序串中各自的第一个块读入分别写入两个输入缓冲区，这两个输入缓冲区的记录分别是有序的。利用上一章讲述的归并排序方法的思路，对两个输入缓冲区的记录进行归并，
将归并结果写入输出缓冲区。归并过程中，当输出缓冲区满时，就将输出缓冲区中的内容写入磁盘；当一个输入缓冲区腾空时，便把同一有序串的一下块读入，这样不断进行，直到有序串 S1和有序串 S2的归并完成。
用同样的方法将 S3和 S4,S5和 S6分别归并。这样整个文件经这一趟归并后可以得到 3个有序串。这趟归并需要对整个文件中的所有记录读写一次（即从磁盘上读入内存一次，并从内存写到磁盘一次），并在内存中参加一次归并。反复对每两个有序串进行归并，
最后得到一个有序串，即为排序结果。归并过程见图
11.3.2 多路归并 (略 )
