數(shù)據(jù)結(jié)構(gòu)課件第八章

1、靜態(tài)索引結(jié)構(gòu)示例：有一個(gè)存放職工信息的數(shù)據(jù)表，每一個(gè)職工對(duì)象有近 1k 字節(jié)的信息, 正好占據(jù)一個(gè)頁(yè)塊的存儲(chǔ)空間。當(dāng)數(shù)據(jù)對(duì)象個(gè)數(shù) n 很大時(shí)，如果用無(wú)序表形式的靜態(tài)搜索結(jié)構(gòu)存儲(chǔ)，采用順序搜索，則搜索效率極低。如果采用有序表存儲(chǔ)形式的靜態(tài)搜索結(jié)構(gòu)，則插入新記錄進(jìn)行排序，時(shí)間開(kāi)銷也很可觀。這時(shí)可采用索引方法來(lái)實(shí)現(xiàn)存儲(chǔ)和搜索。線性索引 (Linear Index List)多級(jí)索引結(jié)構(gòu) 假設(shè)內(nèi)存工作區(qū)僅能容納 64k 字節(jié)的數(shù)據(jù)，在某一時(shí)刻內(nèi)存最多可容納 64 個(gè)對(duì)象以供搜索。如果對(duì)象總數(shù)有 14400 個(gè), 不可能把所有對(duì)象的數(shù)據(jù)一次都讀入內(nèi)存。無(wú)論是順序搜索或二分搜索，都需要多次讀取外存記錄。如

2、果在索引表中每一個(gè)索引項(xiàng)占4個(gè)字節(jié), 每個(gè)索引項(xiàng)索引一個(gè)職工對(duì)象，則 14400 個(gè)索引項(xiàng)需要 56.25k 字節(jié), 在內(nèi)存中可以容納所有的索引項(xiàng)。這樣只需從外存中把索引表讀入內(nèi)存，經(jīng)過(guò)搜索索引后確定了職工對(duì)象的存儲(chǔ)地址，再經(jīng)過(guò) 1 次讀取對(duì)象操作就可以完成搜索。稠密索引：一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一個(gè)對(duì)象的索引結(jié)構(gòu)。當(dāng)對(duì)象在外存中按加入順序存放而不是按關(guān)鍵碼有序存放時(shí)必須采用稠密索引結(jié)構(gòu)，這時(shí)的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。稀疏索引：當(dāng)對(duì)象在外存中有序存放時(shí)，可以把所有 n 個(gè)對(duì)象分為 b 個(gè)子表(塊)存放，一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一組對(duì)象(子表)。在子表中, 所有對(duì)象可能按關(guān)鍵碼有序地存放, 也可

3、能無(wú)序地存放。但所有這些子表必須分塊有序，后一個(gè)子表中所有對(duì)象的關(guān)鍵碼均大于前一個(gè)子表中所有對(duì)象的關(guān)鍵碼。它們都存放在數(shù)據(jù)區(qū)中。另外建立一個(gè)索引表。索引表中每一表目叫做索引項(xiàng)，它記錄了子表中最大關(guān)鍵碼max_key以及該子表在數(shù)據(jù)區(qū)中的起始位置obj_addr。各個(gè)索引項(xiàng)在索引表中的序號(hào)與各個(gè)子表的塊號(hào)有一一對(duì)應(yīng)的關(guān)系：第 i 個(gè)索引項(xiàng)是第 i 個(gè)子表的索引項(xiàng), i = 0, 1, , n-1。這樣的索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。對(duì)索引順序結(jié)構(gòu)進(jìn)行搜索時(shí)，一般分為兩級(jí)搜索。 先在索引表 ID 中搜索給定值 K，確定滿足 IDi-1.max_key K IDi.max_key 的 i 值，即待查對(duì)象

4、可能在的子表的序號(hào)。 然后再在第 i 個(gè)子表中按給定值搜索要求的對(duì)象。索引表是按max_key有序的，且長(zhǎng)度也不大，可以二分搜索，也可以順序搜索。各子表內(nèi)各個(gè)對(duì)象如果也按對(duì)象關(guān)鍵碼有序，可以采用二分搜索或順序搜索；如果不是按對(duì)象關(guān)鍵碼有序，只能順序搜索。索引順序搜索的搜索成功時(shí)的平均搜索長(zhǎng)度 ASLIndexSeq = ASLIndex + ASLSubList其中，ASLIndex 是在索引表中搜索子表位置的平均搜索長(zhǎng)度，ASLSubList 是在子表內(nèi)搜索對(duì)象位置的搜索成功的平均搜索長(zhǎng)度。設(shè)把長(zhǎng)度為 n 的表分成均等的 b 個(gè)子表，每個(gè)子表 s 個(gè)對(duì)象，則 b = n/s。又設(shè)表中每個(gè)對(duì)象

5、的搜索概率相等，則索引表的搜索概率為1/b，子表內(nèi)各對(duì)象的搜索概率為 1/s。若對(duì)索引表和子表都用順序搜索，則索引順序搜索的搜索成功時(shí)的平均搜索長(zhǎng)度為 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1索引順序搜索的平均搜索長(zhǎng)度不僅與表中的對(duì)象個(gè)數(shù) n 有關(guān)，而且與每個(gè)子表中的對(duì)象個(gè)數(shù) s 有關(guān)。在給定 n 的情況下，s 應(yīng)選擇多大？利用數(shù)學(xué)方法可以導(dǎo)出，當(dāng) s = 時(shí)，ASLIndexSeq取極小值 +1。 這個(gè)值比順序搜索強(qiáng)，但比二分搜索差。但如果子表存放在外存時(shí)，還要受到頁(yè)塊大小的制約。求導(dǎo)并令其結(jié)果為0：所以：若采用二分搜索確定對(duì)象所在的子表，則搜索成

6、功時(shí)的平均搜索長(zhǎng)度為 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2倒排表(Inverted Index List)對(duì)包含有大量數(shù)據(jù)對(duì)象的數(shù)據(jù)表或文件進(jìn)行搜索時(shí)，最常用的是針對(duì)對(duì)象的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標(biāo)識(shí)該對(duì)象。用主關(guān)鍵碼建立的索引叫做主索引。主索引的每個(gè)索引項(xiàng)給出對(duì)象的關(guān)鍵碼和對(duì)象在表或文件中的存放地址。但在實(shí)際應(yīng)用中有時(shí)需要針對(duì)其它屬性進(jìn)行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?(1) 列出所有教師的名單； (2) 已婚的女性職工有哪些人？對(duì)象關(guān)鍵碼 key 對(duì)象存放

7、地址 addr這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問(wèn)題，只能到表或文件中去順序搜索，搜索效率極低。因此，除主關(guān)鍵碼外，可以把一些經(jīng)常搜索的屬性設(shè)定為次關(guān)鍵碼，并針對(duì)每一個(gè)作為次關(guān)鍵碼的屬性，建立次索引。在次索引中，列出該屬性的所有取值，并對(duì)每一個(gè)取值建立有序鏈表，把所有具有相同屬性值的對(duì)象按存放地址遞增的順序或按主關(guān)鍵碼遞增的順序鏈接在一起。次索引的索引項(xiàng)由次關(guān)鍵碼、鏈表長(zhǎng)度和鏈表本身等三部分組成。為了回答上述的查詢，我們可以分別建立“性別”、“婚否”和“職務(wù)”次索引。 (1) 列出所有教師的名單； (2) 已婚的女性職工有哪些人？通過(guò)順序訪問(wèn)“職務(wù)”次索引中的“教師”鏈

8、，可以回答上面的查詢(1)。通過(guò)對(duì)“性別”和“婚否”次索引中的“女性”鏈和“已婚”鏈進(jìn)行求“交”運(yùn)算，就能夠找到所有既是女性又已婚的職工對(duì)象，從而回答上面的查詢(2)。倒排表或倒排文件是一種次索引的實(shí)現(xiàn)。在倒排表中所有次關(guān)鍵碼的鏈都保存在次索引中，僅通過(guò)搜索次索引就能找到所有具有相同屬性值的對(duì)象。在次索引中記錄對(duì)象存放位置的指針可以用主關(guān)鍵碼表示，可以通過(guò)搜索次索引確定該對(duì)象的主關(guān)鍵碼，再通過(guò)搜索主索引確定對(duì)象的存放地址。在倒排表中各個(gè)屬性鏈表的長(zhǎng)度大小不一，管理起來(lái)比較困難。為此引入單元式倒排表。在單元式倒排表中，索引項(xiàng)中不存放對(duì)象的存儲(chǔ)地址，存放該對(duì)象所在硬件區(qū)域的標(biāo)識(shí)。硬件區(qū)域可以是磁盤(pán)

9、柱面、磁道或一個(gè)頁(yè)塊，以一次I/O 操作能存取的存儲(chǔ)空間作為硬件區(qū)域?yàn)樽詈?。為使索引空間最小，在索引中標(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)鍵碼的對(duì)象。單元式倒排表結(jié)構(gòu)如果在硬件區(qū)域1，中有要求的對(duì)象。然后將硬件區(qū)域1，等讀入內(nèi)存，在其中進(jìn)行檢索，確定就可取出所需對(duì)象。倒排表的應(yīng)用文獻(xiàn)檢索以檢索項(xiàng)作為次索引。以文獻(xiàn)號(hào)來(lái)標(biāo)示文獻(xiàn)。對(duì)所有包含檢索項(xiàng)的文獻(xiàn)，以單鏈表的形式將其文獻(xiàn)號(hào)鏈接 起來(lái)，且按文獻(xiàn)號(hào)有序鏈接。對(duì)多個(gè)檢索項(xiàng)，采取相應(yīng)檢索項(xiàng)鏈表的“交

10、”運(yùn)算。若兩個(gè)單鏈表的長(zhǎng)度分別為m和n，則兩個(gè)鏈表“交”運(yùn)算時(shí)間復(fù)雜度為O(m+n)。重復(fù)執(zhí)行“交”運(yùn)算的時(shí)間復(fù)雜度接近O(n) 。關(guān)鍵詞名稱編號(hào)#關(guān)鍵詞1001，003，007，010關(guān)鍵詞2002，004，007關(guān)鍵詞3001，010關(guān)鍵詞4002，005, 008關(guān)鍵詞5001，004，006關(guān)鍵詞6003倒排表的應(yīng)用全文檢索對(duì)多個(gè)正文文本建立索引的基本思想就是，把正文看成一個(gè)一個(gè)的關(guān)鍵詞的集合，然后用這些詞組成一些適合快速檢索的數(shù)據(jù)結(jié)構(gòu)。一個(gè)倒排文件就是一個(gè)已經(jīng)排好序的關(guān)鍵詞的列表，其中每個(gè)關(guān)鍵詞指向一個(gè)倒排表，該表中記錄了該關(guān)鍵詞出現(xiàn)的文檔集合以及在該文檔中的出現(xiàn)位置。 關(guān)鍵詞倒排表

11、（所在文檔編號(hào)，出現(xiàn)次數(shù)， 出現(xiàn)位置）KMP(#3307, 2, 5, 43) (#4615, 5, 0, 19, 34, 70, 143)最小生成樹(shù)(#2519, 1, 267) (#6742, 3, 19, 322, 526)最短路徑(#2948, 3, 45, 267, 587) (#3693, 4, 39, 423, 765, 809, )倒排表的應(yīng)用全文檢索詞條化：將給定的字符序列拆分成一系列子序列的過(guò)程，詞條化處理往往與語(yǔ)言本身有關(guān)。如對(duì)于漢語(yǔ)，需要進(jìn)行文本切詞，即以人工或者機(jī)器自動(dòng)的方式把一篇文檔里的可能成為關(guān)鍵詞的詞組劃分出來(lái)。在漢語(yǔ)等東方語(yǔ)言中，因?yàn)樵~與詞之間沒(méi)有空格，所以怎

12、樣把詞組從句子中完整的切分出來(lái)，需要專門(mén)的研究。這需要自然語(yǔ)言理解技術(shù)(natural language processing)的支持。 去除停用詞：某些情況下一些常見(jiàn)詞在文檔與用戶需求進(jìn)行匹配時(shí)價(jià)值并不大，需要從詞匯表中去除，這些詞被稱為停用詞。詞項(xiàng)歸一化：將看起來(lái)不完全一致的多個(gè)詞條歸納成一個(gè)等價(jià)類（或維護(hù)一個(gè)關(guān)聯(lián)關(guān)系），如car和automobile。 詞干還原和詞形歸并：目的是為了減少變化的形式，并且有時(shí)會(huì)將派生詞轉(zhuǎn)化為基本形式倒排表的應(yīng)用全文檢索索引的構(gòu)建方法索引的壓縮文檔評(píng)分、詞項(xiàng)權(quán)重計(jì)算相關(guān)反饋及查詢擴(kuò)展文檔分類方法文檔機(jī)器學(xué)習(xí)方法可以進(jìn)一步研究的問(wèn)題由于倒排索引支持高效檢索，所

13、以應(yīng)用相當(dāng)廣泛。當(dāng)然，對(duì)倒排表進(jìn)行集合運(yùn)算也需要一些運(yùn)算空間，更大的缺點(diǎn)在于，當(dāng)文件發(fā)生變化時(shí)，要同時(shí)維護(hù)更新這些索引，而這種更新的工作量會(huì)很大。所以它比較適合于當(dāng)大文件里面內(nèi)容比較穩(wěn)定的情況下。尤其像光盤(pán)上的數(shù)據(jù)檢索等就會(huì)是它最理想的應(yīng)用場(chǎng)所之一。 m路靜態(tài)搜索樹(shù)當(dāng)數(shù)據(jù)對(duì)象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。在此情況下，可以建立索引的索引，稱為二級(jí)索引。二級(jí)索引可以常駐內(nèi)存，二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址。多級(jí)索引結(jié)構(gòu)如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍?jí)索

14、引的索引，叫做三級(jí)索引。這時(shí)，訪問(wèn)外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對(duì)象。必要的話，還可以有4級(jí)索引，5極索引，。這種多級(jí)索引結(jié)構(gòu)形成一種 m 叉樹(shù)。樹(shù)中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊，它最多存放 m 個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)分別給出各子樹(shù)結(jié)點(diǎn) (低一級(jí)索引塊) 的最大關(guān)鍵碼和結(jié)點(diǎn)地址。樹(shù)的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對(duì)象的關(guān)鍵碼和存放地址。這種m叉樹(shù)用來(lái)作為多級(jí)索引，就是m路搜索樹(shù)。m路搜索樹(shù)可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，在整個(gè)運(yùn)行期間，樹(shù)的結(jié)構(gòu)不發(fā)生變化。m路搜索樹(shù)還可能是動(dòng)態(tài)索引結(jié)構(gòu)，即在整個(gè)系統(tǒng)運(yùn)行期間，樹(shù)的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整，以保持最佳的搜索

15、效率。多級(jí)索引結(jié)構(gòu)形成m路搜索樹(shù)動(dòng)態(tài)搜索結(jié)構(gòu)現(xiàn)在我們所討論的m路搜索樹(shù)多為可以動(dòng)態(tài)調(diào)整的多路搜索樹(shù)，它的一般定義為：動(dòng)態(tài)的m路搜索樹(shù)一棵m路搜索樹(shù), 它或者是一棵空樹(shù), 或者是滿足如下性質(zhì)的樹(shù)： 根最多有 m 棵子樹(shù), 并具有如下的結(jié)構(gòu)： n, P0, ( K1, P1 ), ( K2, P2 ), , ( Kn, Pn )其中，Pi 是指向子樹(shù)的指針，0 i n m；Ki 是關(guān)鍵碼，1 i n m。 Ki Ki+1, 1 i n。在子樹(shù) Pi 中所有的關(guān)鍵碼都小于 Ki+1，且大于 Ki，0 i n。在子樹(shù) Pn 中所有的關(guān)鍵碼都大于Kn；在子樹(shù) P0 中的所有關(guān)鍵碼都小于 K1。子樹(shù) Pi

16、 也是m路搜索樹(shù)，0 i n。一棵3路搜索樹(shù)的示例結(jié)點(diǎn)a的內(nèi)容為：2, b, (20, c), (40, d)結(jié)點(diǎn)c的內(nèi)容為：2, 0, (25, 0), (30, e)template class Mtree /基類 public: Triple Search ( const T & x);protected: Mtreenode *root; /根指針 int m; /路數(shù)，即樹(shù)的度m路搜索樹(shù)的類定義template struct MtreeNode /樹(shù)結(jié)點(diǎn)定義 int n; /關(guān)鍵碼個(gè)數(shù) MtreeNode *parent; /父結(jié)點(diǎn)指針 T keym+1； /keym為監(jiān)視哨兼工作單

17、元，key0未用 MtreeNode *ptrm+1; /子樹(shù)結(jié)點(diǎn)指針數(shù)組，ptrm在插入溢出時(shí)用 int *recptrm+1； /每個(gè)索引項(xiàng)中指向數(shù)據(jù)區(qū)相應(yīng)記錄起始地址 的指針m路搜索樹(shù)的結(jié)點(diǎn)定義template Struct Triple MtreeNode *r; /結(jié)點(diǎn)地址指針 int i; int tag; /結(jié)點(diǎn)中關(guān)鍵碼序號(hào) /tag=0，搜索成功；tag=1，搜索失敗搜索結(jié)果的三元組表示AVL樹(shù)是2路搜索樹(shù)。如果已知m路搜索樹(shù)的度m和它的高度 h, 則樹(shù)中的最大結(jié)點(diǎn)數(shù)為:(等比級(jí)數(shù)前 h 項(xiàng)求和)每個(gè)結(jié)點(diǎn)中最多有m-1個(gè)關(guān)鍵碼，在一棵高度為h的m路搜索樹(shù)中關(guān)鍵碼的最大個(gè)數(shù)為 m

18、h-1。對(duì)于高度h=3的二叉樹(shù)，關(guān)鍵碼最大個(gè)數(shù)為7；對(duì)于高度h=4的3路搜索樹(shù)，關(guān)鍵碼最大個(gè)數(shù)為 34-1 = 80。template Triple Mtree:Search ( const T & x ) Triple result; /記錄搜索結(jié)果三元組 GetNode ( root ); /讀入根結(jié)點(diǎn) Mtreenode *p = root, *q = NULL; while ( p != NULL ) /從根開(kāi)始檢測(cè) int i = 0; p-key(pn)+1 = Maxvalue; /監(jiān)視哨 while ( pkeyi+1 x ) i+; /在結(jié)點(diǎn)中搜索 if ( pkeyi+1

19、= x ) /搜索成功 result.r = p; result.i = i+1; result.tag = 0; return result; m路搜索樹(shù)上的搜索算法 q = p; p = pptri; /向下一層結(jié)點(diǎn)搜索 GetNode (p); /讀入該結(jié)點(diǎn) result.r = q; result.i = i; result.tag = 1; return result; /搜索失敗,返回插入位置提高搜索樹(shù)的路數(shù)m，可以改善樹(shù)的搜索性能。對(duì)于給定的關(guān)鍵碼數(shù)n，如果搜索樹(shù)是平衡的，可以使 m 路搜索樹(shù)的性能接近最佳。下面我們將討論一種稱之為B_樹(shù)的平衡的m路搜索樹(shù)。在B_樹(shù)中我們引入“失

20、敗”結(jié)點(diǎn)。一個(gè)失敗結(jié)點(diǎn)是當(dāng)搜索值x不在樹(shù)中時(shí)才能到達(dá)的結(jié)點(diǎn)。B_樹(shù)一棵 m 階B_樹(shù)是一棵 m 路搜索樹(shù)，它或者是空樹(shù)，或者是滿足下列性質(zhì)的樹(shù)：根結(jié)點(diǎn)至少有 2 個(gè)子女。除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括失敗結(jié)點(diǎn)）至少有 m/2 個(gè)子女。所有的失敗結(jié)點(diǎn)都位于同一層。事實(shí)上，在B_樹(shù)的每個(gè)結(jié)點(diǎn)中還包含有一組指針Dm，指向?qū)嶋H對(duì)象的存放地址。Ki與Di (1 i n m)形成一個(gè)索引項(xiàng)(Ki, Di)，通過(guò)Ki可找到某個(gè)對(duì)象的存儲(chǔ)地址Di。非B_樹(shù) B_樹(shù)B_樹(shù)的結(jié)點(diǎn)具有如下的結(jié)構(gòu)： n, P0, ( K1, P1 ), ( K2, P2 ), , ( Kn, Pn )其中，Pi 是指向子樹(shù)的指針，0

21、 i n m；Ki 是關(guān)鍵碼，1 i n m。 Ki Ki+1, 1 i n。public: Btree( ); bool Insert ( const T & x ); bool Remove ( T & x );template class Mtreenode /結(jié)點(diǎn)定義private: int n; /結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) Mnode *parent; /雙親指針 T keym+1; /關(guān)鍵碼數(shù)組 1m-1 Mtreenode *recptrm+1; /子樹(shù)指針數(shù)組 0m;template class Btree : public Mtree /繼承 m 路搜索樹(shù)的所有屬性和操作B_樹(shù)的類定

22、義和B_樹(shù)結(jié)點(diǎn)類定義 B_樹(shù)的搜索算法B_樹(shù)的搜索算法繼承了在m路搜索樹(shù)Mtree上的搜索算法。B_樹(shù)的搜索過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過(guò)程。因此，B_樹(shù)的搜索時(shí)間與B_樹(shù)的階數(shù)m和B_樹(shù)的高度h直接有關(guān)，必須加以權(quán)衡。在B_樹(shù)上進(jìn)行搜索，搜索成功所需的時(shí)間取決于關(guān)鍵碼所在的層次，搜索不成功所需的時(shí)間取決于樹(shù)的高度。如果我們定義B_樹(shù)的高度h為失敗結(jié)點(diǎn)所在的層次，需要了解樹(shù)的高度h與樹(shù)中的關(guān)鍵碼個(gè)數(shù)N之間的關(guān)系。 設(shè)在 m 階B_樹(shù)中，失敗結(jié)點(diǎn)位于第 h +1層。在這棵B_樹(shù)中關(guān)鍵碼個(gè)數(shù) N 最小能達(dá)到多少？ 從B_樹(shù)的定義知, 1層 1 個(gè)結(jié)點(diǎn)2層 至少 2 個(gè)

23、結(jié)點(diǎn)3層 至少 2 m / 2 個(gè)結(jié)點(diǎn)4層 至少 2 m / 2 2 個(gè)結(jié)點(diǎn)如此類推，h層至少有2 m / 2 h-2個(gè)結(jié)點(diǎn)。所有這些結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。高度h與關(guān)鍵碼個(gè)數(shù) N 之間的關(guān)系若樹(shù)中關(guān)鍵碼有 N 個(gè), 則失敗結(jié)點(diǎn)數(shù)為 N +1。這是因?yàn)槭∫话惆l(fā)生在 Ki x Ki+1, 0 i N，設(shè)K0 = -，KN+1 = +。因此，有 N +1 = 失敗結(jié)點(diǎn)數(shù) = = 位于第 h +1層的結(jié)點(diǎn)數(shù) 2 m / 2 h-1 N 2 m / 2 h-1-1反之，如果在一棵 m 階B_樹(shù)中有 N 個(gè)關(guān)鍵碼，則所有的非失敗結(jié)點(diǎn)所在層次都小于 h，則 h-1 log m / 2 ( (N +1) /

24、2 ) h log m / 2 ( (N +1) / 2 )+1示例：若B_樹(shù)的階數(shù) m = 199，關(guān)鍵碼總數(shù) N = 1999999，則B_樹(shù)的高度 h 不超過(guò) log100 1000000 +1= 4若B_樹(shù)的階數(shù) m = 4，高度 h = 3，則關(guān)鍵碼總數(shù)至少為 N = 2 4 / 2 3-1-1 = 7。如果提高B_樹(shù)的階數(shù) m，可以減少樹(shù)的高度，從而減少讀入結(jié)點(diǎn)的次數(shù)，因而可減少讀磁盤(pán)的次數(shù)。事實(shí)上，m 受到內(nèi)存可使用空間的限制。當(dāng)m很大超出內(nèi)存工作區(qū)容量時(shí)，結(jié)點(diǎn)不能一次讀入到內(nèi)存，增加了讀盤(pán)次數(shù)，也增加了結(jié)點(diǎn)內(nèi)搜索的難度。m值的選擇m值的選擇：應(yīng)使得在B_樹(shù)中找到關(guān)鍵碼 x 的時(shí)

25、間總量達(dá)到最小。 這個(gè)時(shí)間由兩部分組成： 從磁盤(pán)中讀入結(jié)點(diǎn)所用時(shí)間 在結(jié)點(diǎn)中搜索 x 所用時(shí)間根據(jù)定義，B_樹(shù)的每個(gè)結(jié)點(diǎn)的大小都是固定的，結(jié)點(diǎn)內(nèi)有 m-1 個(gè)索引項(xiàng) (Ki, Di, Pi), 1 i m。其中，Ki 所占字節(jié)數(shù)為，Di 和 Pi 所占字節(jié)數(shù)為，則結(jié)點(diǎn)大小近似為 m(+2) 個(gè)字節(jié)。讀入一個(gè)結(jié)點(diǎn)所用時(shí)間為： tseek + tlatency + m( + 2) ttran = a + bmB_樹(shù)的插入B_樹(shù)是從空樹(shù)起，逐個(gè)插入關(guān)鍵碼而生成的。在B_樹(shù)中，每個(gè)非失敗的非根結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)都在 m/2 -1, m-1 之間。插入在某個(gè)葉結(jié)點(diǎn)開(kāi)始。如果在關(guān)鍵碼插入后結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)

26、超出了上界 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)為： ( 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

27、/2, q )，插入到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)中去。三階B_樹(shù)結(jié)點(diǎn)“分裂”的示例示例：從空樹(shù)開(kāi)始逐個(gè)加入關(guān)鍵碼建立3階B_樹(shù)在插入新關(guān)鍵碼時(shí)，需要自底向上分裂結(jié)點(diǎn)，最壞情況下從被插關(guān)鍵碼所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。template bool Btree:Insert ( const T & x ) Triple loc = Search (x); /找x的位置 if ( !loc.tag ) return 0; /找到,不再插入 Mtreenode *p = loc.r, *q; /未找到,插入 Mtree *ap = NULL, *t; T K = x; int j = loc.i

28、; while (1) if ( pn m-1) /當(dāng)前結(jié)點(diǎn)未滿 insertkey ( p, j, K, ap ); /(K,ap)插入 j后 PutNode (p); return 1; /寫(xiě)出 B_樹(shù)的插入算法 /結(jié)點(diǎn)已滿,分裂 int s = (m+1)/2; /求 m/2 insertkey ( p, j, K, ap ); /(K,ap)插入 j后 q = new Mtreenode; /建立新結(jié)點(diǎn) move ( p, q, s, m ); /從 p向q 搬送 K = pkeys; ap = q; /分界關(guān)鍵碼上移 if ( pparent != NULL ) /雙親結(jié)點(diǎn)不是根 t

29、 = pparent; GetNode (t); /讀入雙親 j = 0; t-key(tn)+1 = MAXKEY; while ( tkeyj+1 K ) j+; /找插入點(diǎn) qparent = pparent; PutNode (p); PutNode (q); p = t; else /雙親是根 root = new Mtreenode; /創(chuàng)建新根 rootn = 1; rootparent = NULL; rootkey1 = K; rootptr0 = p; rootptr1 = ap; qparent = pparent = root; PutNode (p); PutNode

30、 (q); PutNode (root); return 1; 當(dāng)分裂一個(gè)非根的結(jié)點(diǎn)時(shí)需要向磁盤(pán)寫(xiě)出 2 個(gè)結(jié)點(diǎn)（原結(jié)點(diǎn)和新生的兄弟結(jié)點(diǎn)）, 當(dāng)分裂根結(jié)點(diǎn)時(shí)需要寫(xiě)出 3 個(gè)結(jié)點(diǎn)（再加上一個(gè)父結(jié)點(diǎn)）。如果我們所用的內(nèi)存工作區(qū)足夠大，使得在向下搜索時(shí)讀入的結(jié)點(diǎn)在插入后向上分裂時(shí)不必再?gòu)拇疟P(pán)讀入，那么，在完成一次插入操作時(shí) 最多需要讀寫(xiě)磁盤(pán)的次數(shù) = 找插入結(jié)點(diǎn)向下讀盤(pán)次數(shù) + 分裂非根結(jié)點(diǎn)時(shí)寫(xiě)盤(pán)次數(shù) + 分裂根結(jié)點(diǎn)時(shí)寫(xiě)盤(pán)次數(shù) = h+2(h-1)+3 = = 3h+1。可以證明，在向一棵初始為空的B_樹(shù)中插入 N 個(gè)關(guān)鍵碼, 并且非失敗結(jié)點(diǎn)個(gè)數(shù)為 p 時(shí), 分裂的結(jié)點(diǎn)總數(shù)最多為 p-2。由于根結(jié)點(diǎn)

31、至少有一個(gè)關(guān)鍵碼，其它各非失敗結(jié)點(diǎn)至少有 m/2 -1 個(gè)關(guān)鍵碼，則一棵擁有 p 個(gè)結(jié)點(diǎn)的 m 階B_樹(shù)至少有 1+(m/2 -1)(p-1) 個(gè)關(guān)鍵碼。插入 N 個(gè)關(guān)鍵碼平均分裂結(jié)點(diǎn)數(shù)Savg 為： Savg = 分裂結(jié)點(diǎn)總次數(shù)/N (p-2)/(1+(m/2 -1)(p-1) ) 1/(m/2 -1)B_樹(shù)的刪除在B_樹(shù)上刪除一個(gè)關(guān)鍵碼時(shí)，首先需要找到這個(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 所指示子樹(shù)中的最小關(guān)鍵碼 x 來(lái)代替被刪關(guān)鍵碼 Ki 所在的位置，然后在 x 所在的葉結(jié)點(diǎn)中刪除 x。在葉

32、結(jié)點(diǎn)上的刪除有 4 種情況。 （1）被刪關(guān)鍵碼所在葉結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) n 2，則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤(pán)。36 49M=3刪除3649（2）被刪關(guān)鍵碼所在葉結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) n m/2，則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤(pán)，刪除結(jié)束。刪除55簡(jiǎn)單刪除（3）被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù) n = m/2 -1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟 (或左兄弟) 結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù) n m/2，則可按以下步驟調(diào)整該結(jié)點(diǎn)、右兄弟 (或左兄弟) 結(jié)點(diǎn)以及其雙親結(jié)點(diǎn)，以達(dá)到新的平衡。將雙親結(jié)點(diǎn)中剛剛大于 (或小于) 該被刪關(guān)鍵碼的關(guān)鍵碼

33、 Ki (1 i n) 下移到被刪關(guān)鍵碼所在結(jié)點(diǎn)中；將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最小 (或最大)關(guān)鍵碼上移到雙親結(jié)點(diǎn)的 Ki 位置；將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最左 (或最右) 子樹(shù)指針平移到被刪關(guān)鍵碼所在結(jié)點(diǎn)中最后 (或最前) 子樹(shù)指針位置；在右兄弟 (或左兄弟) 結(jié)點(diǎn)中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補(bǔ)、調(diào)整。再將結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減1。刪除65結(jié)點(diǎn)聯(lián)合調(diào)整（4）被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù) n = m/2 -1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟 (或左兄弟) 結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù) n = m/2 -1，則必須按以下步驟合并這兩個(gè)結(jié)點(diǎn)。將雙親結(jié)點(diǎn) p 中相應(yīng)關(guān)鍵碼下

34、移到選定保留的結(jié)點(diǎn)中。若要合并 p 中的子樹(shù)指針 Pi 與 Pi+1 所指的結(jié)點(diǎn)，且保留 Pi 所指結(jié)點(diǎn)，則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點(diǎn)中。把 p 中子樹(shù)指針 Pi+1 所指結(jié)點(diǎn)中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點(diǎn)的后面。刪去 Pi+1 所指的結(jié)點(diǎn)。在結(jié)點(diǎn) p 中用后面剩余的關(guān)鍵碼和指針填補(bǔ)關(guān)鍵碼 Ki+1 和指針 Pi+1。修改結(jié)點(diǎn) p 和選定保留結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)。在合并結(jié)點(diǎn)的過(guò)程中，雙親結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減少了。若雙親結(jié)點(diǎn)是根結(jié)點(diǎn)且結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)減到 0，則該雙親結(jié)點(diǎn)應(yīng)從樹(shù)上刪去，合并后保留的結(jié)點(diǎn)成為新的根結(jié)點(diǎn)；否則將雙親結(jié)點(diǎn)與合并后保留的結(jié)點(diǎn)都寫(xiě)回磁盤(pán)，刪

35、除處理結(jié)束。若雙親結(jié)點(diǎn)不是根結(jié)點(diǎn)，且關(guān)鍵碼個(gè)數(shù)減到m/2 -2，又要與它自己的兄弟結(jié)點(diǎn)合并，重復(fù)上面的合并步驟。最壞情況下這種結(jié)點(diǎn)合并處理要自下向上直到根結(jié)點(diǎn)。刪除55結(jié)點(diǎn)合并刪除80結(jié)點(diǎn)合并非葉結(jié)點(diǎn)刪除刪除50刪除55結(jié)點(diǎn)合并與調(diào)整刪除70刪除75template int Btree:Remove ( const T & x ) Triple loc = Search (x); /搜索x if ( loc.tag ) return 0; /未找到,不刪除B_樹(shù)的關(guān)鍵碼刪除算法 Mtreenode *p = loc.r, *q, *s; /找到,刪除 int j = loc.i; if ( p

36、ptrj != NULL ) /非葉結(jié)點(diǎn) s = pptrj; GetNode (s); q = p; while ( s != NULL ) q = s; s = sptr0; pkeyj = qkey1; /從葉結(jié)點(diǎn)替補(bǔ) compress ( q, 1 ); /在葉結(jié)點(diǎn)刪除 p = q; /轉(zhuǎn)化為葉結(jié)點(diǎn)的刪除 else compress ( p, j ); /葉結(jié)點(diǎn),直接刪除 int d = (m+1)/2; /求 m/2 while (1) /調(diào)整或合并 if ( pn d-1 ) /小于最小限制 j = 0; q = pparent; /找到雙親 GetNode (q); while

37、( j = qn & qptrj != p ) j+; if ( !j ) LeftAdjust ( p, q, d, j ); /調(diào)整 else RightAdjust ( p, q, d, j ); p = q; /向上調(diào)整 if ( p = root ) break; else break; if ( !rootn ) /調(diào)整后根的n減到0 p = rootptr0; delete root; root = p; /刪根 rootparent = NULL; /新根 template void Btree:LeftAdjust(MtreeNode *p, MtreeNode *q, in

38、t d, int j)/結(jié)點(diǎn)p與其父結(jié)點(diǎn)q一起進(jìn)行調(diào)整。d是結(jié)點(diǎn)應(yīng)保持的最少階數(shù)，j是父結(jié)點(diǎn)調(diào)整位置 MtreeNode *p1=q-ptrj+1; /p的右兄弟 if (p1-n d-1) /右兄弟空間還夠，僅做調(diào)整 p-n+; p-keyp-n=q-keyj; /父結(jié)點(diǎn)相應(yīng)關(guān)鍵碼下移 q-keyj=p1-key1; /右兄弟最小關(guān)鍵碼上移父結(jié)點(diǎn) p-ptrp-n=p1-ptr0; /右兄弟最左指針左移 p1-ptr0=p1-ptr1; /右兄弟中剩余關(guān)鍵碼與指針前移 compress(p1,1); else merge(p,q,p1,1); /p與p1合并，保留p結(jié)點(diǎn);template v

39、oid Btree:RightAdjust(MtreeNode *p,MtreeNode *q, int d, int j);/此程序與LeftAdjust功能基本相同，但與LeftAdjust是對(duì)稱的：左右指針互換，前端與后端互換template void Btree:compress(MtreeNode *p, int j) for (int i=j; in; i+) /左移 p-keyi=p-keyi+1; p-ptri=p-ptri+1; p-n-; /結(jié)點(diǎn)中元素個(gè)數(shù)減1;template void Btree:merge(MtreeNode *p, MtreeNode *q, Mtr

40、eeNode *p1, int j)/結(jié)點(diǎn)p與其父結(jié)點(diǎn)q、右兄弟結(jié)點(diǎn)做合并，j是父結(jié)點(diǎn)中合并位置 p-key(p-n)+1 = q-keyj; /從父結(jié)點(diǎn)下降一個(gè)關(guān)鍵碼 p-ptr(p-n)+1 = p1-ptr0; /從右兄弟結(jié)點(diǎn)左移一個(gè)指針 for (int i=1; i n; i+) /從右兄弟結(jié)點(diǎn) p-key(p-n)+i+1 = p1-keyi; /關(guān)鍵碼從p1到p左移 p-ptr(p-n)+i+1 = p1-ptri; /指針從p1到p左移 compress(q,j); /父結(jié)點(diǎn)q中值與指針左移 p-n = p-n + p1-n +1 ; delete p1;B+樹(shù)B+樹(shù)可以看作是

41、B_樹(shù)的一種變形，在實(shí)現(xiàn)文件索引結(jié)構(gòu)方面比B_樹(shù)使用得更普遍。一棵m階B+樹(shù)可以定義如下： 樹(shù)中每個(gè)非葉結(jié)點(diǎn)最多有 m 棵子樹(shù)； 根結(jié)點(diǎn) (非葉結(jié)點(diǎn)) 至少有 2 棵子樹(shù)。除根結(jié)點(diǎn)外，其它的非葉結(jié)點(diǎn)至少有 m/2 棵子樹(shù)；有 n 棵子樹(shù)的非葉結(jié)點(diǎn)有 n-1 個(gè)關(guān)鍵碼。 所有的葉結(jié)點(diǎn)都處于同一層次上，包含了全部關(guān)鍵碼及指向相應(yīng)數(shù)據(jù)對(duì)象存放地址的指針，且葉結(jié)點(diǎn)本身按關(guān)鍵碼從小到大順序鏈接；每個(gè)葉結(jié)點(diǎn)中的子樹(shù)棵數(shù) n 可以多于 m，可以少于 m，視關(guān)鍵碼字節(jié)數(shù)及對(duì)象地址指針字節(jié)數(shù)而定。若設(shè)結(jié)點(diǎn)可容納最大關(guān)鍵碼數(shù)為 m1，則指向?qū)ο蟮牡刂分羔樢灿?m1 個(gè)。結(jié)點(diǎn)中的子樹(shù)棵數(shù) n 應(yīng)滿足 n m1/2,

42、 m1。若根結(jié)點(diǎn)同時(shí)又是葉結(jié)點(diǎn)，則結(jié)點(diǎn)格式同葉結(jié)點(diǎn)。所有的非葉結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中關(guān)鍵碼 Ki 與指向子樹(shù)的指針 Pi 構(gòu)成對(duì)子樹(shù) (即下一層索引塊) 的索引項(xiàng) ( Ki, Pi )，Ki 是子樹(shù)中最小的關(guān)鍵碼。特別地，子樹(shù)指針 P0 所指子樹(shù)上所有關(guān)鍵碼均小于 K1。結(jié)點(diǎn)格式同B_樹(shù)。葉結(jié)點(diǎn)中存放的是對(duì)實(shí)際數(shù)據(jù)對(duì)象的索引。在B+樹(shù)中有兩個(gè)頭指針：一個(gè)指向B+樹(shù)的根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵碼最小的葉結(jié)點(diǎn)。可對(duì)B+樹(shù)進(jìn)行兩種搜索運(yùn)算：一種是循葉結(jié)點(diǎn)鏈順序搜索，另一種是從根結(jié)點(diǎn)開(kāi)始，進(jìn)行自頂向下，直至葉結(jié)點(diǎn)的隨機(jī)搜索。在B+樹(shù)上進(jìn)行隨機(jī)搜索、插入和刪除的過(guò)程基本上與B_樹(shù)類似。只是在搜索過(guò)程中

43、，如果非葉結(jié)點(diǎn)上的關(guān)鍵碼等于給定值，搜索并不停止，而是繼續(xù)沿右指針向下，一直查到葉結(jié)點(diǎn)上的這個(gè)關(guān)鍵碼。B+樹(shù)的搜索分析類似于B_樹(shù)。 B+樹(shù)的插入僅在葉結(jié)點(diǎn)上進(jìn)行。每插入一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后都要判斷結(jié)點(diǎn)中的子樹(shù)棵數(shù)是否超出范圍。當(dāng)插入后結(jié)點(diǎn)中的子樹(shù)棵數(shù) n m1 時(shí)，需要將葉結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn)，它們的關(guān)鍵碼分別為 (m1+1)/2 和 (m1+1)/2。并且它們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)的最小關(guān)鍵碼和結(jié)點(diǎn)地址。此后，問(wèn)題歸于在非葉結(jié)點(diǎn)中的插入了。在非葉結(jié)點(diǎn)中關(guān)鍵碼的插入與葉結(jié)點(diǎn)的插入類似，但非葉結(jié)點(diǎn)中的子樹(shù)棵數(shù)的上限為 m，超出這個(gè)范圍就需要進(jìn)行結(jié)點(diǎn)分裂。在做根結(jié)點(diǎn)分裂時(shí)，因?yàn)闆](méi)有雙

44、親結(jié)點(diǎn)，就必須創(chuàng)建新的雙親結(jié)點(diǎn)，作為樹(shù)的新根。這樣樹(shù)的高度就增加一層了。B+樹(shù)的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，結(jié)點(diǎn)中的子樹(shù)棵數(shù)仍然不少于 m1/2，這屬于簡(jiǎn)單刪除，其上層索引可以不改變。如果刪除的關(guān)鍵碼是該結(jié)點(diǎn)的最小關(guān)鍵碼，但因在其上層的副本只是起了一個(gè)引導(dǎo)搜索的“分界關(guān)鍵碼”的作用，所以上層的副本仍然可以保留。如果在葉結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，該結(jié)點(diǎn)中的子樹(shù)棵數(shù) n 小于結(jié)點(diǎn)子樹(shù)棵數(shù)的下限 m1/2，必須做結(jié)點(diǎn)的調(diào)整或合并工作。刪除18刪除12如果右兄弟結(jié)點(diǎn)的子樹(shù)棵數(shù)已達(dá)到下限m1/2，沒(méi)有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點(diǎn)，這時(shí)必須進(jìn)行兩個(gè)

45、結(jié)點(diǎn)的合并。將右兄弟結(jié)點(diǎn)中的所有關(guān)鍵碼-指針?biāo)饕?xiàng)移入被刪關(guān)鍵碼所在結(jié)點(diǎn)，再將右兄弟結(jié)點(diǎn)刪去。刪除33進(jìn)行結(jié)點(diǎn)合并結(jié)點(diǎn)的合并將導(dǎo)致雙親結(jié)點(diǎn)中“分界關(guān)鍵碼”的減少，有可能減到非葉結(jié)點(diǎn)中子樹(shù)棵數(shù)的下限 m/2 以下。這樣將引起非葉結(jié)點(diǎn)的調(diào)整或合并。如果根結(jié)點(diǎn)的最后兩個(gè)子女結(jié)點(diǎn)合并，樹(shù)的層數(shù)就會(huì)減少一層。Trie樹(shù)是一棵度 m 2 的樹(shù)，它的每一層分支不是靠整個(gè)關(guān)鍵碼的值來(lái)確定，而是由關(guān)鍵碼的一個(gè)分量來(lái)確定。如下圖所示Trie樹(shù)，關(guān)鍵碼由英文字母組成。它包括兩類結(jié)點(diǎn)：元素結(jié)點(diǎn)和分支結(jié)點(diǎn)。元素結(jié)點(diǎn)包含整個(gè)key數(shù)據(jù)；分支結(jié)點(diǎn)有27個(gè)指針，其中有一個(gè)空白字符b，用來(lái)終結(jié)關(guān)鍵碼；其它用來(lái)標(biāo)識(shí)a, b,.,

46、 z等26個(gè)英文字母。Trie樹(shù)Trie樹(shù)的定義當(dāng)關(guān)鍵碼是可變長(zhǎng)時(shí)，Trie樹(shù)是一種特別有用的索引結(jié)構(gòu)。 在第0層，所有的關(guān)鍵碼根據(jù)它們第0位字符, 被劃分到互不相交的27個(gè)類中。因此，rootbrch.linki 指向一棵子Trie樹(shù)，該子Trie樹(shù)上所包含的所有關(guān)鍵碼都是以第 i 個(gè)英文字母開(kāi)頭。若某一關(guān)鍵碼第 j 位字母在英文字母表中順序?yàn)?i ( i = 0, 1, , 26 ), 則它在Trie樹(shù)的第 j 層分支結(jié)點(diǎn)中從第 i 個(gè)指針向下找第 j+1 位字母所在結(jié)點(diǎn)。當(dāng)一棵子Trie樹(shù)上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來(lái)代替。在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對(duì)應(yīng)數(shù)據(jù)對(duì)象的存放地址等。const int MaxKeySize = 25; /關(guān)鍵碼最大位數(shù)typedef struct /關(guān)鍵碼類型 char chMaxKeySize; /關(guān)鍵碼存放數(shù)組 int currentSize; /關(guān)鍵碼當(dāng)前位數(shù) KeyType;class TrieNode /Trie樹(shù)結(jié)點(diǎn)類定義 friend class Trie;protected: enum branch, element NodeType; /結(jié)點(diǎn)類型 Trie樹(shù)的類定義 union No