數(shù)據(jù)結構教程第10章文件、外部排序與搜索課件

第十章文件、外部排序與搜索1主存儲器和外存儲器

文件組織

外排序

多級索引結構

可擴充散列Trie樹

第十章文件、外部排序

與外部搜索2主存儲器與外部存儲器外存儲器與內存儲器相比，優(yōu)點是：價格較低永久的存儲能力缺點：訪問外存儲器上的數(shù)據(jù)比訪問內存要慢5～6個數(shù)量級要求我們在開發(fā)系統(tǒng)時必須考慮如何使外存訪問次數(shù)達到最少。3磁帶卷在一個卷盤上，運行時磁帶經過讀寫磁頭，把磁帶上的信息讀入計算機，或者把計算機中的信息寫到磁帶上去。數(shù)據(jù)記錄在磁帶帶面上。在帶面上并列存放有9個磁道的信息，即每一橫排有9位二進制信息：8位數(shù)據(jù)加1位奇偶校驗位。磁帶的存儲密度用BPI（BitPerInch）為單位，典型的存儲密度有3種：6250BPI（=246排/mm）、1600BPI（=64排/mm）、800BPI（32排/mm）。正常走帶速度為3～5m/Sec，因設備而異。5數(shù)據(jù)的傳送速度=存儲密度走帶速度／讀寫時間。在應用中使用文件進行數(shù)據(jù)處理的基本單位叫做邏輯記錄，簡稱為記錄；在磁帶上物理地存儲的記錄叫做物理記錄。在使用磁帶或磁盤存放邏輯記錄時，常常把若干個邏輯記錄打包進行存放，把這個過程叫做“塊化”（blocking）。經過塊化處理的物理記錄叫做塊化記錄。磁帶設備是一種啟停設備。磁帶每次啟停都有一個加速與減速的過程，在這段時間內走帶不6 穩(wěn)定，只能走空帶，這段空帶叫做記錄間間隙IRG（InterRecordGap）或者塊間間隙IBG（InterBlockGap），其長度因設備而異。磁帶速度75-200英寸/秒傳輸速度字/秒1.5-16ms1.5-16ms定速加速IBG0.3～0.75英寸減速物理記錄啟動位置IBG0.3～0.75英寸停止位置傳輸開始傳輸完成經過時間7在磁帶設備上讀寫一塊信息所用時間

tIO=ta+tb其中，ta是延遲時間，即讀寫磁頭到達待讀寫塊開始位置所需花費的時間，它與當前讀寫磁頭所在位置有關。tb是對一個塊進行讀寫所用時間，它等于數(shù)據(jù)傳輸時間加上IBG時間。磁帶設備只能用于處理變化少，只進行順序存取的大量數(shù)據(jù)。9磁盤（disc）磁盤存儲器通常稱為直接存取設備，或隨機存取設備，它訪問外存上文件的任一記錄的時間幾乎相同。磁盤存儲器可以順序存取，也可以隨機存取。目前使用較多的是活動臂硬盤組：若干盤片構成磁盤組，它們安裝在主軸上，在驅動裝置的控制下高速旋轉。除了最上面一個盤片和最下面一個盤片的外側盤面不用以外，其他每個盤片上下兩面都可存放數(shù)據(jù)。將這些可存放數(shù)據(jù)的盤面稱為記錄盤面。

10主軸盤片活動臂（回轉臂）讀寫磁頭磁道柱面11各個記錄盤面上半徑相同的磁道合在一起稱為柱面。動臂的移動實際上是將磁頭從一個柱面移動到另一個柱面上。一個磁道可以劃分為若干段，稱為扇區(qū)，一個扇區(qū)就是一次讀寫的最小數(shù)據(jù)量。這樣，對磁盤存儲器來說，從大到小的存儲單位是：盤片組、柱面、磁道和扇區(qū)。13對磁盤存儲器進行一次存取所需時間：當有多個盤片組時，要選定某個盤片組。這是由電子線路實現(xiàn)的，速度很快。選定盤片組后再選定某個柱面，并移動動臂把磁頭移到此柱面上。這是機械動作，速度較慢。這稱為“尋查（seek）”。選定柱面后，要進一步確定磁道，即確定由哪個讀寫磁頭讀寫，由電子線路實現(xiàn)?！_定磁道后，還要確定所要讀寫數(shù)據(jù)在磁盤上的位置（如在哪一個扇區(qū)）。這實際上就是在等待要讀寫的扇區(qū)轉到讀寫磁頭下面。這是機械動作。這段時間一般稱為旋轉延遲（rotationaldelay）時。真正進行讀寫時間。14在磁盤組上一次讀寫的時間主要為：

tio＝tseek＋tlatency＋trw其中，tseek是平均尋查時間，是把磁頭定位到要求柱面所需時間，這個時間的長短取決于磁頭移過的柱面數(shù)。tlatency是平均等待時間，是將磁頭定位到指定塊所需時間。trw是傳送一個扇區(qū)數(shù)據(jù)所需的時間。在MS-DOS系統(tǒng)中，多個扇區(qū)集結成組，稱為簇。簇是文件分配的最小單位，其大小由操作系統(tǒng)決定。在UNIX系統(tǒng)中不使用簇，文件分配的最小單位和讀寫的最小單位是一個扇區(qū)，稱為一個塊（block）。磁盤一次讀寫操作訪問一個扇區(qū)，稱為訪問“一頁”（page）或“一塊”（block），又稱為“一次訪外”。15例如在從磁盤向內存讀入一個扇區(qū)的數(shù)據(jù)時，數(shù)據(jù)被存放到輸入緩沖區(qū)，如果下次需要讀入同一個扇區(qū)的數(shù)據(jù)，就可以直接從緩沖區(qū)中讀取數(shù)據(jù)，不需要重新讀盤。緩沖區(qū)大小應與操作系統(tǒng)一次讀寫的塊的大小相適應，這樣可以通過操作系統(tǒng)一次讀寫把信息全部存入緩沖區(qū)中，或把緩沖區(qū)中的信息全部寫出到磁盤。如果緩沖區(qū)大小與磁盤上的塊大小不適配，就會造成內存空間的浪費。緩沖區(qū)的構造可以看作一個先進先出的隊列。

17緩沖區(qū)的定義及其操作

#include<iostream.h>#include<assert.h>constintDefaultSize=2048;template<classT>structbuffer{

T*data; //緩沖區(qū)數(shù)組intcurrent,maxSize; //當前指針,緩沖區(qū)容量

buffer

(intsz=DefaultSize):maxSize(sz),current(0){data=newT[sz];assert(data!=NULL);}

～buffer(){delete[]data;}18voidOutputInfo(ostream&out,Tx);//緩沖區(qū)輸出voidInputInfo(istream&in,T&x);//緩沖區(qū)輸入};template<classT>voidbuffer<T>::OutputInfo(ostream&out,Tx){if(current==maxSize){ for(inti=0;i<maxSize;i++)out<<data[i];

current=0; }

data[current]=x;current++;};19文件組織什么是文件文件是存儲在外存上的數(shù)據(jù)結構。文件分操作系統(tǒng)文件和數(shù)據(jù)庫文件操作系統(tǒng)中的文件是流式文件：是沒有結構的字符流數(shù)據(jù)庫文件是具有結構的數(shù)據(jù)集合數(shù)據(jù)結構中討論的是數(shù)據(jù)庫文件。操作系統(tǒng)對文件是按物理記錄讀寫的，在數(shù)據(jù)庫中文件按頁塊存儲和讀寫。文件的基本概念21文件的組成文件由記錄組成；記錄由若干數(shù)據(jù)項組成。記錄是文件存取的基本單位，數(shù)據(jù)項是文件可使用的最小單位。從不同的觀點，文件記錄分為邏輯記錄和物理記錄。前者是面向用戶的基本存取單位，后者是面向外設的基本存取單位。能夠唯一標識一個記錄的數(shù)據(jù)項或數(shù)據(jù)項集稱為主關鍵碼項，其值稱為主關鍵碼；不唯一標識一個記錄的數(shù)據(jù)項或數(shù)據(jù)項集稱為次關鍵碼項，其值稱為次關鍵碼。22文件結構包括文件的邏輯結構、文件的存儲結構和文件的操作。文件的邏輯結構是線性結構，各個記錄以線性方式排列。文件的存儲結構是指文件在外存上的組織方式，它與文件特性有關。

順序組織索引組織直接存取組織（散列組織）文件的操作是定義在邏輯結構上的，但操作的具體實現(xiàn)要在存儲結構上進行。23順序文件(SequentialFile)順序文件中的記錄按它們進入文件的先后順序存放，其邏輯順序與物理順序一致。順序文件的存儲方式連續(xù)文件：文件的全部記錄順序地存放外存的一個連續(xù)的區(qū)域中。優(yōu)點是存取速度快、存儲利用率高、處理簡單。缺點是區(qū)域大小需事先定義，不能擴充。串聯(lián)文件：文件記錄成塊存放于外存中，在塊中記錄順序連續(xù)存放，但塊與塊之間可以不連續(xù)，通過塊鏈指針順序鏈接。特點是文件可以擴充、存儲利用率高，便于更新。順序文件通常存放在順序存取設備（如磁帶）上或直接存取設備（如磁盤）上。25順序文件的順序存取：存取效率很高！順序文件的隨機存?。好看味紡牡谝粋€記錄開始找，花費許多定位時間，存取效率很低！順序文件按關鍵碼存?。号c順序搜索類似，速度很慢！順序文件的修改操作采用批處理方式完成。將修改請求存放于事務文件中。執(zhí)行時，對每一個請求Q：若Q是刪除或更新請求，則當掃描到主文件中與Q關鍵碼相等的記錄R時，依Q對R進行刪除或更新；若Q是插入請求，則等主文件掃描到適當位置時執(zhí)行插入動作。順序文件的主要優(yōu)點是順序存取速度快，因此多用于順序存取設備（如磁帶）。順序文件(SequentialFile)26直接存取文件(DirectAccessFile)

（散列文件）文件記錄的邏輯順序與物理順序不一定相同。通過記錄的關鍵碼可直接確定該記錄的地址。利用散列技術組織文件。處理類似散列法，但它是存儲在外存上的。使用散列函數(shù)把關鍵碼集合映射到地址集合時，往往會產生地址沖突，處理沖突有兩種處理方式：按桶散列可擴充散列

27在這種散列文件中刪除記錄時，因為可能需要重新鏈接，所以只需做一個邏輯刪除標記即可，待系統(tǒng)做周期性重構時再做物理刪除。桶大小為3的溢出桶鏈表示例

070∧512204246O1597177∧262157∧116613∧285635208O2923076∧0123456O1O2O3O4O5O6O7015337988O3817117390O4

575540435∧362∧基桶編號基桶區(qū)溢出桶編號溢出桶區(qū)29(b)分布式溢出空間溢出桶按照一定的間隔分布在基桶之間。如果有一個基桶溢出了，系統(tǒng)就將記錄存放在下一個溢出桶中。

如果溢出桶自己溢出了，則使用下一個相繼的溢出桶，這需要第二次溢出處理。01234567891011121314分布式溢出桶基桶基桶基桶溢出桶溢出桶30如果系統(tǒng)對基桶按0,1,2,3,4,5,…進行編號，在按間隔G=5插入溢出桶后，可按下列公式按字節(jié)求出各個桶的實際存儲地址：其中，B0是在文件中第0號桶的起始地址，B是每個桶的字節(jié)數(shù)。在括號中的除數(shù)5表示每隔5個基桶安排一個溢出桶。(c)

相繼溢出法此方法不設置溢出桶。當記錄應存放的桶溢出時，溢出記錄存放到下一個相繼的桶中。31如果該桶已滿，就把它放到再下一個桶中，如此處理，直至把記錄存放好。相繼溢出法的優(yōu)點是對溢出不需要漫長的尋找。緊鄰的桶通常相距不多于一次磁盤旋轉。但當鄰近的多個桶被擠滿時，則為了查找空閑空間就需要檢查許多桶。如果桶的容量很小更是如此。362177597157817575070246015542

389116204512435337117635613262988285923076208相繼溢出法

01243567981032(2)可擴充散列這是基于數(shù)字搜索樹的一種散列方法，細節(jié)稍后介紹。散列文件具有隨機存放、記錄不需進行排序、插入刪除方便、存取速度快、不需要索引區(qū)和節(jié)省存儲空間等優(yōu)點。散列文件不能順序存取，只能按關鍵碼隨機存取。在經過多次插入、刪除后，可能出現(xiàn)溢出桶滿而基桶內多數(shù)記錄已被刪除的情況。此時需要重新組織文件。

33索引文件(IndexedFile)索引文件由索引表和數(shù)據(jù)表組成。索引表用于指示邏輯記錄與物理記錄間的對應關系，它是按關鍵碼有序的表。索引順序文件：文件數(shù)據(jù)表也按關鍵碼有序。此時可對文件數(shù)據(jù)表分組，一組記錄對應一個索引項。稱這種索引表為稀疏索引。索引非順序文件：文件數(shù)據(jù)表中記錄未按關鍵碼有序。此時，每一個文件數(shù)據(jù)表記錄必須對應索引項。稱這種索引表為稠密索引。34靜態(tài)索引：采用多級索引結構，每一級索引均為有序表。優(yōu)點是結構簡單，缺點是修改很不方便，每次修改都要重組索引。動態(tài)索引：采用可動態(tài)調整的平衡搜索樹結構，如二叉搜索樹、B_樹與B+樹等。優(yōu)點是插入、刪除和搜索都很方便。在文件中搜索時，訪問外存所花費時間比在內存中搜索所需的時間大得多，因此，外存上搜索一個記錄的時間代價主要取決于訪問外存的次數(shù)，即索引樹的高度。35

01k2k3k4k5k6k7k索引表數(shù)據(jù)表職工號姓名性別職務婚否…83張珊女教師已婚…08李斯男教師已婚…03王璐男教務員已婚…95劉琪女實驗員未婚…24岳跋男教師已婚…47周斌男教師已婚…17胡江男實驗員未婚…51林青女教師未婚…keyaddr032k081k176k244k475k517k830953k索引非順序文件示例362212133029333642444839406074567980669282889894子表1子表2子表3子表4數(shù)據(jù)區(qū)33488098索引表1234max_min_keyaddr索引順序文件示例當記錄在外存中有序存放時，可以把所有n個記錄分為b個子表(塊)存放，一個索引項對應數(shù)據(jù)表中一組記錄(子表)。37對索引順序文件進行搜索，一般分為兩級:先在索引表ID中搜索給定值K,確定滿足

ID[i-1].max_key<K

ID[i].max_key

的i值,即待查記錄可能在的子表的序號。然后再在第i個子表中按給定值搜索要求的記錄。索引表是按max_key有序的,且長度也不大,可以折半搜索，也可以順序搜索。各子表內各個記錄如果也按關鍵碼有序,可以采用折半搜索或順序搜索;如果不是按關鍵碼有序,只能順序搜索。38索引順序文件的搜索成功時的平均搜索長度

ASLIndexSeq=ASLIndex

+ASLSubList其中,ASLIndex

是在索引表中搜索子表位置的平均搜索長度，ASLSubList是在子表內搜索記錄位置的搜索成功的平均搜索長度。設把長度為n的表分成均等的b個子表，每個子表s個記錄，則b=n/s。又設表中每個記錄的搜索概率相等，則每個子表的搜索概率為1/b，子表內各記錄的搜索概率為1/s。若對索引表和子表都用順序搜索，則索引順序搜索的搜索成功時的平均搜索長度為ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+139索引順序文件的平均搜索長度與表中的記錄個數(shù)n有關，與每個子表中的記錄個數(shù)s有關。在給定n的情況下，s應選擇多大？用數(shù)學方法可導出,當s=時,ASLIndexSeq取極小值+1。這個值比順序搜索強，但比折半搜索差。但如果子表存放在外存時，還要受到頁塊大小的制約。若采用折半搜索確定記錄所在的子表,則搜索成功時的平均搜索長度為

ASLIndexSeq=ASLIndex

+ASLSubList

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/240對包含有大量數(shù)據(jù)記錄的數(shù)據(jù)表或文件進行搜索時，最常用的是針對記錄的主關鍵碼建立索引。主關鍵碼可以唯一地標識該記錄。用主關鍵碼建立的索引叫做主索引。主索引的每個索引項給出記錄的關鍵碼和記錄在表或文件中的存放地址。但在實際應用中有時需要針對其它屬性進行搜索。例如，查詢如下的職工信息：

(1)列出所有教師的名單；

(2)已婚的女性職工有哪些人？

記錄關鍵碼

key

記錄存放地址addr多關鍵碼文件41這些信息在數(shù)據(jù)表或文件中都存在，但都不是關鍵碼，為回答以上問題，只能到表或文件中去順序搜索，搜索效率極低。因此，除主關鍵碼外，可以把一些經常搜索的屬性設定為次關鍵碼，并針對每一個作為次關鍵碼的屬性，建立次索引。在次索引中，列出該屬性的所有取值，并對每一個取值建立有序鏈表，把所有具有相同屬性值的記錄按存放地址遞增的順序或按主關鍵碼遞增的順序鏈接在一起。多關鍵碼文件的組織方法：多重表文件倒排表42次索引的索引項由次關鍵碼、鏈表長度和存儲頭指針等三部分組成。例如，為了回答上述的查詢，我們可以分別建立“性別”、“婚否”和“職務”次索引。性別次索引次關鍵碼男女計數(shù)53地址指針指針0308172447518395多重表文件43婚否次索引次關鍵碼已婚未婚計數(shù)53地址指針指針0308244783175195職務次索引次關鍵碼教師教務員實驗員計數(shù)512地址指針指針0824475183031795多重表文件44

(1)列出所有教師的名單； (2)已婚的女性職工有哪些人？對于查詢(1)：在數(shù)據(jù)表中建立“職務鏈”，把所有次關鍵碼為“教師”的記錄通過這個鏈連接起來。通過次索引，找到“職務”鏈的頭地址，再到數(shù)據(jù)表中順著“職務”鏈找到所有“職務為教師”的記錄。需遍歷整個數(shù)據(jù)表，檢索效率較低。對于查詢(2)：需要建“婚否”和“性別”兩個鏈，然后按照上面類似的方法進行檢索，同樣需要遍歷整個數(shù)據(jù)表，檢索效率低。多重表文件45倒排表是次索引的一種實現(xiàn)。在表中所有次關鍵碼的鏈都保存在次索引中，僅通過搜索次索引就能找到所有具有相同屬性值的記錄。在次索引中記錄記錄存放位置的指針可以用主關鍵碼表示:可通過搜索次索引確定該記錄的主關鍵碼,再通過搜索主索引確定記錄的存放地址。次索引的索引項由次關鍵碼、鏈表長度和鏈表本身等3部分組成。倒排表(InvertedIndexList)46對于前面的查詢(1)：通過順序訪問“職務”次索引中的“教師”鏈即可。對于前面的查詢(2)：通過對“性別”和“婚否”次索引中的“女性”鏈和“已婚”鏈進行求“交”運算即可。在倒排表中各個屬性鏈表的長度大小不一,管理比較困難。為此引入單元式倒排表。在單元式倒排表中,索引項中不存放記錄的存儲地址,存放該記錄所在硬件區(qū)域的標識。硬件區(qū)域可以是磁盤柱面、磁道或一個頁塊,以一次I/O操作能存取的存儲空間作為硬件區(qū)域為最好倒排表(InvertedIndexList)47為使索引空間最小,在索引中標識這個硬件區(qū)域時可以使用一個能轉換成地址的二進制數(shù),整個次索引形成一個(二進制數(shù)的)位矩陣。例如,對于記錄學生信息的文件,次索引可以是如圖所示的結構。二進位的值為1的硬件區(qū)域包含具有該次關鍵碼的記錄。如果在硬件區(qū)域1，……中有要求的記錄。然后將硬件區(qū)域1，……等讀入內存，在其中進行檢索，確定就可取出所需記錄。倒排表(InvertedIndexList)48單元式倒排表結構49針對一個查詢：找出所有北京籍學建筑的男學生?？梢詮摹靶詣e”、“籍貫”、“專業(yè)”三個次索引分別抽取屬性值為“男”、“北京”、“建筑”的位向量，按位求交，求得滿足查詢要求的記錄在哪些硬件區(qū)域中，再讀入這些硬件區(qū)域，從中查找所要求的數(shù)據(jù)記錄。5010.3外排序當待排序的記錄數(shù)目特別多時，在內存中不能一次處理。必須把它們以文件的形式存放于外存，排序時再把它們一部分一部分調入內存進行處理。這樣，在排序過程中必須不斷地在內存與外存之間傳送數(shù)據(jù)。這種基于外部存儲設備（或文件）的排序技術就是外排序。51基于磁盤進行的排序多使用歸并排序方法。其排序過程主要分為兩個階段：建立用于外排序的內存緩沖區(qū)。根據(jù)它們的大小將輸入文件劃分為若干段,用某種內排序方法對各段進行排序。經過排序的段叫做初始歸并段(Run)。當它們生成后就被寫到外存中去。按歸并樹模式,把①生成的初始歸并段加以歸并,一趟趟擴大歸并段和減少歸并段數(shù),直到最后歸并成一個大歸并段為止。外排序的基本過程52示例：設有一個包含4500個記錄的輸入文件?，F(xiàn)用一臺其內存至多可容納750個記錄的計算機對該文件進行排序。輸入文件放在磁盤上,磁盤每個頁塊可容納250個記錄,這樣全部記錄可存儲在4500/250＝18個頁塊中。輸出文件也放在磁盤上,用以存放歸并結果。由于內存中可用于排序的存儲區(qū)域能容納750個記錄,因此內存中恰好能存3個頁塊的記錄。在外排序一開始,把18塊記錄,每3塊一組,讀入內存。利用某種內排序方法進行內排序,形成初始歸并段,再寫回外存?？偣部傻玫?個初始歸并段。然后一趟一趟進行歸并排序。53兩路歸并排序的歸并樹R1750R2750R3750R4750R5750R6750初始歸并段R121500R341500R561500R12343000R1234564500第一趟歸并結果

第二趟歸并結果

第三趟歸并結果

54若把內存區(qū)域等份地分為3個緩沖區(qū)。其中的兩個為輸入緩沖區(qū),一個為輸出緩沖區(qū),可以在內存中利用簡單2路歸并函數(shù)merge()

實現(xiàn)2路歸并。首先,從參加歸并排序的兩個輸入歸并段R1和R2中分別讀入一塊,放在輸入緩沖區(qū)1和輸入緩沖區(qū)2中。然后在內存中進行2路歸并，歸并結果順序存放到輸出緩沖區(qū)中。輸入緩沖區(qū)2輸入緩沖區(qū)1輸出緩沖區(qū)55若總記錄個數(shù)為n，磁盤上每個頁塊可容納b個記錄，內存緩沖區(qū)可容納i個頁塊，則每個初始歸并段長度為len=i*b，可生成m=n/len

個等長的初始歸并段。在做2路歸并排序時,第一趟從m個初始歸并段得到m/2

個歸并段，以后各趟將從l(l>1)個歸并段得到l/2

個歸并段?？倸w并趟數(shù)等于歸并樹的高度減一：log2m。估計2路歸并排序時間tES

的上界為：

tES=m*tIS+d*tIO+S*n*tmg56

對4500個記錄排序的例子,各種操作的計算時間如下：讀18個輸入塊,內部排序6段,寫18個輸出塊 ＝6tIS＋36tIO

成對歸并初始歸并段R1～R6

＝36

tIO＋4500

tmg

歸并兩個具有1500個記錄的歸并段R12和R34

＝24

tIO＋3000

tmg

最后將

R1234和R56歸并成一個歸并段

＝36

tIO＋4500

tmg合計tES＝6

tIS＋132

tIO＋12000tmg57

由于tIO=tseek+tlatency+trw,其中,tseek和tlatency是機械動作，而trw、tIS、tmg是電子線路的動作,所以tIO遠遠大于tIS和tmg。想要提高外排序的速度，應著眼于減少d。若對相同數(shù)目的記錄，在同樣頁塊大小的情況下做3路歸并或做6路歸并(當然,內存緩沖區(qū)的數(shù)目也要變化)，則可做大致比較：歸并路數(shù)k

總讀寫磁盤次數(shù)d

歸并趟數(shù)S2 132 3

3 108 2

6 72 158

增大歸并路數(shù),可減少歸并趟數(shù),從而減少總讀寫磁盤次數(shù)d。對m個初始歸并段,做k路平衡歸并,歸并樹可用正則k叉樹(即只有度為k與度為0的結點的k叉樹)來表示。第一趟可將m個初始歸并段歸并為l=m/k個歸并段，以后每一趟歸并將l個歸并段歸并成l=l/k個歸并段，直到最后形成一個大的歸并段為止。歸并趟數(shù)S＝logkm＝樹的高度減一。59k路平衡歸并(k-wayBalancedmerging)做k路平衡歸并時,如果有m

個初始歸并段,則相應的歸并樹有l(wèi)ogkm+1層,需要歸并logkm趟。下圖給出對有36個初始歸并段的文件做6路平衡歸并時的歸并樹。60做內部k路歸并時,在k個記錄中選擇最小者，需要順序比較k-1次。每趟歸并n個記錄需要做(n-1)*(k-1)次比較,S趟歸并總共需要的比較次數(shù)為:

S*(n-1)*(k-1)=logkm*(n-1)*(k-1)=log2m*(n-1)*(k-1)/log2k

在初始歸并段個數(shù)m與記錄個數(shù)n一定時,log2m*(n-1)=const,而(k-1)/log2k

在k增大時趨于無窮大。因此,增大歸并路數(shù)k,會使得內部歸并的時間增大。61使用“敗者樹”從k個歸并段中選最小者,當k較大時(k

6)，選出排序碼最小的記錄只需比較log2k次。S*(n-1)*log2k=logkm*(n-1)*log2k=log2m*(n-1)*log2k/log2k=log2m*(n-1)排序碼比較次數(shù)與k無關,總的內部歸并時間不會隨k的增大而增大。下面討論利用敗者樹在k個輸入歸并段中選擇最小者，實現(xiàn)歸并排序的方法。62

敗者樹是一棵正則的完全二叉樹。其中每個葉結點存放各歸并段在歸并過程中當前參加比較的記錄；每個非葉結點記憶它兩個子女結點中記錄排序碼大的結點(即敗者)；因此，根結點中記憶樹中當前記錄排序碼最小的結點(最小記錄)。敗者樹與勝者樹的區(qū)別在于一個選擇了敗者(排序碼大者),一個選擇了勝者(排序碼小者)。示例：設有5個初始歸并段,它們中各記錄的排序碼分別是：63

Run0:{17,21,∞}Run1:{05,44,∞}Run2:{10,12,∞}Run3:{29,32,∞}Run4:{15,56,∞}冠軍(最小記錄),輸出段1當前記錄29321556172105441012151005172930241k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3選中64次最小記錄輸出段1最小記錄，段1下一記錄參選，調整敗者樹293215561721441012151044172930142k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3選中65

敗者樹的高度為log2k+1，在每次調整,找下一個具有最小排序碼記錄時,最多做log2k次排序碼比較。在內存中應為每一個歸并段分配一個輸入緩沖區(qū),其大小應能容納一個頁塊的記錄,編號與歸并段號一致。每個輸入緩沖區(qū)應有一個指針,指示當前參加歸并的記錄。在內存中還應設立一個輸出緩沖區(qū),其大小相當于一個頁塊大小。它也有一個緩沖區(qū)指針,指示當前可存放結果記錄的位置。每當一個記錄i被選出,就執(zhí)行OutputRecord(i)操作,將記錄存放到輸出緩沖區(qū)中。66在實現(xiàn)利用敗者樹進行多路平衡歸并算法時,把敗者樹的葉結點和非葉結點分開定義。敗者樹葉結點key[]有k+1個,key[0]到key[k-1]存放各歸并段當前參加歸并的記錄的排序碼，key[k]是輔助工作單元,在初始建立敗者樹時使用:存放一個最小的在各歸并段中不可能出現(xiàn)的排序碼:-MaxNum。敗者樹非葉結點loser[]有k個,其中l(wèi)oser[1]到loser[k-1]存放各次比較的敗者的歸并段號,loser[0]中是最后勝者所在歸并段號。另外還有一個存放各歸并段參加歸并記錄的數(shù)組r[k]。67k路平衡歸并排序算法constintMaxValue=……; //當作無窮大值使用voidkwaymerge(Element*r,intk){inti,q;

r=newElement[k]; //敗者樹中的k個記錄int*key=newint[k+1]; //記錄的排序碼

int*loser=newint[k]; //存放敗者樹for(i=0;i<k;i++)//葉結點的值{InputRecord(r[i]);key[i]=r[i].key;} for(i=0;i<k;i++)loser[i]=k;

key[k]=-Maxvalue; //初始化

68for(i=k-1;i>0;i--)adjust(key,loser,k,i);

//從key[k-1]到key[0]調整形成敗者樹 while(key[loser[0]]!=MaxValue){//選冠軍

q=loser[0]; //取當前最小記錄

OutputRecord(r[q]); //寫到輸出歸并段

InputRecord(r[q]); //讀入下一個記錄

key[q]=r[q].key;

adjust(key,loser,k,q); //從key[q]起調整 }

Outputendofrunmarker; //輸出段結束標志 delete[]r;delete[]key;delete[]loser;};69自某葉結點key[q]到敗者樹根結點

的調整算法

voidadjust(intkey[];intloser[];intk;intq){//從敗者樹某葉結點key[q]起到根進行比較,將最小//

key記錄所在歸并段的段號記入loser[0]。for(intt=(k+q)/2;t>0;t/=2)

//t是q的雙親if(key[loser[t]]<key[q]){

//敗者記入loser[t],勝者記入q

inttemp=q;q=loser[t];loser[t]=temp;}//q與loser[t]交換

loser[0]=q;};70每選出一個當前排序碼最小的記錄,就需要在將它送入輸出緩沖區(qū)之后,從相應歸并段的輸入緩沖區(qū)中取出下一個參加歸并的記錄,替換已經取走的最小記錄,再從葉結點到根結點,沿某一特定路徑進行調整,將下一個排序碼最小記錄的歸并段號調整到loser[0]中。段結束標志MaxNum升入loser[0],排序完成。歸并路數(shù)k不是越大越好。歸并路數(shù)k增大,相應需增加輸入緩沖區(qū)個數(shù)。如果可供使用的內存空間不變,勢必要減少每個輸入緩沖區(qū)的容量,使內外存交換數(shù)據(jù)的次數(shù)增大。71利用敗者樹進行5路平衡歸并的過程(1)初始狀態(tài)(2)加入15,調整555-55k3k4k5k0k1k2ls1ls0ls2ls3ls4k25ls3k15k0ls24ls415k4-k5k35ls15ls017051029152917051072(3)加入29,調整(4)加入10,調整2915317405510-55k3k4k5k0k1k2ls1ls0ls2ls3ls410k2205ls3k1174k0ls23ls415k4-k529k35ls15ls0732915317405210-15k3k4k5k0k1k2ls1ls0ls2ls3ls410k2205ls3k1170k0ls23ls415k4-k529k34ls11ls0(5)加入05,調整(6)加入17,調整輸出0574(7)輸出05后調整(8)輸出10后調整291531704411042k3k4k0k1k2ls1ls0ls2ls3ls412k2144ls3k1170k0ls23ls415k429k34ls12ls0輸入44輸出12輸出10輸入12752915317044214k3k4k0k1k2ls1ls0ls2ls3ls4k2244ls3k1173k0ls24ls456k429k31ls10ls0輸入輸出17輸出15輸入56(9)輸出12后調整(10)輸出15后調整762956421344210k3k4k0k1k2ls1ls0ls2ls3ls4k2244ls3k10k0ls24ls456k429k31ls13ls0輸入21輸出29輸出21輸入(11)輸出17后調整(12)輸出21后調整

77(13)輸出29后調整(14)輸出32后調整32564044213k3k4k0k1k2ls1ls0ls2ls3ls4k2244ls3k10k0ls23ls456k4k34ls11ls0輸入32輸出44輸出32輸入78(15)輸出44后調整(16)輸出56后調整5630214k3k4k0k1k2ls1ls0ls2ls3ls4k22ls3k10k0ls23ls4k4k31ls14ls0輸出，結束輸出56輸入輸入79外部搜索

ISAM(索引順序存取方法文件)它是靜態(tài)索引結構。典型的例子是對磁盤上的數(shù)據(jù)文件建立盤組、柱面、磁道三級地址的多級索引。ISAM文件用柱面索引對各個柱面進行索引。一個柱面索引項保存該柱面上的最大關鍵碼（最后一個記錄）以及柱面開始地址指針。如果柱面太多，可以建立柱面索引的分塊索引，即主索引。主索引不太大，一般常駐內存。80C0T0

C0T1R20R25R30R40R45R48R55C0T2R64R69R74R78R83R91R100C0T3R110R125C0T4

溢出區(qū)……55C0T1100C0T2125C0T3C1T0

C1T1R146R151R159R164R168R172R181C1T2R189R190R193R198R203R210R222C1T3R234R246R255R269R270

C1T4

溢出區(qū)……181C1T1222C1T2270C1T3125C0T0270C1T0

…525C5T0714C6T0833C7T0…1510C11T0……5540C84T0主索引525C0T11510C6T1

………5540C79T1C7T0

C7T1R720R724R727R736R743R759R758C7T2R765R769R777R781R785R790R793C7T3R799R801R825R833

C7T4

溢出區(qū)……758C7T1793C7T2833C7T3柱面索引各柱面信息磁道索引磁道索引磁道索引81在每個柱面上，所有數(shù)據(jù)記錄存放于基本區(qū)，此外保留一部分磁道作為溢出區(qū)。所有記錄在基本區(qū)按關鍵碼升序排列，后一磁道所有記錄的關鍵碼均大于前一磁道所有記錄的關鍵碼。在一個柱面上所有記錄分布在一系列磁道上，通過磁道索引進行搜索。磁道索引一般放在每個柱面上第0號磁道中，每個磁道索引的索引項由兩部分組成：最大關鍵碼開始地址指針最大關鍵碼溢出鏈頭指針

基本區(qū)索引項溢出區(qū)索引項82基本區(qū)索引項存放本道在基本區(qū)最大關鍵碼（在基本區(qū)該磁道最后一個記錄）和本道在基本區(qū)的開始地址，溢出區(qū)索引項存放本道在溢出區(qū)最大關鍵碼和本道在溢出區(qū)中溢出記錄鏈（有序鏈表）的第一個結點地址。在某一磁道插入一個新記錄時，如果原來該磁道基本區(qū)記錄已經放滿，則根據(jù)磁道索引項指示位置插入新記錄后，把最后的溢出記錄（具有最大關鍵碼）移出磁道基本區(qū)，再根據(jù)溢出索引項將這個溢出記錄放入溢出區(qū)，并以有序鏈表插入算法將溢出記錄鏈入。

83動態(tài)索引結構現(xiàn)在我們所討論的m路搜索樹多為可以動態(tài)調整的多路搜索樹，它的遞歸定義為：一棵m路搜索樹,它或者是一棵空樹,或者是滿足如下性質的樹：根最多有m棵子樹,并具有如下的結構：

(n,P0,K1,P1,K2,P2,……,Kn,Pn

)其中,Pi是指向子樹的指針,0≤i≤n<m;Ki是關鍵碼,1≤i≤n<m。Ki

<Ki+1,1≤i<n。動態(tài)的m路搜索樹84在子樹

Pi

中所有的關鍵碼都小于Ki+1,且大于Ki，0<i<n。在子樹Pn

中所有的關鍵碼都大于Kn；在子樹P0

中的所有關鍵碼都小于K1。子樹

Pi

也是m路搜索樹，0≤i<n

。一棵3路搜索樹的示例352040abcde25301015455085m叉搜索樹的C++描述

constintMaxValue=……;//關鍵碼集合中不可能有的最大值template<classT>structMtreeNode{ //樹結點定義intn; //索引項個數(shù)

MtreeNode<T>*parent; //父結點指針

Tkey[m+1]; //索引項關鍵碼域 int*recptr[m+1]; //索引項記錄地址指針MtreeNode<T>*ptr[m+1]; //子樹結點指針};86template<classT> //搜索結果三元組structTriple{MtreeNode<T>*r; //結點地址指針inti; //結點中關鍵碼序號iinttag; //tag=0,成功;=1,失敗};template<classT>classMtree{ //m叉搜索樹定義protected:

MtreeNode<T>*root; //根指針intm; //路數(shù)public:

Triple<T>Search(constT&x); //搜索

};87AVL樹是2路搜索樹。若已知m路搜索樹的度m和它的高度h,則樹中的最大結點個數(shù)為：每個結點中最多有m-1個關鍵碼，在一棵高度為h的m路搜索樹中關鍵碼最大個數(shù)為mh-1。高度h=3的二叉搜索樹,關鍵碼最大數(shù)為7；高度h=4的3路搜索樹,關鍵碼最大數(shù)為34-1=80。88在m路搜索樹上的 搜索過程是一個在 結點內搜索和自根 結點向下逐個結點 搜索的交替的過程。m路搜索樹的搜索算法352040abcde253010154550root搜索3589template<classT>Triple<T>Mtree<T>::Search(constT&x){//用關鍵碼x搜索駐留在磁盤上的m路搜索樹//各結點格式為n,p[0],(k[1],p[1]),…,(k[n],p[n]),n<m//函數(shù)返回一個類型為Triple(r,i,tag)的記錄。//tag=0,表示x在結點r中找到,該結點的k[i]等于x;//tag=1,表示沒有找到x,可插入結點為r,插入到該//結點的k[i]與k[i+1]之間。

Tripleresult; //記錄搜索結果三元組

GetNode(root); //從盤上讀取結點root

MtreeNode<T>*p=root,*q=NULL;

//p是掃描指針,q是p的父結點指針90while(p!=NULL){ //從根開始檢測inti=0;p->key[(p->n)+1]=MaxValue;while(p->key[i+1]<x)i++; //在結點內搜索if(p->key[i+1]==x){ //搜索成功

result.r=p;result.i=i+1;result.tag=0;returnresult;}

q=p;p=p->ptr[i];

//本結點無x,q記下當前結點,p下降到子樹

GetNode(p); //從磁盤上讀取結點p }

result.r=q;result.i=i;result.tag=1;

returnresult; //搜索失敗,返回插入位置};91提高搜索樹的路數(shù)m,可以改善樹的搜索性能。對于給定的關鍵碼數(shù)n，如果搜索樹是平衡的，可以使m路搜索樹的性能接近最佳。下面將討論一種稱之為B樹的平衡的m路搜索樹。92B樹一棵m階B樹是一棵平衡的m路搜索樹,它或者是空樹,或者是滿足下列性質的樹：根結點至少有2個子女。除根結點以外的所有結點(不包括失敗結點)至少有m/2個子女。所有的失敗結點都位于同一層。在B樹中的“失敗”結點是當x不在樹中時才能到達的結點。這些結點實際不存在，指向它們的指針為NULL。它們不計入樹的高度。93注意，m階B樹繼承了m路搜索樹的定義。原來m路搜索樹定義中的規(guī)定在m階B樹中都保留。事實上，在B樹的每個結點中還包含有一組指針recptr[m+1]，指向實際記錄的存放地址。key[i]與recptr[i](1≤i≤n<m)形成一個索引項(key[i],

recptr[i])，通過key[i]可找到某個記錄的存儲地址recptr[i]。在討論B樹結構的操作時先不涉及recptr[i]，因此在后續(xù)討論中該指針不出現(xiàn)。94一棵B樹是平衡的m路搜索樹，但一棵平衡的m路搜索樹不一定是B樹。2-3樹是3階的B樹，2-3-4樹是4階B樹。

非B樹 B樹30352040253010154550root4550354020root10152595B樹類和B樹結點類的定義

template<classT>classBtree:publicMtreetree<T>{ //B樹類定義//繼承m叉搜索樹的所有屬性和操作，//Search從Mtree繼承，MtreeNode直接使用public:

Btree(); //構造函數(shù)boolInsert(constT&x); //插入關鍵碼x boolRemove(T&x); //刪除關鍵碼x};96B樹的搜索算法B樹的搜索算法繼承了m路搜索樹Mtree上的搜索算法。B樹的搜索過程是一個在結點內搜索和循某一條路徑向下一層搜索交替進行的過程。搜索成功，報告結點地址及在結點中的關鍵碼序號；搜索不成功，報告最后停留的葉結點地址及新關鍵碼在結點中可插入的位置。B樹的搜索時間與B樹的階數(shù)m和B樹的高度h直接有關,必須加以權衡。

97在B樹上進行搜索,搜索成功所需的時間取決于關鍵碼所在的層次;搜索不成功所需的時間取決于樹的高度。定義B樹的高度h為葉結點（失敗結點的雙親）所在的層次，那么，樹的高度h與樹中的關鍵碼個數(shù)N之間有什么關系？如果讓B樹每層結點個數(shù)達到最大（m-1），且設關鍵碼總數(shù)為N,則樹的高度達到最小： N≤mh-1h≥logm(n+1)98如果讓m階B樹中每層結點個數(shù)達到最少，則B樹的高度可能達到最大。設樹中關鍵碼個數(shù)為N，從B樹的定義知：1層：1個結點2層：至少2個結點3層：至少2m/2個結點4層：至少2m/22個結點如此類推，h層：至少有2m/2

h-2個結點。所有這些結點都不是失敗結點。失敗結點在第h+1層，失敗結點個數(shù)為N+1。99這是因為樹中關鍵碼有N個，而失敗數(shù)據(jù)一般與已有關鍵碼交錯排列。因此，有N+1=失敗結點數(shù)=位于第h+1層的結點數(shù)

≥2m/2

h-1N≥2m/2

h-1-1

h-1≤log

m/2

((N+1)/2)h≤log

m/2

((N+1)/2)+1示例：若B樹的階數(shù)m=199,關鍵碼總數(shù)N=1999999，則B樹的高度h不超過

log1001000000+1=4100m值的選擇如果提高B樹的階數(shù)m,可以減少樹的高度,從而減少讀入結點的次數(shù),因而可減少讀磁盤的次數(shù)。事實上，m受到內存可使用空間的限制。當m很大超出內存工作區(qū)容量時，結點不能一次讀入到內存，增加了讀盤次數(shù)，也增加了結點內搜索的難度。

m值的選擇：應使得在B樹中找到關鍵碼x的時間總量達到最小。101這個時間由兩部分組成：從磁盤中讀入結點所用時間在結點中搜索x所用時間根據(jù)定義,B樹的每個結點的大小都是固定的,結點內有最多有m-1個索引項(keyi,recptri,Pi),1≤i<m。設keyi所占字節(jié)數(shù)為，recptri和Pi所占字節(jié)數(shù)為，則結點大小近似為m(+2)個字節(jié)。讀入一個結點所用時間為：

tseek+tlatency+m(+2)ttran=a+bm102B樹的插入B樹是從空樹起,逐個插入關鍵碼而生成的。在B樹中每個非失敗結點的關鍵碼個數(shù)都在

[m/2

-1,m-1] 之間。插入在某個葉結點開始。如果在關鍵碼插入后結點中的關鍵碼個數(shù)超出了上界m-1，則結點需要“分裂”，否則可以直接插入。實現(xiàn)結點“分裂”的原則是：設結點

p中已經有m-1個關鍵碼，當再插入一個關鍵碼后結點中的狀態(tài)為103

(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中

Ki<Ki+1,1

i<m這時必須把結點

p分裂成兩個結點p和q，它們包含的信息分別為：

結點p：

(m/2

-1,P0,K1,P1,……,Km/2

-1,Pm/2

-1)

結點q：(m-m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中間的關鍵碼Km/2

與指向新結點

q的指針形成一個二元組(Km/2,q)，插入到這兩個結點的雙親結點中去。104結點“分裂”的示例25375nP0K1P1K2P2p35375139nP0K1P1K2P2K3P3p加入139,結點溢出175nP0K1P1153nP0K1P11139nP0K1P1結點分裂

Pqm=3105示例:從空樹開始加入關鍵碼建立3階B樹n=1加入5353n=2加入755375n=3加入13975139534975n=5加入49,145751391454953n=6加入361391455336106在插入新關鍵碼時，需要自底向上地分裂結點，最壞情況下從被插關鍵碼所在葉結點到根的路徑上的所有結點都要分裂。

若設B樹的高度為h,則在自頂向下搜索到葉結點的過程中需要進行h次讀盤。n=7加入10149533613914510175107template<classT>boolBtree<T>::Insert(constT&x){//將關鍵碼x插入到一個m階B樹中。

Triple<T>loc=Search(x); //搜索x的插入位置 if(!loc.tag)returnfalse; //x已存在,不插入

MtreeNode<T>*p=loc.r,*q; //r是插入結點

MtreeNode<T>*ap=NULL,*t; //ap是右鄰指針B樹的插入算法108TK=x;intj=loc.i; //(K,ap)形成插入組 while(1){ if(p->n<m-1){ //關鍵碼個數(shù)未超出

insertkey(p,j,K,ap); //插入,且p->n加1

PutNode(p);returntrue; //輸出結點p}ints=(m+1)/2; //準備分裂結點

insertkey(p,j,K,ap); //先插入

q=newMtreeNode<T>; //建立新結點q

move(p,q,s,m); //向新結點移動

K=p->key[s];ap=q;

//(K,ap)形成向上插入二元組

109if(p->parent!=NULL){ //從下向上調整

t=p->parent;GetNode(t); //讀取父結點t

j=0;

t->key[(t->n)+1]=MAXKEY;//設監(jiān)視哨while(t->key[j+1]<K)j++; //順序搜索

q->parent=p->parent; //新結點的雙親

PutNode(p);PutNode(q); //輸出結點

p=t; //p上升到雙親,繼續(xù)調整}else{ //原來p是根,要產生新根

root=newMtreeNode<T>;

root->n=1;root->parent=NULL;110root->key[1]=K;

root->ptr[0]=p;root->ptr[1]=ap;

q->parent=p->parent=root;

PutNode(p);PutNode(q);PutNode(root);returntrue;

}}};當分裂一個非根的結點時需要向磁盤寫出2個結點,當分裂根結點時需要寫出3個結點。111假設我們所用的內存工作區(qū)足夠大,使得在向下搜索時,讀入的結點在插入后向上分裂時不必再從磁盤讀入。那么,在完成一次插入操作時需要讀/寫磁盤的最大次數(shù)為：

=找插入（葉）結點向下讀盤次數(shù)++分裂非根結點時寫盤次數(shù)++分裂根結點時寫盤次數(shù)= =h+2(h-1)+3=3h+1。112在B樹上刪除一個關鍵碼時，若結點中所剩關鍵碼個數(shù)少于下限，要考慮結點的調整或合并問題，刪除過程如下：首先需要找到這個關鍵碼所在的結點,從中刪去這個關鍵碼。若該結點不是葉結點，且被刪關鍵碼為Ki，1≤i≤n,則在刪去該關鍵碼之后,應以該結點Pi所指示子樹中的最小關鍵碼x來代替被刪關鍵碼Ki

所在的位置;然后在x

所在的葉結點中刪除x。B樹的刪除113在葉結點上的刪除有4種情況。被刪關鍵碼所在葉結點同時是根結點且刪除前該結點中關鍵碼個數(shù)n≥2，則直接刪去該關鍵碼并將修改后的結點寫回磁盤。被刪關鍵碼所在葉結點不是根結點且刪除前該結點中關鍵碼個數(shù)n≥m/2,則直接刪去該關鍵碼并將修改后的結點寫回磁盤,刪除結束。3649m=3刪除36491145558刪除55簡單刪除7580m=3刪除5510406560703050acbdefgh58758010406560703