《chapter11外部排序》由会员分享，可在线阅读，更多相关《chapter11外部排序（10页珍藏版）》请在金锄头文库上搜索。
1、chapter11chapter11外部排序外部排序11.1 外存信息的存取外存信息的存取11.1.1 磁带信息的存取磁带信息的存取 磁带磁带：一条薄薄涂上一层磁性材料的窄带（现在使用的磁带大：一条薄薄涂上一层磁性材料的窄带（现在使用的磁带大多数有多数有1/2英寸宽，最长可达英寸宽，最长可达3600英尺，绕在一个卷盘上）。它是英尺，绕在一个卷盘上）。它是一种顺序存取的存储设备。一种顺序存取的存储设备。 磁带的磁带的工作原理工作原理：使用时，将磁带放在磁带机上，驱动器控制：使用时，将磁带放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动。通过读磁带盘转动，带动磁带向前移动。通过读/写头就可以读
2、出磁带上的写头就可以读出磁带上的信息或者把信息写入磁带中。信息或者把信息写入磁带中。7道带道带：在：在1/2英寸宽的带面上记录英寸宽的带面上记录7位二进制信息的磁带。位二进制信息的磁带。 9道带道带：在：在1/2英寸宽的带面上记录英寸宽的带面上记录9位二进制信息的磁带。每位二进制信息的磁带。每一横排可表示一个字符（一横排可表示一个字符（8位表示一个字符，剩下的一位作奇偶校位表示一个字符，剩下的一位作奇偶校验位）。验位）。 信息密度信息密度：每英寸的二进制字符数。通常为每英寸：每英寸的二进制字符数。通常为每英寸800位或位或1600位或位或6250位。位。 移动速度移动速度：每秒：每秒200英寸
3、。英寸。 间隙间隙IRG（Inter Record Gap）：磁带上相邻两组字符组（记录）：磁带上相邻两组字符组（记录）之间的空白区。根据启停时间的需要，这个间隙通常为之间的空白区。根据启停时间的需要，这个间隙通常为1/43/4英寸。英寸。 例如，若每个字符组的长度是例如，若每个字符组的长度是80个字符，个字符，IRG为为3/4英寸，则对密英寸，则对密度为每英寸度为每英寸1600个字符的磁带，其利用率仅为个字符的磁带，其利用率仅为1/16，有，有15/16的带用于的带用于IRG。如图。如图11.1(a)所示。所示。 块间间隙块间间隙IBG（Inter Block Gap）：将若干个字符组合并成
4、块，每）：将若干个字符组合并成块，每个字符组间没有个字符组间没有IRG，而变成块间的间隙。，而变成块间的间隙。 例如，图例如，图11.1(b)表示将表示将20个长度为个长度为80字符的字符组存放在磁带上的字符的字符组存放在磁带上的一个物理块中的情况。一个物理块中的情况。 IRG IRG IRG记记 录录(a) 字符组长字符组长80字符的磁带字符的磁带IBG IBG IBG20个记录个记录 20个记录个记录 20个记录个记录 (b)成块存放的磁带成块存放的磁带图图11.1磁带上信息存放示意图磁带上信息存放示意图磁带上读写一块信息所需的时间为：磁带上读写一块信息所需的时间为：TI/O = ta +
5、 n * tw其中：其中：ta为延迟时间，读为延迟时间，读/写头到达传输信息所在物理块起始位置所需写头到达传输信息所在物理块起始位置所需时间（显然，延迟时间和信息在磁带上的位置、当前读时间（显然，延迟时间和信息在磁带上的位置、当前读/写头所在位置写头所在位置有关）；有关）；tw为传输一个字符的时间。为传输一个字符的时间。成块的优点：成块的优点： （1）可以减少）可以减少IRG的数目，从而提高磁带的利用率，块的长度大于的数目，从而提高磁带的利用率，块的长度大于IBG的长度。的长度。 （2）可以减少）可以减少I/O操作。因为一次操作。因为一次I/O操作可把整个物理块都读到内操作可把整个物理块都读到
6、内存缓冲区中，然后再从缓冲区中取出所需要的信息（一个字符组）。存缓冲区中，然后再从缓冲区中取出所需要的信息（一个字符组）。每当要读一个字符组时，首先要查缓冲区中是否已有，若有，则不必执每当要读一个字符组时，首先要查缓冲区中是否已有，若有，则不必执行行I/O操作，直接从缓冲区读取即可。操作，直接从缓冲区读取即可。 11.1.2 磁盘信息的存取磁盘信息的存取 磁盘磁盘：是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息：是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息就记载在磁道上。它是一种直接存取的存储设备（就记载在磁道上。它是一种直接存取的存储设备（DASD）。）。 磁盘的磁盘的工作原理工作
7、原理：盘片装在一个主轴上，并绕主轴高速旋转，当：盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读磁道在读/写头下通过时，便可进行信息的读写头下通过时，便可进行信息的读/写。读写。读/写信息的功能由写信息的功能由磁盘驱动器执行。磁盘驱动器执行。 固定头盘固定头盘：固定头盘的每一磁道上都有独立的磁头，这些磁头固：固定头盘的每一磁道上都有独立的磁头，这些磁头固定不动，专负责读定不动，专负责读/写某一磁道上的信息。写某一磁道上的信息。 活动头盘活动头盘：活动头盘的磁头是可以移动的。一个盘面上只有一个：活动头盘的磁头是可以移动的。一个盘面上只有一个磁头，磁头装在一个动臂上，可以从该面上的一道移动到另一道
8、。磁头，磁头装在一个动臂上，可以从该面上的一道移动到另一道。 在磁盘上表明一个具体信息必须用一个在磁盘上表明一个具体信息必须用一个三维地址三维地址：柱面号（确定：柱面号（确定读读/写头的径向运动写头的径向运动)、盘面号、块号、盘面号、块号(确定信息在盘片圆圈上的位置）。确定信息在盘片圆圈上的位置）。 访问一块信息访问一块信息： （1）找柱面）找柱面,移动臂使磁头移动到所需柱面上移动臂使磁头移动到所需柱面上(称为定位或寻查称为定位或寻查)； （2）等待要访问的信息转动磁头之下；）等待要访问的信息转动磁头之下； （3）读）读/写所需信息。写所需信息。磁盘上读写一块信息所需的磁盘上读写一块信息所需的
9、时间时间为：为：TI/O = tseek + tla + n * twm其中：其中：tseek为寻查时间（为寻查时间（seek time）：即读）：即读/写头定位的时间；写头定位的时间； tla为等待时间（为等待时间（latency time）：即等待信息块的初始位置旋到）：即等待信息块的初始位置旋到 读读/写头下的时间；写头下的时间； twm为传输时间（为传输时间（transmission time）。）。11.2 外部排序的方法外部排序的方法（1）外部排序的过程）外部排序的过程 1按可用内存大小，将外存上含按可用内存大小，将外存上含n个记录的文件分成若干长度个记录的文件分成若干长度为为l的
10、子文件或段（的子文件或段（segment），依次读入内存并利用有效的内部排），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件（通常称这序方法对它们进行排序，并将排序后得到的有序子文件（通常称这些有序子文件为些有序子文件为归并段归并段或或顺串顺串（run）重新写入外存。）重新写入外存。 例如，假设有一个含例如，假设有一个含10000个记录的文件，首先通过个记录的文件，首先通过10次内部排次内部排序得到序得到10个初始归并段个初始归并段R1R10，其中每一段都含，其中每一段都含1000个记录。然后个记录。然后对它们作如下图所示的两两归并，直至得到一个有序文件为止。对
11、它们作如下图所示的两两归并，直至得到一个有序文件为止。外部排序的过程：外部排序的过程： 2对归并段进行逐趟归并，使归并段（有序的子文件）逐渐对归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。由小至大，直至得到整个有序文件为止。R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R3 有序文件有序文件 从上图可见，由从上图可见，由10个初始归并段到一个有序文件，共进行了个初始归并段到一个有序文件，共进行了4趟归并，每一趟从趟归并，每一趟从m个归并段到个归并段到 个归并段。这种归并方法称个归并段。这
12、种归并方法称为为2-路平衡归并。路平衡归并。（2）外部排序所需的时间）外部排序所需的时间例如，上例例如，上例10000个记录利用个记录利用2-路归并进行外排所需总的时间为：路归并进行外排所需总的时间为：10tIS500 tIO410000tmg外部排序所需的总时间内部排序外部排序所需的总时间内部排序(产生初始归并段产生初始归并段)所需的时间所需的时间(mtIS)+ 外存信息读写时间外存信息读写时间(dtIO)+ 内部归并所需的时间内部归并所需的时间(sutmg)其中：其中：tIS是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值； tIO是进行一
13、个外存读是进行一个外存读/写时间的均值；写时间的均值； utmg是对是对u个记录进行内部归并所需时间；个记录进行内部归并所需时间； m为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数； s为归并的趟数；为归并的趟数； d为总的读为总的读/写次数。写次数。（3）d（总的读（总的读/写次数）和写次数）和“归并过程归并过程”的关系分析的关系分析 若对若对上例上例中所得的中所得的10个初始归并段进行个初始归并段进行5-路平衡归并（即每一路平衡归并（即每一趟将趟将5个或个或5个以下的有序子文件归并成一个有序子文件），则从下个以下的有序子文件归并成一个有序子文件），则从下图可见，仅需进行二趟归并，外排的总的读图可见，仅需进行二趟归并，外排的总的读/写次数便减至写次数便减至2100+100300，比，比2-路归并减少了路归并减少了200次的读次的读/写。写。R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R1 R2 有序文件有序文件 可见，对同一文件而言，进行外排时所需读可见，对同一文件而言，进行外排时所需读/写外存的次数和写外存的次数和归并的趟数归并的趟数s成正比。成正比。 一般情况下，对一般情况下，对m个初始归并段进行个初始归并段进行k-路平衡归并时，归并的路平衡归并时，归并的趟数：趟数： 结束结束
