chapter11外部排序.ppt

1、第十一章外部排序,11.1 外存信息的存取,11.1.1 磁帶信息的存取,11.1.2 磁盤信息的存取,11.2 外部排序的方法,11.1 外存信息的存取,11.1.1 磁帶信息的存取,磁帶：一條薄薄涂上一層磁性材料的窄帶（現(xiàn)在使用的磁帶大 多數(shù)有1/2英寸寬，最長可達3600英尺，繞在一個卷盤上）。它是 一種順序存取的存儲設備。,磁帶的工作原理：使用時，將磁帶放在磁帶機上，驅(qū)動器控制 磁帶盤轉(zhuǎn)動，帶動磁帶向前移動。通過讀/寫頭就可以讀出磁帶上的 信息或者把信息寫入磁帶中。,7道帶：在1/2英寸寬的帶面上記錄7位二進制信息的磁帶。,9道帶：在1/2英寸寬的帶面上記錄9位二進制信息的磁帶。每 一

2、橫排可表示一個字符（8位表示一個字符，剩下的一位作奇偶校 驗位）。,信息密度：每英寸的二進制字符數(shù)。通常為每英寸800位或 1600位或6250位。,移動速度：每秒200英寸。,間隙IRG（Inter Record Gap）：磁帶上相鄰兩組字符組（記錄） 之間的空白區(qū)。根據(jù)啟停時間的需要，這個間隙通常為1/43/4英寸。,例如，若每個字符組的長度是80個字符，IRG為3/4英寸，則對密 度為每英寸1600個字符的磁帶，其利用率僅為1/16，有15/16的帶用于 IRG。如圖11.1(a)所示。,塊間間隙IBG（Inter Block Gap）：將若干個字符組合并成塊，每 個字符組間沒有IRG，

3、而變成塊間的間隙。,例如，圖11.1(b)表示將20個長度為80字符的字符組存放在磁帶上的 一個物理塊中的情況。,(a) 字符組長80字符的磁帶,(b)成塊存放的磁帶,圖11.1磁帶上信息存放示意圖,磁帶上讀寫一塊信息所需的時間為：,TI/O = ta + n * tw 其中：ta為延遲時間，讀/寫頭到達傳輸信息所在物理塊起始位置所需 時間（顯然，延遲時間和信息在磁帶上的位置、當前讀/寫頭所在位置 有關）；tw為傳輸一個字符的時間。,成塊的優(yōu)點： （1）可以減少IRG的數(shù)目，從而提高磁帶的利用率，塊的長度大于 IBG的長度。 （2）可以減少I/O操作。因為一次I/O操作可把整個物理塊都讀到內(nèi)

4、存緩沖區(qū)中，然后再從緩沖區(qū)中取出所需要的信息（一個字符組）。 每當要讀一個字符組時，首先要查緩沖區(qū)中是否已有，若有，則不必執(zhí) 行I/O操作，直接從緩沖區(qū)讀取即可。,11.1.2 磁盤信息的存取,磁盤：是一個扁平的圓盤，盤面上有許多稱為磁道的圓圈，信息 就記載在磁道上。它是一種直接存取的存儲設備（DASD）。,磁盤的工作原理：盤片裝在一個主軸上，并繞主軸高速旋轉(zhuǎn)，當 磁道在讀/寫頭下通過時，便可進行信息的讀/寫。讀/寫信息的功能由 磁盤驅(qū)動器執(zhí)行。,固定頭盤：固定頭盤的每一磁道上都有獨立的磁頭，這些磁頭固 定不動，專負責讀/寫某一磁道上的信息。,活動頭盤：活動頭盤的磁頭是可以移動的。一個盤面上只

5、有一個 磁頭，磁頭裝在一個動臂上，可以從該面上的一道移動到另一道。,在磁盤上表明一個具體信息必須用一個三維地址：柱面號（確定 讀/寫頭的徑向運動)、盤面號、塊號(確定信息在盤片圓圈上的位置）。,訪問一塊信息： （1）找柱面,移動臂使磁頭移動到所需柱面上(稱為定位或?qū)げ?； （2）等待要訪問的信息轉(zhuǎn)動磁頭之下； （3）讀/寫所需信息。,磁盤上讀寫一塊信息所需的時間為： TI/O = tseek + tla + n * twm 其中：tseek為尋查時間（seek time）：即讀/寫頭定位的時間； tla為等待時間（latency time）：即等待信息塊的初始位置旋到 讀/寫頭下的時間； tw

6、m為傳輸時間（transmission time）。,11.2 外部排序的方法,（1）外部排序的過程,1按可用內(nèi)存大小，將外存上含n個記錄的文件分成若干長度 為l的子文件或段（segment），依次讀入內(nèi)存并利用有效的內(nèi)部排 序方法對它們進行排序，并將排序后得到的有序子文件（通常稱這 些有序子文件為歸并段或順串（run）重新寫入外存。,例如，假設有一個含10000個記錄的文件，首先通過10次內(nèi)部排 序得到10個初始歸并段R1R10，其中每一段都含1000個記錄。然后 對它們作如下圖所示的兩兩歸并，直至得到一個有序文件為止。,外部排序的過程：,2對歸并段進行逐趟歸并，使歸并段（有序的子文件）逐漸

7、 由小至大，直至得到整個有序文件為止。,從上圖可見，由10個初始歸并段到一個有序文件，共進行了4 趟歸并，每一趟從m個歸并段到 個歸并段。這種歸并方法稱 為2-路平衡歸并。,（2）外部排序所需的時間,例如，上例10000個記錄利用2-路歸并進行外排所需總的時間為： 10tIS500 tIO410000tmg,外部排序所需的總時間內(nèi)部排序(產(chǎn)生初始歸并段)所需的時間(mtIS)+ 外存信息讀寫時間(dtIO)+ 內(nèi)部歸并所需的時間(sutmg),其中：tIS是為得到一個初始歸并段進行內(nèi)部排序所需時間的均值； tIO是進行一個外存讀/寫時間的均值； utmg是對u個記錄進行內(nèi)部歸并所需時間； m為經(jīng)過內(nèi)部排序之后得到的初始歸并段的個數(shù)； s為歸并的趟數(shù)； d為總的讀/寫次數(shù)。,（3）d（總的讀/寫次數(shù)）和“歸并過程”的關系分析,若對上例中所得的10個初始歸并段進行5-路平衡歸并（即每一 趟將5個或5個以下的有序子文件歸并成一個有序子文件），則從下 圖可見，僅需進行二趟歸并，