講義說(shuō)明教案講稿d

1、11.111.1 外存信息的存取外存信息的存取l外部排序：外部排序：指的是大文件的排序，即待指的是大文件的排序，即待排序的記錄存儲(chǔ)在外部存儲(chǔ)器上，在排排序的記錄存儲(chǔ)在外部存儲(chǔ)器上，在排序過(guò)程中需要多次進(jìn)行內(nèi)、外存間的交序過(guò)程中需要多次進(jìn)行內(nèi)、外存間的交換。換。l外部排序的機(jī)制是由外部排序的機(jī)制是由外部存儲(chǔ)器存取信外部存儲(chǔ)器存取信息息的特點(diǎn)決定。的特點(diǎn)決定。第 2 頁(yè)第 3 頁(yè)主存儲(chǔ)器和外存儲(chǔ)器主存儲(chǔ)器和外存儲(chǔ)器l主存儲(chǔ)器主存儲(chǔ)器 ( primary memory 或或 main memory，簡(jiǎn)稱內(nèi)存簡(jiǎn)稱內(nèi)存/主存主存) 隨機(jī)訪問(wèn)存儲(chǔ)器隨機(jī)訪問(wèn)存儲(chǔ)器( RAM )高速緩存高速緩存( cache

2、 )。 l外存儲(chǔ)器外存儲(chǔ)器 ( peripheral storage 或或 secondary storage，簡(jiǎn)稱外存，簡(jiǎn)稱外存) 硬盤硬盤 / 軟盤軟盤 / 磁帶磁帶 / U盤盤11.111.1 外存信息的存取外存信息的存取第 4 頁(yè)l磁盤的物理結(jié)構(gòu)磁盤的物理結(jié)構(gòu)11.111.1 外存信息的存取外存信息的存取11.111.1 外存信息的存取外存信息的存取第 5 頁(yè)第 6 頁(yè)l磁盤磁片的組織磁盤磁片的組織11.111.1 外存信息的存取外存信息的存取第 7 頁(yè)l磁盤的存取步驟磁盤的存取步驟:選定某個(gè)盤片組選定某個(gè)盤片組選定某個(gè)柱面選定某個(gè)柱面n這需要把磁頭移動(dòng)到該柱面這需要把磁頭移動(dòng)到該柱面

3、 ，這個(gè)移動(dòng)這個(gè)移動(dòng)過(guò)程稱為過(guò)程稱為尋道尋道( seek ) 確定磁道確定磁道 確定所要讀寫(xiě)的數(shù)據(jù)在磁盤上的準(zhǔn)確位置確定所要讀寫(xiě)的數(shù)據(jù)在磁盤上的準(zhǔn)確位置n這段時(shí)間一般稱為這段時(shí)間一般稱為旋轉(zhuǎn)延遲旋轉(zhuǎn)延遲( rotational delay ( rotational delay 或者或者rotational rotational latency )latency )真正進(jìn)行讀寫(xiě)真正進(jìn)行讀寫(xiě)11.111.1 外存信息的存取外存信息的存取第 8 頁(yè)l磁盤的存取時(shí)間磁盤的存取時(shí)間11.111.1 外存信息的存取外存信息的存取間間時(shí)時(shí)輸輸傳傳磁道磁道尋道尋道時(shí)間時(shí)間磁臂磁臂等等待待 時(shí)時(shí)間間數(shù)數(shù)據(jù)據(jù)信信

4、息息磁磁盤盤旋旋轉(zhuǎn)轉(zhuǎn)方方向向第 9 頁(yè)l扇區(qū)的組織（交錯(cuò)法扇區(qū)的組織（交錯(cuò)法 interleaving）11.111.1 外存信息的存取外存信息的存?。╝ a）沒(méi)有扇區(qū)交錯(cuò)）沒(méi)有扇區(qū)交錯(cuò) （b b）以）以3 3為交錯(cuò)因子為交錯(cuò)因子第 10 頁(yè)l磁盤的存取時(shí)間磁盤的存取時(shí)間磁盤訪問(wèn)時(shí)間主要由磁盤訪問(wèn)時(shí)間主要由尋道時(shí)間尋道時(shí)間、旋轉(zhuǎn)延遲旋轉(zhuǎn)延遲時(shí)間時(shí)間和和數(shù)據(jù)傳輸時(shí)間數(shù)據(jù)傳輸時(shí)間組成。組成。 尋道時(shí)間（尋道時(shí)間（Seek time）t tseekseek：是：是移動(dòng)磁盤移動(dòng)磁盤臂，定位到正確磁道所需的時(shí)間。臂，定位到正確磁道所需的時(shí)間。旋轉(zhuǎn)延遲時(shí)間旋轉(zhuǎn)延遲時(shí)間t tlala：是：是等待被存取的扇區(qū)

5、出等待被存取的扇區(qū)出現(xiàn)在讀寫(xiě)頭下所需的時(shí)間?，F(xiàn)在讀寫(xiě)頭下所需的時(shí)間。傳輸時(shí)間傳輸時(shí)間t twmwm：是：是傳輸字符的時(shí)間。傳輸字符的時(shí)間。T TI/OI/O=t=tseek seek + t+ tlala + t + twmwm11.111.1 外存信息的存取外存信息的存取第 11 頁(yè)l磁帶運(yùn)行示意磁帶運(yùn)行示意11.111.1 外存信息的存取外存信息的存取 磁帶卷在一個(gè)卷盤上，運(yùn)行時(shí)磁帶經(jīng)過(guò)讀磁帶卷在一個(gè)卷盤上，運(yùn)行時(shí)磁帶經(jīng)過(guò)讀寫(xiě)磁頭，把磁帶上的信息讀入計(jì)算機(jī)，或把計(jì)寫(xiě)磁頭，把磁帶上的信息讀入計(jì)算機(jī)，或把計(jì)算機(jī)中的信息寫(xiě)在磁帶上算機(jī)中的信息寫(xiě)在磁帶上。第 12 頁(yè)l外存的特點(diǎn)外存的特點(diǎn)優(yōu)點(diǎn)：優(yōu)

6、點(diǎn)：永久存儲(chǔ)能力、便攜性永久存儲(chǔ)能力、便攜性 缺點(diǎn)：訪問(wèn)時(shí)間長(zhǎng)缺點(diǎn)：訪問(wèn)時(shí)間長(zhǎng)訪問(wèn)磁盤中的數(shù)據(jù)比訪問(wèn)內(nèi)存慢五六個(gè)數(shù)訪問(wèn)磁盤中的數(shù)據(jù)比訪問(wèn)內(nèi)存慢五六個(gè)數(shù)量級(jí)量級(jí)。 因此，在對(duì)外存的數(shù)據(jù)結(jié)構(gòu)及其上的操作因此，在對(duì)外存的數(shù)據(jù)結(jié)構(gòu)及其上的操作時(shí)，必須遵循的基本原則是：時(shí)，必須遵循的基本原則是：盡量減少訪外盡量減少訪外次數(shù)！次數(shù)！ 11.111.1 外存信息的存取外存信息的存取第 13 頁(yè)為什么需要文件管理和外部排序？為什么需要文件管理和外部排序？l文件結(jié)構(gòu)（文件結(jié)構(gòu)（file structure）：）：數(shù)據(jù)量太大不可能同時(shí)都放到內(nèi)存中，所數(shù)據(jù)量太大不可能同時(shí)都放到內(nèi)存中，所以需要把全部數(shù)據(jù)放到外部存儲(chǔ)

7、設(shè)備上。以需要把全部數(shù)據(jù)放到外部存儲(chǔ)設(shè)備上。對(duì)于在外存中存儲(chǔ)的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)就對(duì)于在外存中存儲(chǔ)的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)就稱為文件結(jié)構(gòu)。稱為文件結(jié)構(gòu)。l對(duì)文件的對(duì)文件的各種操作各種操作：外部排序是針對(duì)外存文件所進(jìn)行的外部排序是針對(duì)外存文件所進(jìn)行的排序操排序操作，是文件的作，是文件的基礎(chǔ)操作基礎(chǔ)操作；高效的外部排序；高效的外部排序可以可以提高文件存儲(chǔ)效率和其他操作的效率。提高文件存儲(chǔ)效率和其他操作的效率。11.111.1 外存信息的存取外存信息的存取第 14 頁(yè)l文件上的操作文件上的操作l檢索檢索：在文件中尋找滿足一定條件的記錄在文件中尋找滿足一定條件的記錄 l修改修改：對(duì)記錄中某些數(shù)據(jù)值進(jìn)行修改。若

8、對(duì)：對(duì)記錄中某些數(shù)據(jù)值進(jìn)行修改。若對(duì)關(guān)鍵字進(jìn)行修改，就相當(dāng)于刪除加插入。關(guān)鍵字進(jìn)行修改，就相當(dāng)于刪除加插入。l插入插入：向文件中增加一個(gè)新記錄。向文件中增加一個(gè)新記錄。 l刪除刪除：從文件中刪去一個(gè)記錄：從文件中刪去一個(gè)記錄 。l排序排序 ：對(duì)指定好的數(shù)據(jù)項(xiàng)，按其值的大小把對(duì)指定好的數(shù)據(jù)項(xiàng)，按其值的大小把文件中的記錄排成序列。常用的是按關(guān)鍵字文件中的記錄排成序列。常用的是按關(guān)鍵字的排序。的排序。 11.111.1 外存信息的存取外存信息的存取第 15 頁(yè)l外存文件的組織外存文件的組織 文件是一些記錄的集合，每個(gè)記錄可由文件是一些記錄的集合，每個(gè)記錄可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成

9、。 數(shù)據(jù)項(xiàng)也稱為字段，或?qū)傩?。?shù)據(jù)項(xiàng)也稱為字段，或?qū)傩浴?1.111.1 外存信息的存取外存信息的存取職工號(hào)職工號(hào)姓名姓名性別性別職務(wù)職務(wù)婚姻狀況婚姻狀況工資工資156張東張東男男程序員程序員未婚未婚7800860李珍李珍女女分析員分析員已婚已婚8900510趙莉趙莉女女程序員程序員未婚未婚6900950陳萍陳萍女女程序員程序員未婚未婚6200620周力周力男男分析員分析員已婚已婚10300第 16 頁(yè)l邏輯文件邏輯文件對(duì)高級(jí)程序語(yǔ)言的編程人員而言，磁盤中可以隨機(jī)對(duì)高級(jí)程序語(yǔ)言的編程人員而言，磁盤中可以隨機(jī)訪問(wèn)的文件訪問(wèn)的文件被當(dāng)作一段連續(xù)的字節(jié)被當(dāng)作一段連續(xù)的字節(jié)，且可將這些字，且可將這些字

10、節(jié)結(jié)合起來(lái)構(gòu)成記錄，這種文件被稱為邏輯文件。節(jié)結(jié)合起來(lái)構(gòu)成記錄，這種文件被稱為邏輯文件。l物理文件物理文件實(shí)際存儲(chǔ)在磁盤中的物理文件通常實(shí)際存儲(chǔ)在磁盤中的物理文件通常不是一段連續(xù)的不是一段連續(xù)的字節(jié)，而是字節(jié)，而是成塊地分布成塊地分布在整個(gè)磁盤中。在整個(gè)磁盤中。l文件管理文件管理是操作系統(tǒng)的一部分，當(dāng)應(yīng)用程序請(qǐng)求從邏輯文件是操作系統(tǒng)的一部分，當(dāng)應(yīng)用程序請(qǐng)求從邏輯文件中讀取數(shù)據(jù)時(shí)，它將這些中讀取數(shù)據(jù)時(shí)，它將這些邏輯位置映射為磁盤中具邏輯位置映射為磁盤中具體的物理位置體的物理位置。11.111.1 外存信息的存取外存信息的存取第 17 頁(yè)l文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)文件是記錄的集合文件是記錄的集

11、合。當(dāng)一個(gè)文件的各個(gè)記錄按照某種次序排列當(dāng)一個(gè)文件的各個(gè)記錄按照某種次序排列起來(lái)時(shí)，各記錄間就自然地形成了一種線起來(lái)時(shí)，各記錄間就自然地形成了一種線性關(guān)系。性關(guān)系。 因而，文件可看成是一種線性結(jié)構(gòu)。因而，文件可看成是一種線性結(jié)構(gòu)。 11.111.1 外存信息的存取外存信息的存取l文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)l順序結(jié)構(gòu)順序結(jié)構(gòu)順序文件順序文件 l計(jì)算尋址結(jié)構(gòu)計(jì)算尋址結(jié)構(gòu)散列文件散列文件 l帶索引的結(jié)構(gòu)帶索引的結(jié)構(gòu)帶索引文件帶索引文件 第 18 頁(yè)l文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)p順序文件：記錄按照自然次序依次存儲(chǔ)順序文件：記錄按照自然次序依次存儲(chǔ)1.存取第存取第 i 個(gè)記錄之前，必須存取第個(gè)記錄之

12、前，必須存取第 i-1 個(gè)記錄個(gè)記錄2.新記錄只能插在文件尾部新記錄只能插在文件尾部3.更新文件中的數(shù)據(jù)必須將整個(gè)文件復(fù)制一遍更新文件中的數(shù)據(jù)必須將整個(gè)文件復(fù)制一遍p散列文件：利用散列文件：利用散列函數(shù)和沖突處理散列函數(shù)和沖突處理p索引文件：帶有按關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)進(jìn)行索引索引文件：帶有按關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)進(jìn)行索引的文件的文件n虛擬存儲(chǔ)存取方式虛擬存儲(chǔ)存取方式VSAM：索引順序文件用：索引順序文件用B+樹(shù)作為動(dòng)態(tài)索引樹(shù)樹(shù)作為動(dòng)態(tài)索引樹(shù)11.111.1 外存信息的存取外存信息的存取第 19 頁(yè)l外部排序外部排序( External Sort )產(chǎn)生的緣由產(chǎn)生的緣由：由于文件很大，無(wú)法把整個(gè)：由于文件很大，無(wú)

13、法把整個(gè)文件的所有記錄同時(shí)調(diào)入內(nèi)存中進(jìn)行排序，文件的所有記錄同時(shí)調(diào)入內(nèi)存中進(jìn)行排序，即即無(wú)法進(jìn)行內(nèi)部排序無(wú)法進(jìn)行內(nèi)部排序。對(duì)對(duì)外存設(shè)備上外存設(shè)備上（文件（文件）進(jìn)行）進(jìn)行的排序技術(shù)。的排序技術(shù)。 l外部排序算法的主要目標(biāo)：外部排序算法的主要目標(biāo)：盡量減少讀盡量減少讀寫(xiě)磁盤的次數(shù)寫(xiě)磁盤的次數(shù) 。11.211.2 外部排序的方法外部排序的方法第 20 頁(yè)l順串：順串：用某種有效的用某種有效的內(nèi)排序方法內(nèi)排序方法對(duì)組成對(duì)組成文件的各段文件的各段/ /子文件進(jìn)行初始排序后重新子文件進(jìn)行初始排序后重新寫(xiě)回外存的段或子文件被稱為寫(xiě)回外存的段或子文件被稱為歸并段歸并段或或順串順串(run) (run) 。l

14、外部排序的過(guò)程：外部排序的過(guò)程：把文件分成若干盡可能長(zhǎng)的初始把文件分成若干盡可能長(zhǎng)的初始順串順串。逐步歸并順串（或歸并段），最后形成一逐步歸并順串（或歸并段），最后形成一個(gè)已排序的文件。個(gè)已排序的文件。11.211.2 外部排序的方法外部排序的方法第 21 頁(yè)l外部排序的時(shí)間開(kāi)銷：外部排序的時(shí)間開(kāi)銷：總時(shí)間總時(shí)間 =內(nèi)部排序產(chǎn)生初始順段內(nèi)部排序產(chǎn)生初始順段 時(shí)間時(shí)間 +外存信息讀寫(xiě)時(shí)間外存信息讀寫(xiě)時(shí)間 +內(nèi)部歸并所需時(shí)間內(nèi)部歸并所需時(shí)間 = m* *tis + d* *tio + s* *utmg其中：其中：tis：得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所需時(shí)間：得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所需時(shí)間

15、m：經(jīng)過(guò)內(nèi)排序后得到的初始?xì)w并段的數(shù)量：經(jīng)過(guò)內(nèi)排序后得到的初始?xì)w并段的數(shù)量tio：進(jìn)行一次外存讀寫(xiě)的時(shí)間：進(jìn)行一次外存讀寫(xiě)的時(shí)間d：總的讀：總的讀/寫(xiě)次數(shù)寫(xiě)次數(shù)utmg：對(duì)：對(duì) u 個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間s：歸并的趟數(shù)：歸并的趟數(shù)11.211.2 外部排序的方法外部排序的方法第 22 頁(yè)p減少外存信息的讀寫(xiě)次數(shù)減少外存信息的讀寫(xiě)次數(shù)是提高外部排序效是提高外部排序效率的關(guān)鍵率的關(guān)鍵 ：l對(duì)同一個(gè)文件而言，進(jìn)行外排序所需讀寫(xiě)外對(duì)同一個(gè)文件而言，進(jìn)行外排序所需讀寫(xiě)外存的存的次數(shù)與歸并趟數(shù)成正比關(guān)系。次數(shù)與歸并趟數(shù)成正比關(guān)系。l假設(shè)有假設(shè)有m個(gè)初始順串，每次對(duì)個(gè)初始順串，

16、每次對(duì)k個(gè)順串進(jìn)行歸個(gè)順串進(jìn)行歸并，其歸并趟數(shù)為并，其歸并趟數(shù)為logkm。p為了減少歸并趟數(shù)，可以從兩個(gè)方面著手：為了減少歸并趟數(shù)，可以從兩個(gè)方面著手：減少初始順串的個(gè)數(shù)減少初始順串的個(gè)數(shù)m m增加歸并的順串?dāng)?shù)量增加歸并的順串?dāng)?shù)量k k11.211.2 外部排序的方法外部排序的方法第 23 頁(yè)p外部排序基本做法的描述：外部排序基本做法的描述：假定文件有假定文件有4500個(gè)記錄：個(gè)記錄：R1, R2, , R4500。磁。磁盤上盤上 1 塊（即塊（即1 個(gè)扇區(qū)）的尺寸是個(gè)扇區(qū)）的尺寸是250個(gè)記錄個(gè)記錄，該文件總共需用磁盤的，該文件總共需用磁盤的 18 個(gè)扇區(qū)。內(nèi)存可個(gè)扇區(qū)。內(nèi)存可供用于排序的

17、空間是供用于排序的空間是 750 個(gè)記錄大小。個(gè)記錄大小。p排序過(guò)程如下：排序過(guò)程如下： 每次從磁盤讀入每次從磁盤讀入 3 塊（塊（750個(gè)記錄）到內(nèi)存，利用內(nèi)排序算法將它們個(gè)記錄）到內(nèi)存，利用內(nèi)排序算法將它們排好序，然后寫(xiě)回磁盤。這樣，磁盤上就得排好序，然后寫(xiě)回磁盤。這樣，磁盤上就得到了到了6個(gè)初始有序段個(gè)初始有序段A1、A2、A6。 11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A422513000有序段有序段A530013750有序段有序段A637514500第 24 頁(yè)把內(nèi)存按把內(nèi)

18、存按 250 個(gè)記錄的長(zhǎng)度分成三部分：個(gè)記錄的長(zhǎng)度分成三部分： 兩部分為輸入緩沖區(qū)，兩部分為輸入緩沖區(qū)， 一部分為輸出緩沖區(qū)。一部分為輸出緩沖區(qū)。先對(duì)先對(duì) A1 和和 A2 進(jìn)行歸并：進(jìn)行歸并：先將每段的一塊（先將每段的一塊（250個(gè)有序記錄）讀到內(nèi)存的兩個(gè)輸入緩沖區(qū)個(gè)有序記錄）讀到內(nèi)存的兩個(gè)輸入緩沖區(qū)，用歸并排序算法實(shí)施排序。邊排序，邊把結(jié)，用歸并排序算法實(shí)施排序。邊排序，邊把結(jié)果寫(xiě)到輸出緩沖區(qū)。果寫(xiě)到輸出緩沖區(qū)。輸出緩沖區(qū)滿時(shí)，寫(xiě)入磁盤；當(dāng)一個(gè)輸入緩沖輸出緩沖區(qū)滿時(shí)，寫(xiě)入磁盤；當(dāng)一個(gè)輸入緩沖區(qū)的內(nèi)容歸并完騰空時(shí)，將該有序段的下一塊區(qū)的內(nèi)容歸并完騰空時(shí)，將該有序段的下一塊讀入該緩沖區(qū)繼續(xù)歸并

19、。讀入該緩沖區(qū)繼續(xù)歸并。這樣繼續(xù)，直到把這樣繼續(xù)，直到把 A1 和和 A2 全歸并完畢，磁全歸并完畢，磁盤里出現(xiàn)一個(gè)含盤里出現(xiàn)一個(gè)含1500個(gè)記錄的新有序段。個(gè)記錄的新有序段。11.211.2 外部排序的方法外部排序的方法第 25 頁(yè) 完成一次歸并后，對(duì)完成一次歸并后，對(duì)A3和和A4、A5和和A6實(shí)施相實(shí)施相同歸并。整個(gè)文件經(jīng)一趟歸并，在磁盤上得同歸并。整個(gè)文件經(jīng)一趟歸并，在磁盤上得到三個(gè)各含到三個(gè)各含1500記錄的有序段。記錄的有序段。11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A42

20、2513000有序段有序段A530013750有序段有序段A6375145003000個(gè)記錄個(gè)記錄第第2趟歸并趟歸并1500個(gè)記錄個(gè)記錄1500個(gè)記錄個(gè)記錄1500個(gè)記錄個(gè)記錄第第1趟歸并趟歸并4500個(gè)記錄個(gè)記錄第第3趟歸并趟歸并繼續(xù)進(jìn)行歸并：繼續(xù)進(jìn)行歸并：第第 2 趟，第趟，第 3 趟。趟。第 26 頁(yè)l分析分析在一切相同的條件下，如果把例中的在一切相同的條件下，如果把例中的 2-路歸路歸并改變成并改變成 3-路或路或 6-路（當(dāng)然，這時(shí)所需要的路（當(dāng)然，這時(shí)所需要的內(nèi)存緩沖區(qū)個(gè)數(shù)將會(huì)變化），那么總的讀寫(xiě)磁內(nèi)存緩沖區(qū)個(gè)數(shù)將會(huì)變化），那么總的讀寫(xiě)磁盤次數(shù)就會(huì)下降。盤次數(shù)就會(huì)下降。11.211

21、.2 外部排序的方法外部排序的方法歸并路數(shù)歸并路數(shù) 總讀寫(xiě)磁盤次數(shù)總讀寫(xiě)磁盤次數(shù) 歸并趟數(shù)歸并趟數(shù) 2 132 3 3 108 2 6 72 1第 27 頁(yè)lk-路歸并路歸并k-路歸并時(shí)，在路歸并時(shí)，在 k 個(gè)關(guān)鍵字中選最小值。通常個(gè)關(guān)鍵字中選最小值。通?？刹捎弥苯舆x擇排序方法，對(duì)關(guān)鍵字做可采用直接選擇排序方法，對(duì)關(guān)鍵字做 k-1次次比較。比較。問(wèn)題：?jiǎn)栴}：在直接選擇排序時(shí)許多關(guān)鍵字間進(jìn)行在直接選擇排序時(shí)許多關(guān)鍵字間進(jìn)行了不止一次的重復(fù)比較，導(dǎo)致時(shí)間的浪費(fèi)。了不止一次的重復(fù)比較，導(dǎo)致時(shí)間的浪費(fèi)。解決辦法：解決辦法：若在選擇最小者時(shí)，將比較結(jié)果若在選擇最小者時(shí)，將比較結(jié)果保留下來(lái)，后面需要時(shí)加以

22、利用，就可減少保留下來(lái)，后面需要時(shí)加以利用，就可減少比較次數(shù)，減少磁盤輸入比較次數(shù)，減少磁盤輸入/輸出所耗費(fèi)的時(shí)間，輸出所耗費(fèi)的時(shí)間，從而使排序的速度提高。從而使排序的速度提高。11.211.2 外部排序的方法外部排序的方法第 28 頁(yè)l選擇樹(shù)選擇樹(shù)選擇樹(shù)是一棵二叉樹(shù)，該樹(shù)中的分支結(jié)點(diǎn)是選擇樹(shù)是一棵二叉樹(shù)，該樹(shù)中的分支結(jié)點(diǎn)是該結(jié)點(diǎn)兩個(gè)孩子中的較小者，根結(jié)點(diǎn)是這棵該結(jié)點(diǎn)兩個(gè)孩子中的較小者，根結(jié)點(diǎn)是這棵樹(shù)各葉結(jié)點(diǎn)中的最小者。樹(shù)各葉結(jié)點(diǎn)中的最小者。11.211.2 外部排序的方法外部排序的方法10920689901769681768 為選擇次小者，可把該記錄原始位置（葉結(jié)點(diǎn)）設(shè)為選擇次小者，可把該記

23、錄原始位置（葉結(jié)點(diǎn)）設(shè)成一個(gè)大于所有關(guān)鍵字的值成一個(gè)大于所有關(guān)鍵字的值“+”。進(jìn)行。進(jìn)行輸出輸出-調(diào)整調(diào)整。最小值最小值+由下往由下往上調(diào)整上調(diào)整2098k=8時(shí)時(shí)第 29 頁(yè)l選擇樹(shù)選擇樹(shù)為選取下一個(gè)最小者，只需對(duì)根結(jié)點(diǎn)到該葉為選取下一個(gè)最小者，只需對(duì)根結(jié)點(diǎn)到該葉結(jié)點(diǎn)所經(jīng)路徑上的各結(jié)點(diǎn)與其左或右兄弟進(jìn)結(jié)點(diǎn)所經(jīng)路徑上的各結(jié)點(diǎn)與其左或右兄弟進(jìn)行比較和適當(dāng)?shù)恼{(diào)整即可，其他結(jié)點(diǎn)保持原行比較和適當(dāng)?shù)恼{(diào)整即可，其他結(jié)點(diǎn)保持原樣。樣。11.211.2 外部排序的方法外部排序的方法10920+899017892081798+9k=8時(shí)時(shí)輸出輸出8，并調(diào)整，并調(diào)整99輸出輸出9，并調(diào)整，并調(diào)整+10109輸出

24、輸出9，并調(diào)整，并調(diào)整+1710第 30 頁(yè)l勝者樹(shù)：結(jié)點(diǎn)記錄勝者信息勝者樹(shù)：結(jié)點(diǎn)記錄勝者信息利用選擇樹(shù)的思想，對(duì)有序段進(jìn)行利用選擇樹(shù)的思想，對(duì)有序段進(jìn)行k-路歸并。路歸并。樹(shù)的每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)樹(shù)的每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)輸入緩沖區(qū)輸入緩沖區(qū)，它總，它總是各有序段在歸并過(guò)程中的是各有序段在歸并過(guò)程中的當(dāng)前關(guān)鍵字當(dāng)前關(guān)鍵字，分，分支結(jié)點(diǎn)是它的兩個(gè)孩子結(jié)點(diǎn)中支結(jié)點(diǎn)是它的兩個(gè)孩子結(jié)點(diǎn)中鍵值較小鍵值較小的那的那個(gè)。個(gè)。根根結(jié)點(diǎn)是樹(shù)中結(jié)點(diǎn)是樹(shù)中鍵最小鍵最小的。的。輸出根結(jié)點(diǎn)后，用該記錄所在有序段的下一輸出根結(jié)點(diǎn)后，用該記錄所在有序段的下一個(gè)關(guān)鍵字填補(bǔ)它的位置，并作適當(dāng)調(diào)整。這個(gè)關(guān)鍵字填補(bǔ)它的位置，并作適當(dāng)調(diào)

25、整。這樣的調(diào)整不會(huì)涉及到整棵樹(shù)，而只需考慮從樣的調(diào)整不會(huì)涉及到整棵樹(shù)，而只需考慮從根結(jié)點(diǎn)到該位置的路徑上的各個(gè)結(jié)點(diǎn)。根結(jié)點(diǎn)到該位置的路徑上的各個(gè)結(jié)點(diǎn)。11.211.2 外部排序的方法外部排序的方法第 31 頁(yè)l勝者樹(shù)勝者樹(shù)當(dāng)前當(dāng)前8個(gè)待歸并有序段的前個(gè)待歸并有序段的前3個(gè)關(guān)鍵字值：個(gè)關(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.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519

26、.2038.2234.1525.1750.2144.95108.3266.第 32 頁(yè)l勝者樹(shù)勝者樹(shù)對(duì)對(duì) 8 個(gè)并有序段進(jìn)行一次歸并。先輸出根結(jié)個(gè)并有序段進(jìn)行一次歸并。先輸出根結(jié)點(diǎn)上關(guān)鍵字為點(diǎn)上關(guān)鍵字為 6 的記錄，它原位于最底層編的記錄，它原位于最底層編號(hào)為號(hào)為 11 的葉結(jié)點(diǎn)處，用的葉結(jié)點(diǎn)處，用15頂替。局部調(diào)整頂替。局部調(diào)整 。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.1598第 33 頁(yè)l勝者樹(shù)勝者樹(shù)輸出原位

27、于編號(hào)為輸出原位于編號(hào)為12的記錄的記錄8，并用它后面值，并用它后面值為為“17”的關(guān)鍵字進(jìn)行頂替。做適當(dāng)調(diào)整的關(guān)鍵字進(jìn)行頂替。做適當(dāng)調(diào)整.11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.159850.171717938.20101010輸出輸出 9，再繼續(xù)進(jìn)行調(diào)整，再繼續(xù)進(jìn)行調(diào)整.第 34 頁(yè)l勝者樹(shù)勝者樹(shù)：實(shí)現(xiàn)：實(shí)現(xiàn)勝者樹(shù)是勝者樹(shù)是完全二叉樹(shù)完全二叉樹(shù)，算法實(shí)現(xiàn)時(shí)，采用，算法實(shí)現(xiàn)時(shí)，采用順順序存儲(chǔ)結(jié)構(gòu)序存儲(chǔ)結(jié)構(gòu)保存。保

28、存。非葉結(jié)點(diǎn)非葉結(jié)點(diǎn)保存的是保存的是“勝者勝者”在樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的在樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的下標(biāo)下標(biāo)（編號(hào)編號(hào)）。）。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.9111215111211保存：勝者保存：勝者對(duì)應(yīng)葉結(jié)點(diǎn)對(duì)應(yīng)葉結(jié)點(diǎn)的編號(hào)的編號(hào)第 35 頁(yè)l敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息敗者樹(shù)是一棵有敗者樹(shù)是一棵有 k 個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，分支個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，分支結(jié)點(diǎn)存放該結(jié)點(diǎn)兩個(gè)孩子中的結(jié)點(diǎn)存放該結(jié)點(diǎn)兩個(gè)孩子中的較大者較大者

29、（敗敗者者），而讓較小者（勝者）參加上一層的比），而讓較小者（勝者）參加上一層的比較，即勝者較，即勝者“出線出線”參加下一輪比賽。每個(gè)參加下一輪比賽。每個(gè)敗者都停在自己失敗的賽場(chǎng)上。敗者都停在自己失敗的賽場(chǎng)上。根根結(jié)點(diǎn)里存放結(jié)點(diǎn)里存放最終的失敗者最終的失敗者。11.211.2 外部排序的方法外部排序的方法第 36 頁(yè)l敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息根結(jié)點(diǎn)里仍存放最終的失敗者。根結(jié)點(diǎn)里仍存放最終的失敗者。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525

30、.1750.2144.95108.3266.60在根的上面附加一個(gè)結(jié)點(diǎn)，存放全局的優(yōu)勝在根的上面附加一個(gè)結(jié)點(diǎn)，存放全局的優(yōu)勝者者冠軍。冠軍。第 37 頁(yè)l敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息敗者樹(shù)：結(jié)點(diǎn)記錄敗者信息輸出輸出“6”，之后進(jìn)行調(diào)整。，之后進(jìn)行調(diào)整。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.601525.201598第 38 頁(yè)l敗者樹(shù)敗者樹(shù)：說(shuō)明：說(shuō)明 勝者樹(shù)在人工處理時(shí)比較勝者樹(shù)在人工處理時(shí)比較直觀直觀，但在程序?qū)崳?/p>

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

32、叉樹(shù)完全二叉樹(shù)，采用，采用順序存儲(chǔ)順序存儲(chǔ)。非葉結(jié)點(diǎn)非葉結(jié)點(diǎn)保保存的是敗者在樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的存的是敗者在樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的下標(biāo)下標(biāo)（編號(hào)編號(hào)）。）。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.6081013149151211第 40 頁(yè)l算法描述（算法描述（P298算法算法11.1）typedef int LoserTreek; /采用順序存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)結(jié)構(gòu)typedef struct KeyType key; ExNo

33、de, External k+1 ; / 外結(jié)點(diǎn)，存待歸并關(guān)鍵字外結(jié)點(diǎn)，存待歸并關(guān)鍵字void K_Merge( LoserTree &ls, External &b ) / ls0.k-1：保存非葉結(jié)點(diǎn)：保存非葉結(jié)點(diǎn) / b0bk-1：敗者樹(shù)的：敗者樹(shù)的 k 個(gè)葉結(jié)點(diǎn)，個(gè)葉結(jié)點(diǎn)，k個(gè)歸并段的個(gè)歸并段的當(dāng)前關(guān)鍵字當(dāng)前關(guān)鍵字11.211.2 外部排序的方法外部排序的方法第 41 頁(yè)l算法描述（算法描述（P298算法算法11.1）void K_Merge( LoserTree &ls, External &b ) 11.211.2 外部排序的方法外部排序的方法for

34、 ( i=0; i= 0 ) if ( bs.key b ls0 .key ) s ls t ; / s：新的勝者的下標(biāo)：新的勝者的下標(biāo) t = t/2; ls 0 = s; / 保存全勝者下標(biāo)保存全勝者下標(biāo)第 43 頁(yè)l算法描述（算法描述（P299算法算法11.3）void CreateLoserTree( LoserTree &ls ) / b 0 . k-1：為完全二叉樹(shù)：為完全二叉樹(shù) ls 的葉結(jié)點(diǎn)，保存鍵值的葉結(jié)點(diǎn)，保存鍵值 / 沿從葉結(jié)點(diǎn)到根的沿從葉結(jié)點(diǎn)到根的 k 條路徑將條路徑將 ls 調(diào)整為敗者樹(shù)調(diào)整為敗者樹(shù)11.211.2 外部排序的方法外部排序的方法b k = MI

35、NKEY; / 設(shè)為最小值設(shè)為最小值for ( i=0; i=0; -i ) Adjust( ls, i ); / 從從bk-1 到到 b0調(diào)整敗者調(diào)整敗者第 44 頁(yè)lk路歸并是每次將路歸并是每次將k個(gè)順串合并成一個(gè)排好序個(gè)順串合并成一個(gè)排好序的順串。一般情況下，對(duì)的順串。一般情況下，對(duì)m個(gè)初始順串進(jìn)行個(gè)初始順串進(jìn)行k路歸并時(shí)歸并趟數(shù)為路歸并時(shí)歸并趟數(shù)為logkm。增加每次歸并的。增加每次歸并的順串?dāng)?shù)量順串?dāng)?shù)量 k 可減少歸并趟數(shù)?？蓽p少歸并趟數(shù)。l選擇樹(shù)是完全二叉樹(shù)，有兩種類型：贏者樹(shù)選擇樹(shù)是完全二叉樹(shù)，有兩種類型：贏者樹(shù)和敗者樹(shù)。和敗者樹(shù)。 11.211.2 外部排序的方法外部排序的方法第 45 頁(yè)l多路歸并多路歸并11.211.2 外部排序的方法外部排序的方法三路歸并三路歸并第 46 頁(yè)l問(wèn)題問(wèn)題在合并階段，如果初始的順串不等長(zhǎng)，應(yīng)該在合并階段，如果初始的順串不等長(zhǎng)，應(yīng)該如何挑選合并對(duì)象，減少讀塊次數(shù)，以加快如何挑選合并對(duì)象，減少讀塊次數(shù)，以加快合并速度？合并速度？l實(shí)例實(shí)例初始有初始有9個(gè)順串，其長(zhǎng)度（塊數(shù)）依次為：個(gè)順串，其長(zhǎng)度（塊數(shù)）依次為：8, 23, 9, 15, 3, 12, 2, 6, 17。采用。采用3路合并。應(yīng)該路合并。應(yīng)該如何進(jìn)行才能使讀盤次數(shù)最少？如何進(jìn)行才能使讀盤次數(shù)最少？11.2