數(shù)據(jù)結(jié)構(gòu)第10章

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

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