第10章外部排序ppt課件

1、第十章第十章 外部排序外部排序10.1 外存信息的特性外存信息的特性10.2 外排序的基本方法外排序的基本方法10.3 總結(jié)與提高總結(jié)與提高10.1 外存信息的特性外存信息的特性存儲器存儲器內(nèi)部存儲器內(nèi)部存儲器（內(nèi)存）（內(nèi)存）外部存儲器外部存儲器（外存）（外存）順序存取設(shè)備磁帶存儲器）順序存取設(shè)備磁帶存儲器）直接存取設(shè)備磁盤存儲器）直接存取設(shè)備磁盤存儲器）內(nèi)存的存儲容量小，但工作速度高；外存的存儲容量大，內(nèi)存的存儲容量小，但工作速度高；外存的存儲容量大，但速度較低。但速度較低。10.1.1 磁帶存儲器磁帶存儲器優(yōu)點(diǎn)：存儲容量大，使用方便，價格便宜。優(yōu)點(diǎn)：存儲容量大，使用方便，價格便宜。 1.

2、特性：磁帶存儲器主要由磁帶、讀寫磁頭和磁帶驅(qū)動器特性：磁帶存儲器主要由磁帶、讀寫磁頭和磁帶驅(qū)動器組成，如下圖所示。組成，如下圖所示。目前常用的典型磁帶長目前常用的典型磁帶長24002400英尺，寬英尺，寬0.50.5英寸，厚英寸，厚0.0020.002英寸。磁帶表面上涂有磁性英寸。磁帶表面上涂有磁性材料，可分為七道或九道磁材料，可分為七道或九道磁帶。帶。 七道磁帶的每一橫排中有六個二進(jìn)制數(shù)據(jù)位和一個奇偶校七道磁帶的每一橫排中有六個二進(jìn)制數(shù)據(jù)位和一個奇偶校驗(yàn)位。九道磁帶的每一橫排中有八個二進(jìn)制數(shù)據(jù)位和一個驗(yàn)位。九道磁帶的每一橫排中有八個二進(jìn)制數(shù)據(jù)位和一個奇偶校驗(yàn)位。這樣的一排二進(jìn)制數(shù)據(jù)位組成一個

3、字節(jié)。奇偶校驗(yàn)位。這樣的一排二進(jìn)制數(shù)據(jù)位組成一個字節(jié)。 2. 分頁塊存儲方法分頁塊存儲方法磁帶存儲器是一種典型的順序存取設(shè)備。所謂順序存取，磁帶存儲器是一種典型的順序存取設(shè)備。所謂順序存取，就是將記錄在存儲器上一個接一個地依次存放，為得到第就是將記錄在存儲器上一個接一個地依次存放，為得到第i i個記錄，必須先讀第個記錄，必須先讀第i-1i-1個記錄。個記錄。 由于磁帶機(jī)不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，而是一種啟停設(shè)備，由于磁帶機(jī)不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，而是一種啟停設(shè)備，所以在啟停時間內(nèi)，不能對磁帶進(jìn)行正常讀寫，因此磁帶上所以在啟停時間內(nèi)，不能對磁帶進(jìn)行正常讀寫，因此磁帶上的信息通常分為若干記錄塊，塊與塊之間留

4、有一定的間隙，的信息通常分為若干記錄塊，塊與塊之間留有一定的間隙，該間隙一般為該間隙一般為1/41/43/43/4英寸。英寸。 由上可知，用磁帶存儲信息時需要在每段信息之間留有空隙，由上可知，用磁帶存儲信息時需要在每段信息之間留有空隙，且此空隙占用了大量的存儲空間且此空隙占用了大量的存儲空間 。為了減少存儲空間的浪。為了減少存儲空間的浪費(fèi)，通常采用把若干個記錄組合成頁塊進(jìn)行存儲的辦法，將費(fèi)，通常采用把若干個記錄組合成頁塊進(jìn)行存儲的辦法，將記錄間的間隙變成頁塊間的間隙。記錄間的間隙變成頁塊間的間隙。 10.1.2 磁盤存儲器磁盤存儲器優(yōu)點(diǎn)：既能進(jìn)行順序存取，又能進(jìn)行直接存取隨即存優(yōu)點(diǎn)：既能進(jìn)行順

5、序存取，又能進(jìn)行直接存取隨即存?。?，并且存取速度快。?。⑶掖嫒∷俣瓤?。 1. 磁盤存儲器的特性磁盤存儲器的特性 磁盤存儲器主要由磁盤組和磁盤驅(qū)動器組成。磁盤組磁盤存儲器主要由磁盤組和磁盤驅(qū)動器組成。磁盤組由若干個盤片組成，每個盤片有上下兩個面，盤面上涂有由若干個盤片組成，每個盤片有上下兩個面，盤面上涂有光滑的磁性物質(zhì)。光滑的磁性物質(zhì)。 盤面上能夠存儲信息的盤面稱為記錄面。在記錄盤面盤面上能夠存儲信息的盤面稱為記錄面。在記錄盤面上有許多稱為磁道的圓圈，信息就記載在磁道上。磁盤驅(qū)上有許多稱為磁道的圓圈，信息就記載在磁道上。磁盤驅(qū)動器由主軸和讀寫磁頭組成，每個盤面都配有一個讀動器由主軸和讀寫磁頭

6、組成，每個盤面都配有一個讀寫磁頭。寫磁頭。 磁盤可分為固定臂盤和活動臂盤兩種。固定臂盤的每個盤面磁盤可分為固定臂盤和活動臂盤兩種。固定臂盤的每個盤面的每一磁道上都有獨(dú)立的磁頭，它是固定不動的，專門負(fù)責(zé)的每一磁道上都有獨(dú)立的磁頭，它是固定不動的，專門負(fù)責(zé)讀寫某一磁道上的信息。讀寫某一磁道上的信息。 如圖：如圖：2. 分頁塊存儲法分頁塊存儲法 為了減少訪問外存的次數(shù)，為了減少訪問外存的次數(shù)，一般采用把記錄組合成頁塊的方一般采用把記錄組合成頁塊的方式來進(jìn)行內(nèi)外存數(shù)據(jù)的交換。一式來進(jìn)行內(nèi)外存數(shù)據(jù)的交換。一個頁塊簡稱塊是磁盤上的一個頁塊簡稱塊是磁盤上的一個物理記錄，通?？梢匀菁{多個個物理記錄，通常可以容

7、納多個邏輯記錄，內(nèi)存中設(shè)置的緩沖區(qū)邏輯記錄，內(nèi)存中設(shè)置的緩沖區(qū)應(yīng)該與頁塊的大小相等。每次訪應(yīng)該與頁塊的大小相等。每次訪問記錄時，需要把一個頁塊讀入問記錄時，需要把一個頁塊讀入一個緩沖區(qū)或者把一個緩沖區(qū)的一個緩沖區(qū)或者把一個緩沖區(qū)的數(shù)據(jù)寫到一個頁塊。數(shù)據(jù)寫到一個頁塊。 10.2 外排序的基本方法外排序的基本方法 最常用的外部排序方法是歸并排序法。這種方最常用的外部排序方法是歸并排序法。這種方法由兩個階段組成：第一階段是把文件逐段輸入到法由兩個階段組成：第一階段是把文件逐段輸入到內(nèi)存，用有效的內(nèi)排序方法對文件的各個段進(jìn)行排內(nèi)存，用有效的內(nèi)排序方法對文件的各個段進(jìn)行排序，經(jīng)排序的文件段稱為順串或歸并

8、段），當(dāng)它序，經(jīng)排序的文件段稱為順串或歸并段），當(dāng)它們生成后立即寫到外存上，這樣在外存上就形成了們生成后立即寫到外存上，這樣在外存上就形成了許多初始順串；第二階段是對這些順串用某種歸并許多初始順串；第二階段是對這些順串用某種歸并方法如方法如2 2路歸并法進(jìn)行多邊歸并，使順串的長度路歸并法進(jìn)行多邊歸并，使順串的長度逐漸由小至大，直至變成一個順串，即整個文件有逐漸由小至大，直至變成一個順串，即整個文件有序?yàn)橹?。序?yàn)橹埂?10.2.1 磁盤排序磁盤排序1.1.例子：假設(shè)磁盤上存有一文件，共有例子：假設(shè)磁盤上存有一文件，共有36003600個記錄個記錄A1,A2,A3600A1,A2,A3600），頁

9、塊長為），頁塊長為200200個記錄，供排序使用的個記錄，供排序使用的緩沖區(qū)可提供容納緩沖區(qū)可提供容納600600個記錄的空間，現(xiàn)要對該文件進(jìn)行排個記錄的空間，現(xiàn)要對該文件進(jìn)行排序，排序過程可按如下步驟進(jìn)行：序，排序過程可按如下步驟進(jìn)行： 第一步：每次將三個頁塊第一步：每次將三個頁塊600個記錄由外存讀到內(nèi)存，個記錄由外存讀到內(nèi)存，進(jìn)行內(nèi)排序，整個文件共得到進(jìn)行內(nèi)排序，整個文件共得到6個初始順串個初始順串R1R6 （每一個（每一個順串占三個頁塊），然后把它們寫回到磁盤上去。內(nèi)排序順串占三個頁塊），然后把它們寫回到磁盤上去。內(nèi)排序后得到的初始順串見后得到的初始順串見p260的圖的圖10.3所示。

10、所示。第二步：將供內(nèi)排序使用的內(nèi)存緩沖區(qū)分為三塊相等的部分第二步：將供內(nèi)排序使用的內(nèi)存緩沖區(qū)分為三塊相等的部分即每塊可容納即每塊可容納200個記錄），其中兩塊作為輸入緩沖區(qū)，一個記錄），其中兩塊作為輸入緩沖區(qū)，一塊作為輸出緩沖區(qū)，然后對各順串進(jìn)行兩路歸并。歸并過程塊作為輸出緩沖區(qū)，然后對各順串進(jìn)行兩路歸并。歸并過程見見p261的圖的圖10.4所示。所示。 2. 多路歸并多路歸并一般說來，如果初始順串有一般說來，如果初始順串有m m個，則如圖個，則如圖10.410.4所示那樣的歸所示那樣的歸并樹就有并樹就有l(wèi)og2m+1log2m+1層，要對數(shù)據(jù)進(jìn)行層，要對數(shù)據(jù)進(jìn)行l(wèi)og2mlog2m遍掃描。采

11、用遍掃描。采用多路歸并可以減少掃描遍數(shù)，如下圖。多路歸并可以減少掃描遍數(shù)，如下圖。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 圖10.5 16個順串歸并的示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 在在k k路歸并中，為了確定下一個要輸出的記錄，就需要路歸并中，為了確定下一個要輸出的記錄，就需要在在k k個記錄中尋找關(guān)鍵字值最小的那個記錄，這要比個記錄中尋找關(guān)鍵字值最小的那個記錄，這要比2 2路歸并路歸并復(fù)雜些。如果逐個比較每個順串的待選記錄，從而選出一個復(fù)雜些。如果逐個比較每個順串的待選記錄，從而選出一個關(guān)鍵字值最小

12、的記錄，則每選取一個記錄需要進(jìn)行關(guān)鍵字值最小的記錄，則每選取一個記錄需要進(jìn)行k-1k-1次比次比較。為了減少這個代價，我們可采用下面介紹的選擇樹的方較。為了減少這個代價，我們可采用下面介紹的選擇樹的方法來實(shí)現(xiàn)法來實(shí)現(xiàn)k k路歸并。路歸并。 選擇樹是一種完全二叉樹，下圖顯示了選擇樹是一種完全二叉樹，下圖顯示了8路歸并的選擇路歸并的選擇樹，其中葉結(jié)點(diǎn)為各順串在歸并過程中的當(dāng)前記錄圖中樹，其中葉結(jié)點(diǎn)為各順串在歸并過程中的當(dāng)前記錄圖中標(biāo)出了它們各自的關(guān)鍵字值），其它每個結(jié)點(diǎn)都代表其兩標(biāo)出了它們各自的關(guān)鍵字值），其它每個結(jié)點(diǎn)都代表其兩個子結(jié)點(diǎn)中關(guān)鍵字值較小的一個。因此根結(jié)點(diǎn)是樹中個子結(jié)點(diǎn)中關(guān)鍵字值較小的

13、一個。因此根結(jié)點(diǎn)是樹中的最小結(jié)點(diǎn)，即為下一個要輸出的記錄結(jié)點(diǎn)。這種選擇樹的最小結(jié)點(diǎn)，即為下一個要輸出的記錄結(jié)點(diǎn)。這種選擇樹的構(gòu)造可比作一種淘汰制的體育比賽，其中獲勝者便是那的構(gòu)造可比作一種淘汰制的體育比賽，其中獲勝者便是那個具有較小關(guān)鍵字值的記錄。個具有較小關(guān)鍵字值的記錄。 在非葉結(jié)點(diǎn)中，可以只存關(guān)鍵字值及指向相應(yīng)記錄的指針，在非葉結(jié)點(diǎn)中，可以只存關(guān)鍵字值及指向相應(yīng)記錄的指針，而不必存放整個記錄內(nèi)容。由于非葉結(jié)點(diǎn)總是代表優(yōu)勝者，而不必存放整個記錄內(nèi)容。由于非葉結(jié)點(diǎn)總是代表優(yōu)勝者，所以可以把這種樹稱為勝方樹。所以可以把這種樹稱為勝方樹。 圖圖10.6 8路歸并程序的選擇樹勝方樹）路歸并程序的選擇

14、樹勝方樹）圖圖10.7 勝方樹的修改勝方樹的修改 由上述過程可見，要選取關(guān)鍵字值最小的記錄，只有第由上述過程可見，要選取關(guān)鍵字值最小的記錄，只有第一個需要進(jìn)行一個需要進(jìn)行m-1次比較建立勝方樹），此后每個只要進(jìn)行次比較建立勝方樹），此后每個只要進(jìn)行l(wèi)og2m次比較即可，這是由于樹中保持了以前的比較結(jié)果。次比較即可，這是由于樹中保持了以前的比較結(jié)果。 勝方樹的缺點(diǎn)：在選取一個記錄之后重構(gòu)選擇樹的勝方樹的缺點(diǎn)：在選取一個記錄之后重構(gòu)選擇樹的修改工作比較麻煩，既要查找兄弟結(jié)點(diǎn)，又要查找修改工作比較麻煩，既要查找兄弟結(jié)點(diǎn)，又要查找父結(jié)點(diǎn)。為了減少重構(gòu)選擇樹的代價，可以采用敗父結(jié)點(diǎn)。為了減少重構(gòu)選擇樹的

15、代價，可以采用敗方樹的辦法來簡化重構(gòu)的過程。方樹的辦法來簡化重構(gòu)的過程。 敗方樹：就是在比賽樹選擇樹中，每個非葉結(jié)敗方樹：就是在比賽樹選擇樹中，每個非葉結(jié)點(diǎn)均存放其兩個子結(jié)點(diǎn)中的敗方。點(diǎn)均存放其兩個子結(jié)點(diǎn)中的敗方。 建立過程是：從葉結(jié)點(diǎn)開始分別對每兩個兄弟結(jié)點(diǎn)進(jìn)行比較，建立過程是：從葉結(jié)點(diǎn)開始分別對每兩個兄弟結(jié)點(diǎn)進(jìn)行比較，敗者較大的關(guān)鍵字值存放在父結(jié)點(diǎn)中，而勝者繼續(xù)參加敗者較大的關(guān)鍵字值存放在父結(jié)點(diǎn)中，而勝者繼續(xù)參加下一輪的比較，最終結(jié)果是每個下一輪的比較，最終結(jié)果是每個“選手都停在自己失敗的選手都停在自己失敗的“比賽場上。在根結(jié)點(diǎn)之上有一個附加的結(jié)點(diǎn)，存放全局比賽場上。在根結(jié)點(diǎn)之上有一個附加

16、的結(jié)點(diǎn)，存放全局優(yōu)勝者。優(yōu)勝者。 圖圖10.8 對應(yīng)于圖對應(yīng)于圖10.6的敗方樹的敗方樹圖圖10.9 敗方樹的修改敗方樹的修改 在敗方樹中，當(dāng)輸出全局優(yōu)勝者記錄之后，對樹的修改在敗方樹中，當(dāng)輸出全局優(yōu)勝者記錄之后，對樹的修改比勝方樹容易一些。修改過程如下：將新進(jìn)入樹的葉結(jié)點(diǎn)與比勝方樹容易一些。修改過程如下：將新進(jìn)入樹的葉結(jié)點(diǎn)與父結(jié)點(diǎn)進(jìn)行比較，大的存放在父結(jié)點(diǎn)，小的與上一級父結(jié)點(diǎn)父結(jié)點(diǎn)進(jìn)行比較，大的存放在父結(jié)點(diǎn)，小的與上一級父結(jié)點(diǎn)再進(jìn)行比較，此過程不斷進(jìn)行，直至到根，最后把新的全局再進(jìn)行比較，此過程不斷進(jìn)行，直至到根，最后把新的全局優(yōu)勝者存放到附加的結(jié)點(diǎn)優(yōu)勝者存放到附加的結(jié)點(diǎn) 。 采用多路歸并可

17、以減少對數(shù)據(jù)的掃描遍數(shù)從而減少了輸采用多路歸并可以減少對數(shù)據(jù)的掃描遍數(shù)從而減少了輸入輸出量。但也應(yīng)該看到，若歸并的路數(shù)入輸出量。但也應(yīng)該看到，若歸并的路數(shù)k k增大時，緩沖增大時，緩沖區(qū)就要設(shè)置得比較大。區(qū)就要設(shè)置得比較大。 3. 初始順串的生成初始順串的生成其生成過程見下圖。其生成過程見下圖。輸入文件輸入文件10，9，20，6，8，12，90，17，14，22，7，24，15，16，11，100，13，18，26，38，30，25，50，28，110，21，40，19，(a)輸入文件，每個記錄只列出其關(guān)鍵字值輸入文件，每個記錄只列出其關(guān)鍵字值初始順串初始順串1：6，8，9，10，12，14,

18、15,16, 17,20,22,24,26,30,38， 50,90,100,110初始順串初始順串2:7,11,13,18,21,25,28,40(b)生成的初始順串生成的初始順串(c) 包含包含8個記錄的敗方樹，并列出個記錄的敗方樹，并列出了新進(jìn)入敗方樹的各記錄的結(jié)點(diǎn)位了新進(jìn)入敗方樹的各記錄的結(jié)點(diǎn)位置及進(jìn)入的次序，用符號置及進(jìn)入的次序，用符號表示該表示該記錄不屬于當(dāng)前的初始順川。記錄不屬于當(dāng)前的初始順川。圖圖10.10 初始順串的生成過程初始順串的生成過程10.2.2 磁帶排序磁帶排序 磁帶排序過程基本上與磁盤排序過程相同。首先對待排磁帶排序過程基本上與磁盤排序過程相同。首先對待排序文件的

19、各段進(jìn)行內(nèi)排序，產(chǎn)生所有的初始順串，再把它們序文件的各段進(jìn)行內(nèi)排序，產(chǎn)生所有的初始順串，再把它們寫回到磁帶上，然后對這些順串進(jìn)行反復(fù)歸并，直至成為一寫回到磁帶上，然后對這些順串進(jìn)行反復(fù)歸并，直至成為一個順串即為有序文件為止。個順串即為有序文件為止。 磁帶排序需充分考慮順串的分布情況，因?yàn)榇艓琼樞虼艓判蛐璩浞挚紤]順串的分布情況，因?yàn)榇艓琼樞虼嫒〉模判蜻^程中尋找或等待的時間較長，所以各順串分存取的，排序過程中尋找或等待的時間較長，所以各順串分布在不同磁帶和同一磁帶的不同位置對排序效率影響極大。布在不同磁帶和同一磁帶的不同位置對排序效率影響極大。 1. 磁帶排序的例子：磁帶排序的例子： 設(shè)有

20、一個文件包含設(shè)有一個文件包含36003600個記錄，現(xiàn)在要對其進(jìn)行排序，個記錄，現(xiàn)在要對其進(jìn)行排序，可供使用的磁帶機(jī)有四臺，分別為可供使用的磁帶機(jī)有四臺，分別為T1T1、T2T2、T3T3、T4T4，可供排，可供排序用的內(nèi)存空間包含存放序用的內(nèi)存空間包含存放600600個記錄的空間以及一些必要的工個記錄的空間以及一些必要的工作區(qū)。設(shè)每個頁塊長為作區(qū)。設(shè)每個頁塊長為200200個記錄。為了簡化討論，我們假定個記錄。為了簡化討論，我們假定初始順串的生成是采用通常的內(nèi)排序方法實(shí)現(xiàn)的。這樣，一初始順串的生成是采用通常的內(nèi)排序方法實(shí)現(xiàn)的。這樣，一次可讀入三個頁塊，對其進(jìn)行排序并作為一個順串輸出。我次可讀

21、入三個頁塊，對其進(jìn)行排序并作為一個順串輸出。我們將采用們將采用2 2路歸并的方法來實(shí)現(xiàn)順串的歸并，因而我們使用兩路歸并的方法來實(shí)現(xiàn)順串的歸并，因而我們使用兩個輸入緩沖區(qū)和一個輸出緩沖區(qū)，每個緩沖區(qū)能容納個輸入緩沖區(qū)和一個輸出緩沖區(qū)，每個緩沖區(qū)能容納200200個記個記錄。錄。 排序過程的具體步驟如下排序過程的具體步驟如下 ：第一步：把輸入文件分段每段包含第一步：把輸入文件分段每段包含600個記錄讀入內(nèi)存并個記錄讀入內(nèi)存并進(jìn)行內(nèi)排序，生成初始順串，然后將這些順串輪流寫到磁帶進(jìn)行內(nèi)排序，生成初始順串，然后將這些順串輪流寫到磁帶機(jī)機(jī)T1和和T2上。上。 見圖見圖10.11(a)。圖圖10.11 磁帶

22、排序過程磁帶排序過程第二步：采用第二步：采用2路歸并法對路歸并法對T1上的各順串與上的各順串與T2上的上的各順串進(jìn)行歸并，并把所產(chǎn)生的較大順串輪流分布各順串進(jìn)行歸并，并把所產(chǎn)生的較大順串輪流分布到到T3和和T4上若輸入文件帶需要保留，則在第一步上若輸入文件帶需要保留，則在第一步完成后把輸入文件帶從完成后把輸入文件帶從T4上卸下來，換上工作帶）。上卸下來，換上工作帶）。見圖見圖10.11(b)。第三步：把第三步：把T3上的順串上的順串1和和T4上的順串上的順串2進(jìn)行合并，進(jìn)行合并，并將結(jié)果放到并將結(jié)果放到T1上。見圖上。見圖10.11(c)。第四步：把第四步：把T1T1上的順串上的順串1 1和和

23、T3T3上的順串上的順串3 3合并，并把合并，并把結(jié)果放到結(jié)果放到T2T2上，即為所要求的有序文件。上，即為所要求的有序文件。 2. 非平衡歸并非平衡歸并k路平衡歸并的特點(diǎn)是：把要?dú)w并的順串平衡均勻地路平衡歸并的特點(diǎn)是：把要?dú)w并的順串平衡均勻地分布到分布到k臺輸入帶上。這樣，為了避免對數(shù)據(jù)進(jìn)行再臺輸入帶上。這樣，為了避免對數(shù)據(jù)進(jìn)行再分配的掃描，就需要分配的掃描，就需要2k臺磁帶機(jī)，現(xiàn)采用非平衡歸臺磁帶機(jī)，現(xiàn)采用非平衡歸并，即不同輸入帶上的順串個數(shù)不同，適當(dāng)?shù)貙槻?，即不同輸入帶上的順串個數(shù)不同，適當(dāng)?shù)貙槾M(jìn)行非均勻分配，就可以用不到串進(jìn)行非均勻分配，就可以用不到2k臺磁帶機(jī)來實(shí)臺磁帶機(jī)來實(shí)現(xiàn)

24、現(xiàn) k路歸并。路歸并。 用用k+1k+1臺磁帶機(jī)便可取得臺磁帶機(jī)便可取得k k路歸并的效果，我路歸并的效果，我們以三臺磁帶機(jī)們以三臺磁帶機(jī)T1T1、T2T2、T3T3實(shí)現(xiàn)實(shí)現(xiàn)2 2路歸并為例來說路歸并為例來說明這個方法。明這個方法。 我們設(shè)初始順串的長度為度量單位，即規(guī)定初我們設(shè)初始順串的長度為度量單位，即規(guī)定初始順串的長度為始順串的長度為1 1，用，用SnSn來表示某臺磁帶機(jī)上有來表示某臺磁帶機(jī)上有n n個個順串，每個順串的長度為順串，每個順串的長度為S S。 步驟步驟 T1 T2 T3 說明說明初始分布初始分布 15 13 第一步后第一步后 12 23 歸并到歸并到T3第二步后第二步后 3

25、2 21 歸并歸并到到T2第三步后第三步后 51 31 歸并到歸并到T1第四步后第四步后 81 歸并到歸并到T3圖圖10.12 采用非平衡分布法用三臺磁帶機(jī)實(shí)現(xiàn)采用非平衡分布法用三臺磁帶機(jī)實(shí)現(xiàn)2路歸并路歸并 討論如何確定順串初始分布的問題討論如何確定順串初始分布的問題 為了確定初始分布，就得從最后一步往前推。假設(shè)有為了確定初始分布，就得從最后一步往前推。假設(shè)有n步，步，我們希望我們希望n步之后在步之后在T1上正好有一個順串，而在上正好有一個順串，而在T2和和T3上沒上沒有順串。要做到這點(diǎn)，則必須把有順串。要做到這點(diǎn)，則必須把T2中的一個順串與中的一個順串與T3中的一中的一個順串加以歸并來得到這

26、種順串，并且個順串加以歸并來得到這種順串，并且T2和和T3上沒有別的順上沒有別的順串，所以在第串，所以在第n-1步后，步后，T2和和T3上應(yīng)各有一個順串，上應(yīng)各有一個順串，T2上的上的順串是從順串是從T1和和T3中各取一個順串加以歸并后得到，因而，在中各取一個順串加以歸并后得到，因而，在第第n-2步后，在步后，在T1上應(yīng)有一個順串，在上應(yīng)有一個順串，在T3上應(yīng)有兩個順串，上應(yīng)有兩個順串，就這樣一步一步往前推。就這樣一步一步往前推。下圖顯示了這個前推得過程。下圖顯示了這個前推得過程。 步驟步驟 T1 T2 T3 n 1 0 0 n-1 0 1 1 n-2 1 0 2 n-3 3 2 0 n-4

27、0 5 3 n-5 5 0 8 n-6 13 8 0三帶三帶2路歸并的順串分布路歸并的順串分布 步驟步驟 T1 T2 T3 T4 n 1 0 0 0 n-1 0 1 1 1 n-2 1 0 2 2 n-3 3 2 0 4 n-4 7 6 4 0 n-5 0 13 11 7 n-6 13 0 24 20 n-7 37 24 0 44 n-8 81 68 44 0 四帶四帶3路歸并的順串分布路歸并的順串分布10.3 總結(jié)與提高總結(jié)與提高10.3.1 主要知識點(diǎn)主要知識點(diǎn) 基本概念：基本概念： 外部排序：待排序的記錄數(shù)外部排序：待排序的記錄數(shù)n很大，內(nèi)存容納不下，必須很大，內(nèi)存容納不下，必須借用外部

28、存儲器才能完成的排序過程。借用外部存儲器才能完成的排序過程。 外存一般分為兩類：順序存取設(shè)備如磁帶存儲器）、直外存一般分為兩類：順序存取設(shè)備如磁帶存儲器）、直接存取設(shè)備如磁盤存儲器）。接存取設(shè)備如磁盤存儲器）。 磁帶的存取時間主要用在定位上，讀寫頭與所需信息的磁帶的存取時間主要用在定位上，讀寫頭與所需信息的距離越遠(yuǎn)，定位時間就越長。距離越遠(yuǎn)，定位時間就越長。 磁盤存儲器硬盤特點(diǎn)：直接存取隨機(jī)存取），高速。磁盤存儲器硬盤特點(diǎn)：直接存取隨機(jī)存取），高速。 磁盤存儲單位：盤片組，柱面，磁道，扇段。磁盤存儲單位：盤片組，柱面，磁道，扇段。 外存中把若干個記錄邏輯記錄組合成頁塊物理記錄外存中把若干個記錄邏輯記錄組合成頁塊物理記錄進(jìn)行存儲。頁塊進(jìn)行存儲。頁塊1KB8KB是內(nèi)外存數(shù)據(jù)交換