7.1磁盤文件的歸并分類7.2磁帶文件的歸并分類第7章外部分類歸并方法：首先將文件中的數(shù)據(jù)輸入到內存，采用內部分類方法進行分類（歸并段），然后將有序段寫回外存；對多歸并段進行多遍歸并，最后形成一個有序序列。7.1磁盤文件的歸并分類磁盤信息的存取

磁盤：是一個扁平的圓盤，盤面上有許多稱為磁道的圓圈，信息就記載在磁道上。它是一種直接存取的存儲設備（DASD）。

磁盤的工作原理：盤片裝在一個主軸上，并繞主軸高速旋轉，當磁道在讀/寫頭下通過時，便可進行信息的讀/寫。讀/寫信息的功能由磁盤驅動器執(zhí)行。

固定頭盤：固定頭盤的每一磁道上都有獨立的磁頭，這些磁頭固定不動，專負責讀/寫某一磁道上的信息。

活動頭盤：活動頭盤的磁頭是可以移動的。一個盤面上只有一個磁頭，磁頭裝在一個動臂上，可以從該面上的一道移動到另一道。

在磁盤上表明一個具體信息必須用一個三維地址：柱面號（確定讀/寫頭的徑向運動)、盤面號、塊號(確定信息在盤片圓圈上的位置）。磁盤結構：由磁盤驅動器、讀、寫磁頭、活動臂、盤片（磁道、扇區(qū)）、旋轉主軸構成。速度快、容量大、直接存取設備。訪問一塊信息：（1）找柱面,移動臂使磁頭移動到所需柱面上(稱為定位或尋查)；（2）等待要訪問的信息轉動磁頭之下；（3）讀/寫所需信息。磁盤上讀寫一塊信息所需的時間為：

TI/O=tseek+tla+n*twm其中：tseek為尋查時間（seektime）：即讀/寫頭定位的時間；

tla為等待時間（latencytime）：即等待信息塊的初始位置旋到讀/寫頭下的時間；

twm為傳輸時間（transmissiontime）。例：假設一個磁盤文件，由4500個記錄組成，分別記為A1,A2,……,A4500

設系統(tǒng)提供容納750個記錄的內存共分類使用，每次磁盤讀寫250個記錄的數(shù)據(jù)塊，則可設計分類過程如下：(1)每次從文件中輸入三個數(shù)據(jù)塊（750個記錄）到工作空間，進行內部分類。分類結果寫回磁盤，構成6個初始歸并段：R1,R2,R3,R4,R5,R6R1R2R3R4R5R61-750751-15001501-22502251-30003001-37503751-4500（2）將內存空間三等分，每塊250個記錄，其中2塊為輸入緩沖區(qū)，1塊為輸出緩沖區(qū)。歸并R1和R2，輸出到輸出緩沖區(qū)，若輸出緩沖區(qū)滿，則寫盤。同樣，若

R1和R2的緩沖區(qū)出現(xiàn)空，則繼續(xù)讀盤，直到歸并結束為止。R12=R1+R2；同樣得到：R34=R3+R4,R56=R5+R6；

R12、R34、R56分別都包含1500個記錄。（3）類似（2）的方法，可將R12和R34歸并成R1234,，再將R1234和R56進行歸并。得到最后的排序結果。R1R2R3R4R5R6R12R34R56R1234R12346×750記錄3×1500記錄12×250記錄18×250記錄K路歸并……...遍數(shù)[log2m]層數(shù)[log2m]+1M個歸并段的歸并過程R1R2Rm-1Rm2…KK+1…2K……m...logkm+1levers(1)多路歸并——減少歸并遍數(shù)并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊(3)初始歸并段的生成討論問題logkm遍比較次數(shù)：擴大初始歸并段長度，從而減少初始歸并段個數(shù)m進行多路(k路)歸并減少合并趟數(shù)s，以減少I/O次數(shù)

s=logkm提高外排序效率的途徑(1)多路歸并——減少歸并遍數(shù)m個初始段進行2路歸并，需要log2m遍歸并;一般地，m個初始段，采用k路歸并，需要logkm遍歸并。顯然，k越大，歸并遍數(shù)越少，可提高歸并的效率。

在k路歸并時，從k個關鍵字中選擇最小記錄時，要比較K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為：

n*(k-1)[log2m/log2k]可以看出，隨著k增大，(k-1)/log2k也增大，當歸并路數(shù)多時，CPU處理的時間也隨之增多。為此要選擇好的分類方法，以減少分類中比較次數(shù)。610920689901796817681516203820301525155011161001101820

選擇樹(Selectiontree)或敗者樹(treeofloser)分析：第一次建立選擇樹的比較所花時間為:O(k-1)=O(k)而后每次重新建造選擇樹所需時間為：

O(log2k)n個記錄處理時間為初始建立選擇樹的時間加上n-1次重新選擇樹的時間：

O((n-1)·

log2k)+O(k)=O(n·

log2k)這就是k路歸并一遍所需的CPU處理時間。歸并遍數(shù)為logkm，總時間為：

O(n·

log2k·

logkm)=O(n·

log2m)(k路歸并CPU時間與k無關)最佳歸并樹

將哈夫曼樹進行拓展，不僅對2叉樹，同樣可形成3叉、4叉、…、k叉樹，亦稱為哈夫曼樹，同樣可求得帶權路徑長度最小。最佳歸并樹：對長度不等的m個初始歸并段，構造哈夫曼樹作為歸并樹，便可使在進行外部歸并時所需要對外存進行的讀寫次數(shù)達到最小。

最佳歸并樹中，并不只是只有度為k和0的結點，會有缺額。當初始歸并段的數(shù)目不足時，需附加長度為0的虛段，按照哈夫曼樹的構造原則，權為0的葉子結點應離樹根最遠。問題：起因：由于初始歸并段通常不等長,進行歸并時,長度不同的初始歸并段歸并的順序不同,讀寫外存的總次數(shù)也不同。目的：減少讀寫外存的次數(shù)。

例：假定由置換－選擇分類法生成了9個初始歸并段，記錄數(shù)分別為9、30、12、18、3、17、2、6、24。如果進行3-路歸并，請討論在各種情況下的對外存的讀寫次數(shù)。從外存讀121個記錄寫入外存121個記錄從外存讀121個記錄寫入外存121個記錄30129317186242513832121總共讀寫外存484個記錄從外存讀11個記錄寫入外存11個記錄從外存讀91個記錄寫入外存121個記錄寫入外存91個記錄從外存讀121個記錄62392417183011325912112總共讀寫外存446個記錄按照hafuman樹的思想，記錄少的段最先合并。不夠時增加虛段。從外存讀5個記錄寫入外存67個記錄從外存讀91個記錄寫入外存67個記錄寫入外存91個記錄32691718125204791總共讀寫外存326個記錄24從外存讀5個記錄

虛段的補法:

在K路平衡歸并時，它的歸并樹的模型是一棵度為K的樹。在這棵樹上的結點要么是葉子，要么是具有K個孩子的內部結點。設具有K個孩子的內部結點共有nk

個。初始歸并段的個數(shù)為m個。設n=nk+m，故：從結點出發(fā)的分枝，共計有K*nk

個。若從進入結點的角度進行考慮，則共有：nk+m-1注意：沒有分枝進入根結點。所以，K*nk＝nk+m-1

于是：nk=(m-1)/(K-1)

這就意味著，若(m-1)MOD(K-1)＝0，無需增加虛段。否則，要增加虛段，其數(shù)目為：

（K-1)-(m-1)MOD(K-1)限制：由于磁帶尋找具有最少記錄的初始歸并段，必須反復倒帶。所以，實用性不強。在磁盤的情況下，需要有段包含的記錄數(shù)信息、段的位置信息等。文件如集中放置在幾個相鄰的柱面上的情況比較合適。并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊----1324ou(1)ou(2)iu(1)iu(2)----iu(3)iu(4)12---3-457--34----57615歸并到ou(1)輸入到in(3)歸并到ou(2)輸入到in(4)輸出ou(1)(a)(b)(c)56

89---7-15

78-92025---159-

--2025

-15歸并到ou(1)輸入到in(1)歸并到ou(1)輸入到in(3)輸出ou(2)(d)(e)(f)歸并到ou(2)輸入到in(2)輸出ou(1)輸出ou(2)

對k個歸并段進行k路歸并至少需要k個輸入和1個輸出緩沖區(qū)，要使輸入、輸出和歸并同時進行，k+1個緩沖區(qū)是不夠的，需要2k個輸入緩沖區(qū)實現(xiàn)并行操作。135789246152025(3)初始歸并段的生成步12345678910111213…緩沖區(qū)內容151515(11)(11)(11)(11)(11)(11)1111(06)……1919191925(16)(16)(16)(16)161616……04122727272734(26)(26)262626……8383838383838383(07)109090……輸出結果0412151925273483

07101116…R1R2(a)初始歸并段的長度≥緩沖區(qū)的長度(b)任何內部分類算法都可作為生成初始歸并段的算法(c)例如：緩沖區(qū)的長度為4，輸入序列為：

151904831227112516342607109006…新輸入記錄.key小于當前記錄.key，等待下一個歸并段采用選擇樹法生成初始歸并段的長度平均是緩沖區(qū)長度的兩倍。7.2磁帶文件的歸并分類（外部）存儲設備——紙帶、磁鼓、磁帶、磁盤等磁帶信息的表示：一種磁化方向、代表1另一種磁化方向，代表00100100110101111關于磁帶==〉磁帶信息的存取

磁帶：一條薄薄涂上一層磁性材料的窄帶（現(xiàn)在使用的磁帶大多數(shù)有1/2英寸寬，最長可達3600英尺，繞在一個卷盤上）。它是一種順序存取的存儲設備。

磁帶的工作原理：使用時，將磁帶放在磁帶機上，驅動器控制磁帶盤轉動，帶動磁帶向前移動。通過讀/寫頭就可以讀出磁帶上的信息或者把信息寫入磁帶中。

7道帶：在1/2英寸寬的帶面上記錄7位二進制信息的磁帶。

9道帶：在1/2英寸寬的帶面上記錄9位二進制信息的磁帶。每一橫排可表示一個字符（8位表示一個字符，剩下的一位作奇偶校驗位）。

信息密度：每英寸的二進制字符數(shù)。通常為每英寸800位或1600位或6250位。移動速度：每秒200英寸。

間隙IRG（InterRecordGap）：磁帶上相鄰兩組字符組（記錄）之間的空白區(qū)。根據(jù)啟停時間的需要，這個間隙通常為1/4~3/4英寸。

例如，若每個字符組的長度是80個字符，IRG為3/4英寸，則對密度為每英寸1600個字符的磁帶，其利用率僅為1/16，有15/16的帶用于IRG。如圖11.1(a)所示。

塊間間隙IBG（InterBlockGap）：將若干個字符組合并成塊，每個字符組間沒有IRG，而變成塊間的間隙。

例如，圖(b)表示將20個長度為80字符的字符組存放在磁帶上的一個物理塊中的情況。IRGIRGIRG記錄(a)字符組長80字符的磁帶IBGIBGIBG20個記錄20個記錄20個記錄(b)成塊存放的磁帶磁帶上信息存放示意圖磁帶上讀寫一塊信息所需的時間為： TI/O=ta+n*tw其中：ta為延遲時間，讀/寫頭到達傳輸信息所在物理塊起始位置所需時間（顯然，延遲時間和信息在磁帶上的位置、當前讀/寫頭所在位置有關）；tw為傳輸一個字符的時間。成塊的優(yōu)點：（1）可以減少IRG的數(shù)目，從而提高磁帶的利用率，塊的長度大于IBG的長度。（2）可以減少I/O操作。因為一次I/O操作可把整個物理塊都讀到內存緩沖區(qū)中，然后再從緩沖區(qū)中取出所需要的信息（一個字符組）。每當要讀一個字符組時，首先要查緩沖區(qū)中是否已有，若有，則不必執(zhí)行I/O操作，直接從緩沖區(qū)讀取即可。

與磁盤不同，磁帶是順序存儲設備，讀取信息塊的時間與信息塊的位置有關。研究磁帶分類，需要了解信息塊的分布。K路平衡歸并分類磁帶機數(shù)量：2k輸入：T1,T2,……,Tk

輸出輸出：Tk+1,Tk+2,……,T2k

輸入磁帶機T1T2…Tk歸并段R1R2…RkRk+1Rk+2…R2k…………Rmk+1………T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)T3:?T4:?T1:?T2:?T3:

R1(2000),R3(2000)T4:R2(2000)T1:R1(4000)T2:

R2(2000)T3:?T4:?T1:?T2:?T3:R1(6000)

T4:?i遍后t1t2t3開始13(1L)21(L)空1空8(1L)13(2L)28(3L)空5(2L)33(3L)5(5L)空4空2(5L)3(8L)52(13L)空1(8L)61(13L)1(21L)空7空空1(34L)步t1t2t3總段數(shù)n0011n-11102n-22013n-30235n-43508n-580513n-6081321n-71321034多階段歸并分類

K+1臺磁帶機，實現(xiàn)k路歸并K階Fibonacci數(shù)列tji表示第j步中邏輯上第i臺磁帶機。n-j步歸并段分布規(guī)則空磁帶機臺號=K+1當j=0或k+1的整數(shù)倍j%(k+1)j不為上述值注：在多路歸并中，若要求歸并的文件其初始歸并段總數(shù)不是K階Fibonacci數(shù)，則需附加一些虛的歸并段數(shù)，以湊成k階Fibonacci數(shù)，同時還應該將虛歸并段適當?shù)胤植荚趉路歸并的k臺磁帶上。例1：設有磁盤文件中記錄的關鍵字分別為：

10,20,15,25,12,13,21,30,8,16,10

用置換-選擇排序法產生初始歸并段，問可產生幾個初始歸并段？每個初始歸并段包含哪些記錄（設工作區(qū)能容納4個記錄）。解：內存緩沖區(qū)可容納4個記錄，采用4路歸并的置換-選擇排序方法生成初始歸并段，如表所示。步1234567891011緩沖區(qū)內容101213212121(16)(16)16162020202020(8)(8)(8)151515153030303025252525252525(10)10輸出結果101213152021253081016

生成的第一個初始歸并段第二個初始歸并段例2：給出一組關鍵字T=(12,2,16,30,8,28,4,10,20,6,18),設內存工作區(qū)可容納4個記錄，寫出用置換-選擇排序得到的全部初始歸并段。解：初始歸并段1：2,8,12,16,28,30

初始歸并段2：4,6,10,18,20例3：設有13個初始歸并段，其長度分別為：28,16,37,42,5,9,13,14,20,17,30,12,18。試畫出4路歸并時的最佳排序樹，并計算它的帶權路徑長度。解：n=13,k=4

因為(n-1)%(k-1)=0,所以不需要加虛段。WPS=(5+9+12+13+14+16+17+18+20+28+30+37)×2+42=4805912131416171820283037651154226139最佳歸并樹例：假設4個初始歸并段如下：

R1:15,16,25,32R2:3,22,28,45R3:1,12,30,42R4:33,60給出進行4路歸并的過程。(1)輸出1R1:15,16,25,32R2:3,22,28,45R3:12,30,42R4:33,60(2)輸出1,3R1:15,16,25,32R2:22,28,45R3:12,30,42R4:33,60(3)輸出1,3,12R1:15,16,25,32R2:22,28,45R3:30,42R4:33,60(4)輸出1,3,12,15R1:16,25,32R2:22,28,45R3:30,42R4:33,60(5)輸出1,3,12,15,16R1:25,32R2:22,28,45R3:30,42R4:33,60(6)輸出1,3,12,15,16,22R1:25,32R2:28,45R3:30,42R4:33,60(7)輸出1,3,12,