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

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

文件組織

外排序

多級(jí)索引結(jié)構(gòu)

可擴(kuò)充散列Trie樹

第十章文件、外部排序

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

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

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

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

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

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

T*data; //緩沖區(qū)數(shù)組intcurrent,maxSize; //當(dāng)前指針,緩沖區(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文件組織什么是文件文件是存儲(chǔ)在外存上的數(shù)據(jù)結(jié)構(gòu)。文件分操作系統(tǒng)文件和數(shù)據(jù)庫文件操作系統(tǒng)中的文件是流式文件：是沒有結(jié)構(gòu)的字符流數(shù)據(jù)庫文件是具有結(jié)構(gòu)的數(shù)據(jù)集合數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)庫文件。操作系統(tǒng)對(duì)文件是按物理記錄讀寫的，在數(shù)據(jù)庫中文件按頁塊存儲(chǔ)和讀寫。文件的基本概念21文件的組成文件由記錄組成；記錄由若干數(shù)據(jù)項(xiàng)組成。記錄是文件存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位。從不同的觀點(diǎn)，文件記錄分為邏輯記錄和物理記錄。前者是面向用戶的基本存取單位，后者是面向外設(shè)的基本存取單位。能夠唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)集稱為主關(guān)鍵碼項(xiàng)，其值稱為主關(guān)鍵碼；不唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)集稱為次關(guān)鍵碼項(xiàng)，其值稱為次關(guān)鍵碼。22文件結(jié)構(gòu)包括文件的邏輯結(jié)構(gòu)、文件的存儲(chǔ)結(jié)構(gòu)和文件的操作。文件的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，各個(gè)記錄以線性方式排列。文件的存儲(chǔ)結(jié)構(gòu)是指文件在外存上的組織方式，它與文件特性有關(guān)。

順序組織索引組織直接存取組織（散列組織）文件的操作是定義在邏輯結(jié)構(gòu)上的，但操作的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。23順序文件(SequentialFile)順序文件中的記錄按它們進(jìn)入文件的先后順序存放，其邏輯順序與物理順序一致。順序文件的存儲(chǔ)方式連續(xù)文件：文件的全部記錄順序地存放外存的一個(gè)連續(xù)的區(qū)域中。優(yōu)點(diǎn)是存取速度快、存儲(chǔ)利用率高、處理簡(jiǎn)單。缺點(diǎn)是區(qū)域大小需事先定義，不能擴(kuò)充。串聯(lián)文件：文件記錄成塊存放于外存中，在塊中記錄順序連續(xù)存放，但塊與塊之間可以不連續(xù)，通過塊鏈指針順序鏈接。特點(diǎn)是文件可以擴(kuò)充、存儲(chǔ)利用率高，便于更新。順序文件通常存放在順序存取設(shè)備（如磁帶）上或直接存取設(shè)備（如磁盤）上。25順序文件的順序存?。捍嫒⌒屎芨撸№樞蛭募碾S機(jī)存取：每次都從第一個(gè)記錄開始找，花費(fèi)許多定位時(shí)間，存取效率很低！順序文件按關(guān)鍵碼存取：與順序搜索類似，速度很慢！順序文件的修改操作采用批處理方式完成。將修改請(qǐng)求存放于事務(wù)文件中。執(zhí)行時(shí)，對(duì)每一個(gè)請(qǐng)求Q：若Q是刪除或更新請(qǐng)求，則當(dāng)掃描到主文件中與Q關(guān)鍵碼相等的記錄R時(shí)，依Q對(duì)R進(jìn)行刪除或更新；若Q是插入請(qǐng)求，則等主文件掃描到適當(dāng)位置時(shí)執(zhí)行插入動(dòng)作。順序文件的主要優(yōu)點(diǎn)是順序存取速度快，因此多用于順序存取設(shè)備（如磁帶）。順序文件(SequentialFile)26直接存取文件(DirectAccessFile)

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

27在這種散列文件中刪除記錄時(shí)，因?yàn)榭赡苄枰匦骆溄?，所以只需做一個(gè)邏輯刪除標(biāo)記即可，待系統(tǒng)做周期性重構(gòu)時(shí)再做物理刪除。桶大小為3的溢出桶鏈表示例

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

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

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

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

389116204512435337117635613262988285923076208相繼溢出法

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

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

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

ID[i-1].max_key<K

ID[i].max_key

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

ASLIndexSeq=ASLIndex

+ASLSubList其中,ASLIndex

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

ASLIndexSeq=ASLIndex

+ASLSubList

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

log2(1+n/s)+s/240對(duì)包含有大量數(shù)據(jù)記錄的數(shù)據(jù)表或文件進(jìn)行搜索時(shí)，最常用的是針對(duì)記錄的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標(biāo)識(shí)該記錄。用主關(guān)鍵碼建立的索引叫做主索引。主索引的每個(gè)索引項(xiàng)給出記錄的關(guān)鍵碼和記錄在表或文件中的存放地址。但在實(shí)際應(yīng)用中有時(shí)需要針對(duì)其它屬性進(jìn)行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?/p>

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

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

記錄關(guān)鍵碼

key

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

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

第二趟歸并結(jié)果

第三趟歸并結(jié)果

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

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

個(gè)等長(zhǎng)的初始?xì)w并段。在做2路歸并排序時(shí),第一趟從m個(gè)初始?xì)w并段得到m/2

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

個(gè)歸并段。總歸并趟數(shù)等于歸并樹的高度減一：log2m。估計(jì)2路歸并排序時(shí)間tES

的上界為：

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

對(duì)4500個(gè)記錄排序的例子,各種操作的計(jì)算時(shí)間如下：讀18個(gè)輸入塊,內(nèi)部排序6段,寫18個(gè)輸出塊 ＝6tIS＋36tIO

成對(duì)歸并初始?xì)w并段R1～R6

＝36

tIO＋4500

tmg

歸并兩個(gè)具有1500個(gè)記錄的歸并段R12和R34

＝24

tIO＋3000

tmg

最后將

R1234和R56歸并成一個(gè)歸并段

＝36

tIO＋4500

tmg合計(jì)tES＝6

tIS＋132

tIO＋12000tmg57

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

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

歸并趟數(shù)S2 132 3

3 108 2

6 72 158

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

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

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

在初始?xì)w并段個(gè)數(shù)m與記錄個(gè)數(shù)n一定時(shí),log2m*(n-1)=const,而(k-1)/log2k

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

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

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

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

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

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

int*loser=newint[k]; //存放敗者樹for(i=0;i<k;i++)//葉結(jié)點(diǎn)的值{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]調(diào)整形成敗者樹 while(key[loser[0]]!=MaxValue){//選冠軍

q=loser[0]; //取當(dāng)前最小記錄

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

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

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

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

Outputendofrunmarker; //輸出段結(jié)束標(biāo)志 delete[]r;delete[]key;delete[]loser;};69自某葉結(jié)點(diǎn)key[q]到敗者樹根結(jié)點(diǎn)

的調(diào)整算法

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

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

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

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

C0T1R20R25R30R40R45R48R55C0T2R64R69R74R78R83R91R100C0T3R110R125C0T4

溢出區(qū)……55C0T1100C0T2125C0T3C1T0

C1T1R146R151R159R164R168R172R181C1T2R189R190R193R198R203R210R222C1T3R234R246R255R269R270

C1T4

溢出區(qū)……181C1T1222C1T2270C1T3125C0T0270C1T0

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

………5540C79T1C7T0

C7T1R720R724R727R736R743R759R758C7T2R765R769R777R781R785R790R793C7T3R799R801R825R833

C7T4

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

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

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

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

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

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

Pi

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

中所有的關(guān)鍵碼都大于Kn；在子樹P0

中的所有關(guān)鍵碼都小于K1。子樹

Pi

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

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

constintMaxValue=……;//關(guān)鍵碼集合中不可能有的最大值template<classT>structMtreeNode{ //樹結(jié)點(diǎn)定義intn; //索引項(xiàng)個(gè)數(shù)

MtreeNode<T>*parent; //父結(jié)點(diǎn)指針

Tkey[m+1]; //索引項(xiàng)關(guān)鍵碼域 int*recptr[m+1]; //索引項(xiàng)記錄地址指針MtreeNode<T>*ptr[m+1]; //子樹結(jié)點(diǎn)指針};86template<classT> //搜索結(jié)果三元組structTriple{MtreeNode<T>*r; //結(jié)點(diǎn)地址指針inti; //結(jié)點(diǎn)中關(guān)鍵碼序號(hào)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,則樹中的最大結(jié)點(diǎn)個(gè)數(shù)為：每個(gè)結(jié)點(diǎn)中最多有m-1個(gè)關(guān)鍵碼，在一棵高度為h的m路搜索樹中關(guān)鍵碼最大個(gè)數(shù)為mh-1。高度h=3的二叉搜索樹,關(guān)鍵碼最大數(shù)為7；高度h=4的3路搜索樹,關(guān)鍵碼最大數(shù)為34-1=80。88在m路搜索樹上的 搜索過程是一個(gè)在 結(jié)點(diǎn)內(nèi)搜索和自根 結(jié)點(diǎn)向下逐個(gè)結(jié)點(diǎn) 搜索的交替的過程。m路搜索樹的搜索算法352040abcde253010154550root搜索3589template<classT>Triple<T>Mtree<T>::Search(constT&x){//用關(guān)鍵碼x搜索駐留在磁盤上的m路搜索樹//各結(jié)點(diǎn)格式為n,p[0],(k[1],p[1]),…,(k[n],p[n]),n<m//函數(shù)返回一個(gè)類型為Triple(r,i,tag)的記錄。//tag=0,表示x在結(jié)點(diǎn)r中找到,該結(jié)點(diǎn)的k[i]等于x;//tag=1,表示沒有找到x,可插入結(jié)點(diǎn)為r,插入到該//結(jié)點(diǎn)的k[i]與k[i+1]之間。

Tripleresult; //記錄搜索結(jié)果三元組

GetNode(root); //從盤上讀取結(jié)點(diǎn)root

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

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

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

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

//本結(jié)點(diǎn)無x,q記下當(dāng)前結(jié)點(diǎn),p下降到子樹

GetNode(p); //從磁盤上讀取結(jié)點(diǎn)p }

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

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

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

非B樹 B樹30352040253010154550root4550354020root10152595B樹類和B樹結(jié)點(diǎn)類的定義

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

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

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

h-2個(gè)結(jié)點(diǎn)。所有這些結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。失敗結(jié)點(diǎn)在第h+1層，失敗結(jié)點(diǎn)個(gè)數(shù)為N+1。99這是因?yàn)闃渲嘘P(guān)鍵碼有N個(gè)，而失敗數(shù)據(jù)一般與已有關(guān)鍵碼交錯(cuò)排列。因此，有N+1=失敗結(jié)點(diǎn)數(shù)=位于第h+1層的結(jié)點(diǎn)數(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,關(guān)鍵碼總數(shù)N=1999999，則B樹的高度h不超過

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

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

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

[m/2

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

p中已經(jīng)有m-1個(gè)關(guān)鍵碼，當(dāng)再插入一個(gè)關(guān)鍵碼后結(jié)點(diǎn)中的狀態(tài)為103

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

其中

Ki<Ki+1,1

i<m這時(shí)必須把結(jié)點(diǎn)

p分裂成兩個(gè)結(jié)點(diǎn)p和q，它們包含的信息分別為：

結(jié)點(diǎn)p：

(m/2

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

-1,Pm/2

-1)

結(jié)點(diǎn)q：(m-m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中間的關(guān)鍵碼Km/2

與指向新結(jié)點(diǎn)

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

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

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

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

MtreeNode<T>*p=loc.r,*q; //r是插入結(jié)點(diǎn)

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

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

PutNode(p);returntrue; //輸出結(jié)點(diǎn)p}ints=(m+1)/2; //準(zhǔn)備分裂結(jié)點(diǎn)

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

q=newMtreeNode<T>; //建立新結(jié)點(diǎn)q

move(p,q,s,m); //向新結(jié)點(diǎn)移動(dòng)

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

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

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

t=p->parent;GetNode(t); //讀取父結(jié)點(diǎn)t

j=0;

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

q->parent=p->parent; //新結(jié)點(diǎn)的雙親

PutNode(p);PutNode(q); //輸出結(jié)點(diǎn)

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

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;

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

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

所在的位置;然后在x

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