數(shù)據(jù)結構第10章

第10章外部排序10.1外存信息的特性

10.2外排序的基本方法10.1外存信息的特性10.1.1磁帶存儲器1.磁帶存儲器的特性圖10.1磁帶運行示意圖目前常用的典型磁帶長2400英尺1英尺=0.3048m，寬0.5英寸1英寸=0.0254m，厚0.002英寸。磁帶表面上涂有磁性材料，可分為七道或九道磁帶。七道磁帶的每一橫排中有六個二進制數(shù)據(jù)位和一個奇偶校驗位。九道磁帶的每一橫排中有八個二進制數(shù)據(jù)位和一個奇偶校驗位。這樣的一排二進制數(shù)據(jù)位組成一個字節(jié)。磁帶的存儲密度（每英寸帶面上所存放的字節(jié)數(shù)）通常為800字節(jié)／英寸和1600字節(jié)／英寸兩種，走帶速度為200英寸／s。磁帶存儲器是一種典型的順序存取設備。所謂順序存取，就是將記錄在存儲器上一個接一個地依次存放，為得到第i個記錄，必須先讀第i-1個記錄。磁帶的存取時間主要用在定位上（即把磁帶轉到待讀／寫信息所在的物理位置上），讀／寫頭與所需信息的距離越遠，定位時間就越長，一般情況下，定位時間為20毫秒至數(shù)分鐘。當磁帶轉到信息所在位置上時才開始真正讀寫數(shù)據(jù)。磁帶的讀寫速度由走帶速度和存儲密度所決定，對于存儲密度為800字節(jié)／英寸的磁帶來說，每秒鐘約可寫800×200＝160000字節(jié)。由于磁帶機不是連續(xù)運轉的設備，而是一種啟停設備，因而磁帶的運轉從靜止到達正常的走帶速度以及從正常運轉到達停止都需要一定的時間。在啟停時間內(nèi)，不能對磁帶進行正常讀寫，因此磁帶上的信息通常分為若干記錄塊，塊與塊之間留有一定的間隙，該間隙一般為1/4～3/4英寸。2.分頁塊存儲方法為了減少存儲空間的浪費，通常采用把若干個記錄組合成頁塊進行存儲的辦法，將記錄間的間隙變成頁塊間的間隙。一般情況下，可以把記錄稱為邏輯記錄，而把邏輯記錄組合成的頁塊稱為物理記錄。對于上述例子，如果將100個記錄作為一個頁塊，則存放1000個記錄僅需長度為1000×0.05＋1000×0.6/100=56英寸顯然，采用分頁塊存儲法后，可以大大節(jié)省存儲空間，而且頁塊越大，浪費間隙的空間越小。但是這并不等于說頁塊越大越好，原因是采用分頁塊存儲后，內(nèi)外存數(shù)據(jù)交換的基本單位為頁塊，而不是記錄，因此需要在內(nèi)存中開辟一個數(shù)據(jù)緩沖區(qū)來暫存一個頁塊的內(nèi)容，以便進行輸入輸出操作。頁塊越大，則要求緩沖區(qū)越大，這勢必會過多地占用內(nèi)存空間，造成讀寫時間過長、出錯概率過大等一系列的問題，所以應適當?shù)剡x擇頁塊的大小。通常一個頁塊取1KB～8KB為宜。10.1.2磁盤存儲器1.磁盤存儲器的特性磁盤存儲器主要由磁盤組和磁盤驅(qū)動器組成。磁盤組由若干個盤片組成，每個盤片有上下兩個面，盤面上涂有光滑的磁性物質(zhì)。以6片盤組為例，由于最頂上和最底下盤片的外側面不能使用，所以總共只有10個面可用來保存信息，能夠存儲信息的盤面稱為記錄面。在記錄盤面上有許多稱為磁道的圓圈，信息就記載在磁道上。磁盤驅(qū)動器由主軸和讀／寫磁頭組成，每個盤面都配有一個讀／寫磁頭。圖10.2活動臂示意圖活動臂磁盤的磁頭是安裝在一個可活動臂上，隨著活動臂的移動，磁頭可在盤面上做同步的徑向移動，從一個磁道移到另一個磁道，當盤面高速旋轉，磁道在讀／寫頭下通過時，便可進行信息的讀寫。各記錄盤面上半徑相同的磁道合在一起稱為一個柱面，柱面上各磁道在同一磁頭位置下，即活動臂移動時，實際上是把這些磁頭從一個柱面移到另一個柱面。一個磁道內(nèi)還可以分為若干段，稱為扇段。因此，對磁盤存儲來說，由大到小的存儲單位是：盤片組，柱面，磁道，扇段。以IBM2314型磁盤為例，其參數(shù)為：20個記錄面／磁盤組，200個磁道／記錄面，7294字節(jié)／磁道。因此，整個盤片組的容量為：7294×200×200≈29MB。磁盤的存取時間主要取決于尋查時間和等待時間。磁盤以2400～3600r/min的速度旋轉，因此平均等待時間約為10ms～20ms，而平均尋查時間約為幾毫秒至幾十毫秒，這與CPU的處理速度相比較而言，仍是很慢的。因此，在討論外存的數(shù)據(jù)結構及其上的操作時，要盡量設法減少訪問外存的次數(shù)，以提高磁盤存取效率。2.分頁塊存儲法為了減少訪問外存的次數(shù)，一般采用把記錄組合成頁塊的方式來進行內(nèi)外存數(shù)據(jù)的交換。一個頁塊（簡稱塊）是磁盤上的一個物理記錄，通?？梢匀菁{多個邏輯記錄，內(nèi)存中設置的緩沖區(qū)應該與頁塊的大小相等。每次訪問記錄時，需要把一個頁塊讀入一個緩沖區(qū)或者把一個緩沖區(qū)的數(shù)據(jù)寫到一個頁塊。由于在這種方式下僅當一個頁塊中的記錄已處理完，接著將處理下一頁的記錄時才需要再次訪問外存，因而大大提高了處理效率。分頁塊存儲方法被廣泛采用。10.2外排序的基本方法10.2.1磁盤排序1.磁盤排序的例子假設磁盤上存有一文件，共有3600個記錄（A1,A2,A3600），頁塊長為200個記錄，供排序使用的緩沖區(qū)可提供容納600個記錄的空間，現(xiàn)要對該文件進行排序，排序過程可按如下步驟進行：第一步，每次將三個頁塊（600個記錄）由外存讀到內(nèi)存，進行內(nèi)排序，整個文件共得到6個初始順串R1~R6（每一個順串占三個頁塊），然后把它們寫回到磁盤上去，如圖10.3所示。圖10.3內(nèi)排序后得到的初始順串第二步圖10.46個順串的歸并過程從以上歸并過程可見，掃描遍數(shù)對于歸并過程所需要的時間起著關鍵的作用，在上例中，除了在內(nèi)排序形成初始順串時需作一遍掃描外，各順串的歸并還需遍掃描把6個長為600個記錄的順串歸并為3個長為1200個記錄的順串需要掃描一遍；把兩個長為1200個記錄的順串歸并為一個長為2400個記錄的順串需要掃描2/3遍,把一個長為2400個記錄的順串與另一個長為1200個記錄的順串歸并在一起，需要掃描一遍。2.多路歸并圖10.516個順串歸并的示例圖10.68路歸并程序的選擇樹(勝方樹)圖10.7勝方樹的修改圖10.8對應于圖10.6的敗方樹圖10.9敗方樹的修改3.初始順串的生成圖10.10初始順串的生成過程輸入文件:10,9,20,6,8,12,90,1714,22,7,24,15,16,11,100,13,18,26,38,30,25,50,28,110,21,40,19,…a輸入文件,每個記錄只列出其關鍵字值圖10.10初始順串的生成過程初始順串1:6,8,9,10,12,14,15,16,17,20,22,24,26,30,38,50,90,100,110初始順串2:7,11,13,18,21,25,28,40(b)生成的初始順串圖10.10初始順串的生成過程?包含8個記錄的敗方樹,并列出了新進入敗方樹的各記錄的結點位置及進入的次序,用符號√表示該記錄不屬于當前的初始順串10.2.2磁帶排序1.磁帶排序的例子設有一個文件包含3600個記錄，現(xiàn)在要對其進行排序，可供使用的磁帶機有四臺，分別為T1、T2、T3、T4，可供排序用的內(nèi)存空間包含存放600個記錄的空間以及一些必要的工作區(qū)設每個頁塊長為200個記錄。為了簡化討論，我們假定初始順串的生成是采用通常的內(nèi)排序方法實現(xiàn)的。這樣，一次可讀入三個頁塊，對其進行排序并作為一個順串輸出。我們將采用2路歸并的方法來實現(xiàn)順串的歸并，因而我們使用兩個輸入緩沖區(qū)和一個輸出緩沖區(qū)，每個緩沖區(qū)能容納200個記錄。排序過程的具體步驟如下（假設必要的磁帶反繞動作已經(jīng)隱含并設輸入文件在磁帶機T4上）：圖10.11磁帶排序過程2.非平衡歸并設初始順串的長度為度量單位，即規(guī)定初始順串的長度為1，用Sn來表示某臺磁帶機上有n個順串，每個順串的長度為S。假設初始順串有八個，則在T1上分配五個順串，在T2上分配三個順串，然后把T2上的三個順串與T1中的三個順串相歸并，得到三個長度為2的順串，將它們寫到T3上。下一步把T1中的兩個順串與T3中的兩個順串相歸并，得到兩個長度為3的順串，把它們寫到T2上。再下一步是把T3上一個長度為2的順串與