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

2、。每 一橫排可表示一個字符（8位表示一個字符，剩下的一位作奇偶校 驗位）。,信息密度：每英寸的二進制字符數(shù)。通常為每英寸800位或 1600位或6250位。,移動速度：每秒200英寸。,3,間隙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）：將若干個字符組合并成塊，每 個字符組間

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

4、物理塊都讀到內(nèi) 存緩沖區(qū)中，然后再從緩沖區(qū)中取出所需要的信息（一個字符組）。 每當要讀一個字符組時，首先要查緩沖區(qū)中是否已有，若有，則不必執(zhí) 行I/O操作，直接從緩沖區(qū)讀取即可。,5,11.1.2 磁盤信息的存取,磁盤：是一個扁平的圓盤，盤面上有許多稱為磁道的圓圈，信息 就記載在磁道上。它是一種直接存取的存儲設備（DASD）。,磁盤的工作原理：盤片裝在一個主軸上，并繞主軸高速旋轉，當 磁道在讀/寫頭下通過時，便可進行信息的讀/寫。讀/寫信息的功能由 磁盤驅動器執(zhí)行。,固定頭盤：固定頭盤的每一磁道上都有獨立的磁頭，這些磁頭固 定不動，專負責讀/寫某一磁道上的信息。,活動頭盤：活動頭盤的磁頭是可以移動的。一個盤面上只有一個 磁頭，磁頭裝在一個動臂上，可以從該面上的一道移動到另一道。,6,11.1.2 磁盤信息的存取,在磁盤上表明一個具體信息必須用一個三維地址：柱面號（確定 讀/寫頭的徑向運動)、盤面號、塊號(確定信息在盤片圓圈上的位置）。,訪問一塊信息： （1）找柱面,移動臂使磁頭移動到所需柱面上(稱為定位或尋查)； （2）等待要訪問的信息轉動磁頭之下； （3）讀/寫所需信息。,磁盤上讀寫一塊信息所需的時間為： TI/O = tseek + tla + n * twm 其中：tseek為尋查時間（seek time）：即讀/寫頭定位的時間； tla