教案數(shù)據(jù)結(jié)構(gòu)d11

1、第11章 外部排序第 2 頁為什么需要文件管理和外排序？文件結(jié)構(gòu)（file structure）對于在外存中存儲的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)就稱為文件結(jié)構(gòu)數(shù)據(jù)量太大不可能同時把它們放到內(nèi)存中需要把全部數(shù)據(jù)放到磁盤中文件的各種運(yùn)算外排序是針對磁盤文件所進(jìn)行的排序操作提高文件存儲效率和運(yùn)算效率11.1 外存信息的存取第 3 頁主存儲器和外存儲器主存儲器 ( primary memory 或 main memory，簡稱內(nèi)存/主存) 隨機(jī)訪問存儲器( RAM )高速緩存( cache )視頻存儲器( video memory ) 外存儲器 ( peripheral storage 或 secondary st

2、orage，簡稱外存) 硬盤 / 軟盤 / 磁帶 / U盤11.1 外存信息的存取第 4 頁外存的特點(diǎn)優(yōu)點(diǎn)：永久存儲能力、便攜性 缺點(diǎn)：訪問時間長訪問磁盤中的數(shù)據(jù)比訪問內(nèi)存慢五六個數(shù)量級。 因此，在對外存的數(shù)據(jù)結(jié)構(gòu)及其上的操作時，必須遵循的基本原則是：盡量減少訪外次數(shù)！ 11.1 外存信息的存取第 5 頁磁盤的物理結(jié)構(gòu)11.1 外存信息的存取第 6 頁磁盤磁片的組織11.1 外存信息的存取第 7 頁磁道的組織（交錯法）11.1 外存信息的存?。╝）沒有扇區(qū)交錯 （b）以3為交錯因子第 8 頁磁盤的存取步驟選定某個盤片組選定某個柱面這需要把磁頭移動到該柱面 ，這個移動過程稱為尋道( seek )

3、 確定磁道 確定所要讀寫的數(shù)據(jù)在磁盤上的準(zhǔn)確位置這段時間一般稱為旋轉(zhuǎn)延遲( rotational delay 或者rotational latency )真正進(jìn)行讀寫11.1 外存信息的存取第 9 頁磁盤的存取時間11.1 外存信息的存取間時輸傳磁道尋道時間磁臂等待時間數(shù)據(jù)信息磁盤旋轉(zhuǎn)方向第 10 頁磁盤的存取時間磁盤訪問時間主要由尋道時間、旋轉(zhuǎn)延遲時間和數(shù)據(jù)傳輸時間組成。 尋道時間（Seek time）tseek：是移動磁盤臂，定位到正確磁道所需的時間。旋轉(zhuǎn)延遲時間tla：是等待被存取的扇區(qū)出現(xiàn)在讀寫頭下所需的時間。傳輸時間twm：是傳輸一個字符的時間。TI/O=tseek + tla +

4、twm11.1 外存信息的存取第 11 頁磁帶運(yùn)行示意11.1 外存信息的存取 磁帶卷在一個卷盤上，運(yùn)行時磁帶經(jīng)過讀寫磁頭，把磁帶上的信息讀入計(jì)算機(jī)，或把計(jì)算機(jī)中的信息寫在磁帶上。第 12 頁外存文件的組織 文件是一些記錄的集合，每個記錄可由一個或多個數(shù)據(jù)項(xiàng)組成。 數(shù)據(jù)項(xiàng)也稱為字段，或?qū)傩浴?1.1 外存信息的存取職工號姓名性別職務(wù)婚姻狀況工資156張東男程序員未婚7800860李珍女分析員已婚8900510趙莉女程序員未婚6900950陳萍女程序員未婚6200620周力男分析員已婚10300第 13 頁邏輯文件對高級程序語言的編程人員而言，磁盤中可以隨機(jī)訪問的文件被當(dāng)作一段連續(xù)的字節(jié)，且可將

5、這些字節(jié)結(jié)合起來構(gòu)成記錄，這種文件被稱為邏輯文件。物理文件實(shí)際存儲在磁盤中的物理文件通常不是一段連續(xù)的字節(jié)，而是成塊地分布在整個磁盤中。文件管理器是操作系統(tǒng)的一部分，當(dāng)應(yīng)用程序請求從邏輯文件中讀取數(shù)據(jù)時，它將這些邏輯位置映射為磁盤中具體的物理位置。11.1 外存信息的存取第 14 頁文件的邏輯結(jié)構(gòu)文件是記錄的集合。當(dāng)一個文件的各個記錄按照某種次序排列起來時，各記錄間就自然地形成了一種線性關(guān)系。 因而，文件可看成是一種線性結(jié)構(gòu)。 11.1 外存信息的存取文件的物理結(jié)構(gòu)順序結(jié)構(gòu)順序文件 計(jì)算尋址結(jié)構(gòu)散列文件 帶索引的結(jié)構(gòu)帶索引文件 第 15 頁文件的物理結(jié)構(gòu)順序文件：記錄按照自然次序依次存儲存取第

6、 i 個記錄之前，必須存取第 i-1 個記錄新記錄只能插在文件尾部更新文件中的數(shù)據(jù)必須將整個文件復(fù)制一遍散列文件： 通過散列函數(shù)和沖突處理索引文件：帶有按關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)進(jìn)行索引的文件虛擬存儲存取方式VSAM：索引順序文件，用B+樹作為動態(tài)索引樹11.1 外存信息的存取第 16 頁文件上的操作檢索：在文件中尋找滿足一定條件的記錄 修改：對記錄中某些數(shù)據(jù)值進(jìn)行修改。若對關(guān)鍵字進(jìn)行修改，就相當(dāng)于刪除加插入。插入：向文件中增加一個新記錄。 刪除：從文件中刪去一個記錄 。排序 ：對指定好的數(shù)據(jù)項(xiàng)，按其值的大小把文件中的記錄排成序列。常用的是按關(guān)鍵字的排序。 11.1 外存信息的存取第 17 頁外排序( e

7、xternal sort )外存設(shè)備上（文件）的排序技術(shù)由于文件很大，無法把整個文件的所有記錄同時調(diào)入內(nèi)存中進(jìn)行排序，即無法進(jìn)行內(nèi)排序 外部排序算法的主要目標(biāo)：盡量減少讀寫磁盤的次數(shù) 11.2 外部排序的方法第 18 頁磁盤排序過程文件分成若干盡可能長的初始順串；逐步歸并歸順串，最后形成一個已排序的文件。順串 用某種有效的內(nèi)排序方法對文件的各段進(jìn)行初始排序，這些經(jīng)過排序的段通常稱為順串(run) ，它們生成之后立即被寫回到外存上。11.2 外部排序的方法第 19 頁外排序通常由兩個相對獨(dú)立的階段組成：文件形成盡可能長的初始順串逐趟歸并順串，最后形成對整個數(shù)據(jù)文件的排列文件外排序所需要的時間由三

8、部分組成：內(nèi)部排序所需要的時間外存信息讀寫所需要的時間內(nèi)部歸并所需要的時間 11.2 外部排序的方法第 20 頁外排序的時間開銷外排序總時間=內(nèi)部排序產(chǎn)生初始順段 時間 +外存信息讀寫時間 +內(nèi)部歸并所需時間 = m*tis + d*tio + s*utmg其中：tis：得到一個初始?xì)w并段進(jìn)行內(nèi)部排序所需時間m：經(jīng)過內(nèi)排序后得到的初始?xì)w并段的數(shù)量tio：進(jìn)行一個外存讀寫的時間d：總的讀寫次數(shù)utmg：對 u 個記錄進(jìn)行內(nèi)部歸并所需時間s：歸并的趟數(shù)11.2 外部排序的方法第 21 頁減少外存信息的讀寫次數(shù)是提高外部排序效率的關(guān)鍵 對同一個文件而言，進(jìn)行外排序所需讀寫外存的次數(shù)與歸并趟數(shù)有關(guān)系假

9、設(shè)有m個初始順串，每次對k個順串進(jìn)行歸并，歸并趟數(shù)為logkm為了減少歸并趟數(shù)，可以從兩個方面著手：減少初始順串的個數(shù)m增加歸并的順串?dāng)?shù)量k11.2 外部排序的方法第 22 頁磁盤排序基本做法的描述假定文件有4500個記錄：R1, R2, , R4500。磁盤上 1 塊（如 1 個扇區(qū)）的尺寸是250個記錄，該文件總共需用磁盤的 18 個扇區(qū)。內(nèi)存可供用于排序的空間是 750 個記錄大小。排序過程如下： 每次從磁盤讀入 3 塊（750個記錄）到內(nèi)存，利用內(nèi)排序算法將它們排好序，然后寫回磁盤。這樣，磁盤上就得到了6個初始有序段A1、A2、A6。 11.2 外部排序的方法初始有序段A11750有序

10、段A27511500有序段A315012250有序段A422513000有序段A530013750有序段A637514500第 23 頁把內(nèi)存按 250 個記錄的長度分成三部分：兩部分為輸入緩沖區(qū)，一部分為輸出緩沖區(qū)。先對 A1 和 A2 進(jìn)行歸并：先將每段的一塊（250個有序記錄）讀到內(nèi)存的兩個輸入緩沖區(qū)，用歸并排序算法實(shí)施排序。邊排序，邊把結(jié)果寫到輸出緩沖區(qū)。輸出緩沖區(qū)滿時，寫入磁盤；當(dāng)一個輸入緩沖區(qū)的內(nèi)容歸并完騰空時，將該有序段的下一塊讀入該緩沖區(qū)繼續(xù)歸并。這樣繼續(xù)，直到把 A1 和 A2 全歸并完畢，磁盤里出現(xiàn)一個含1500個記錄的新有序段。11.2 外部排序的方法第 24 頁完成一次

11、歸并后，對A3和A4、A5和A6實(shí)施相同歸并。整個文件經(jīng)一趟歸并，在磁盤上得到三個各含1500記錄的有序段。11.2 外部排序的方法初始有序段A11750有序段A27511500有序段A315012250有序段A422513000有序段A530013750有序段A6375145003000個記錄第2趟歸并1500個記錄1500個記錄1500個記錄第1趟歸并4500個記錄第3趟歸并繼續(xù)進(jìn)行歸并：第 2 趟，第 3 趟。第 25 頁分析在一切相同的條件下，如果把例中的 2-路歸并改變成 3-路或 6-路（當(dāng)然，這時所需要的內(nèi)存緩沖區(qū)個數(shù)將會變化），那么總的讀寫磁盤次數(shù)就會下降。11.2 外部排序的

12、方法歸并路數(shù) 總讀寫磁盤次數(shù) 歸并趟數(shù) 2 132 3 3 108 2 6 72 1第 26 頁k-路歸并k-路歸并時，在 k 個關(guān)鍵字中選最小值。通?？刹捎弥苯舆x擇排序方法，對關(guān)鍵字做 k-1次比較。問題：在直接選擇排序時許多關(guān)鍵字間進(jìn)行了不止一次的重復(fù)比較，導(dǎo)致時間的浪費(fèi)。解決辦法：若在選擇最小者時，將比較結(jié)果保留下來，后面需要時加以利用，就可減少比較次數(shù)，減少磁盤輸入/輸出所耗費(fèi)的時間，從而使排序的速度提高。11.2 外部排序的方法第 27 頁選擇樹選擇樹是一棵二叉樹，該樹中的分支結(jié)點(diǎn)是該結(jié)點(diǎn)兩個孩子中的較小者，根結(jié)點(diǎn)是這棵樹各葉結(jié)點(diǎn)中的最小者。11.2 外部排序的方法109206899

13、01769681768 為選擇次小者，可把該記錄原始位置（葉結(jié)點(diǎn)）設(shè)成一個大于所有關(guān)鍵字的值“+”。進(jìn)行輸出-調(diào)整。最小值+由下往上調(diào)整2098k=8時第 28 頁選擇樹為選取下一個最小者，只需對根結(jié)點(diǎn)到該葉結(jié)點(diǎn)所經(jīng)路徑上的各結(jié)點(diǎn)與其左或右兄弟進(jìn)行比較和適當(dāng)?shù)恼{(diào)整即可，其他結(jié)點(diǎn)保持原樣。11.2 外部排序的方法10920+899017892081798+9k=8時輸出8，并調(diào)整99輸出9，并調(diào)整+10109輸出9，并調(diào)整+1710第 29 頁勝者樹：結(jié)點(diǎn)記錄勝者信息利用選擇樹的思想，對有序段進(jìn)行k-路歸并。樹的每個葉結(jié)點(diǎn)對應(yīng)一個輸入緩沖區(qū)，它總是各有序段在歸并過程中的當(dāng)前關(guān)鍵字，分支結(jié)點(diǎn)是它的

14、兩個孩子結(jié)點(diǎn)中鍵值較小的那個。根結(jié)點(diǎn)是樹中鍵最小的。輸出根結(jié)點(diǎn)后，用該記錄所在有序段的下一個關(guān)鍵字填補(bǔ)它的位置，并作適當(dāng)調(diào)整。這樣的調(diào)整不會涉及到整棵樹，而只需考慮從根結(jié)點(diǎn)到該位置的路徑上的各個結(jié)點(diǎn)。11.2 外部排序的方法第 30 頁勝者樹當(dāng)前8個待歸并有序段的前3個關(guān)鍵字值：10, 15, 19 9, 20, 38 20, 22, 34 6, 15, 258, 17, 50 18, 21, 44 90, 95, 108 24, 32, 6611.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.17

15、50.2144.95108.3266.第 31 頁勝者樹對 8 個并有序段進(jìn)行一次歸并。先輸出根結(jié)點(diǎn)上關(guān)鍵字為 6 的記錄，它原位于最底層編號為 11 的葉結(jié)點(diǎn)處，用15頂替。局部調(diào)整 。11.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.1598第 32 頁勝者樹輸出原位于編號為12的記錄8，并用它后面值為“17”的關(guān)鍵字進(jìn)行頂替。做適當(dāng)調(diào)整.11.2 外部排序的方法1092068189024696824681234567891011121314

16、151519.2038.2234.1525.1750.2144.95108.3266.1525.159850.171717938.20101010輸出 9，再繼續(xù)進(jìn)行調(diào)整.第 33 頁勝者樹：實(shí)現(xiàn)勝者樹是完全二叉樹，算法實(shí)現(xiàn)時，采用順序存儲結(jié)構(gòu)保存。非葉結(jié)點(diǎn)保存的是“勝者”在樹中對應(yīng)結(jié)點(diǎn)的下標(biāo)（編號）。11.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.9111215111211保存：勝者對應(yīng)葉結(jié)點(diǎn)的編號第 34 頁敗者樹：結(jié)點(diǎn)記錄敗者信息敗者樹是一棵有 k

17、 個葉結(jié)點(diǎn)的二叉樹，分支結(jié)點(diǎn)存放該結(jié)點(diǎn)兩個孩子中的較大者（敗者），而讓較小者（勝者）參加上一層的比較，即勝者“出線”參加下一輪比賽。每個敗者都停在自己失敗的賽場上。根結(jié)點(diǎn)里存放最終的失敗者。11.2 外部排序的方法第 35 頁敗者樹：結(jié)點(diǎn)記錄敗者信息根結(jié)點(diǎn)里仍存放最終的失敗者。11.2 外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.60在根的上面附加一個結(jié)點(diǎn)，存放全局的優(yōu)勝者冠軍。第 36 頁敗者樹：結(jié)點(diǎn)記錄敗者信息輸出“6”，之后進(jìn)行調(diào)整。11.2 外

18、部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.601525.201598第 37 頁敗者樹：說明 勝者樹在人工處理時比較直觀，但在程序?qū)崿F(xiàn)時，特別是在重構(gòu)比賽樹時尋找對手，不如敗者樹效率高。 由于全勝者（最小元素）所在的從葉到根的內(nèi)結(jié)點(diǎn)中，都記錄著被全勝者所擊敗的對手，所以輸出最小元素并由后繼者代替之后，重構(gòu)選擇樹時，很容易找到要比較的“對手”，所以，實(shí)現(xiàn)替代選擇合并的算法也就簡單了。11.2 外部排序的方法第 38 頁敗者樹：實(shí)現(xiàn)是完全二叉樹，采用順序存

19、儲。非葉結(jié)點(diǎn)保存的是敗者在樹中對應(yīng)結(jié)點(diǎn)的下標(biāo)（編號）。11.2 外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.6081013149151211第 39 頁算法描述（P298算法11.1）typedef int LoserTreek; /采用順序存儲結(jié)構(gòu)typedef struct KeyType key; ExNode, External k+1 ; / 外結(jié)點(diǎn)，存待歸并關(guān)鍵字void K_Merge( LoserTree &ls, External &

20、b ) / ls0.k-1：保存非葉結(jié)點(diǎn) / b0bk-1：敗者樹的 k 個葉結(jié)點(diǎn)，k個歸并段的當(dāng)前關(guān)鍵字11.2 外部排序的方法第 40 頁算法描述（P298算法11.1）void K_Merge( LoserTree &ls, External &b ) 11.2 外部排序的方法for ( i=0; i= 0 ) if ( bs.key b ls0 .key ) s ls t ; / s：新的勝者的下標(biāo) t = t/2; ls 0 = s; / 保存全勝者下標(biāo)第 42 頁算法描述（P299算法11.3）void CreateLoserTree( LoserTree &ls ) / b 0

21、. k-1：為完全二叉樹 ls 的葉結(jié)點(diǎn)，保存鍵值 / 沿從葉結(jié)點(diǎn)到根的 k 條路徑將 ls 調(diào)整為敗者樹11.2 外部排序的方法b k = MINKEY; / 設(shè)為最小值for ( i=0; i=0; -i ) Adjust( ls, i ); / 從bk-1 到 b0調(diào)整敗者第 43 頁為一個待排文件創(chuàng)建盡可能大的初始順串，可以大大減少掃描遍數(shù)和外存讀寫次數(shù)。歸并順序的安排也能影響讀寫次數(shù)，把初始順串長度作為權(quán)，其實(shí)質(zhì)就是Huffman樹最優(yōu)化問題。11.2 外部排序的方法第 44 頁k路歸并是每次將k個順串合并成一個排好序的順串。一般情況下，對m個初始順串進(jìn)行k路歸并時歸并趟數(shù)為logkm。增加每次歸并的順串?dāng)?shù)量 k 可減少歸并趟數(shù)。選擇樹是完全二叉樹，有兩種類型：贏者樹和敗者樹。 11.2 外部排序的方法第 45 頁多路歸并11.2 外部排序的方法三路歸并第 46 頁問題在合并階段，如果初始的順串不等長，應(yīng)該如何挑選合并對象，減少讀塊次數(shù)，以加快合并速度？實(shí)例初始有9個順串，其長度（塊數(shù)）依次為：8, 23, 9, 15, 3, 12, 2, 6, 17。采用3路合并。應(yīng)該如何進(jìn)行才能使讀盤次數(shù)最少？11.3 最佳歸并樹第 47 頁實(shí)例初始有9個順串，其長度（塊數(shù)）依次為：8, 23, 9, 1