靜態(tài)索引結(jié)構(gòu)動(dòng)態(tài)索引結(jié)構(gòu)散列可擴(kuò)充散列

1、靜態(tài)索引結(jié)構(gòu)動(dòng)態(tài)索引結(jié)構(gòu)散列可擴(kuò)充散列,第十章 索引與散列,靜態(tài)索引結(jié)構(gòu),示例：有一個(gè)存放職工信息的數(shù)據(jù)表, 每一 個(gè)職工對(duì)象有近 1k 字節(jié)的信息, 正好占據(jù)一 個(gè)頁塊的存儲(chǔ)空間。,當(dāng)數(shù)據(jù)對(duì)象個(gè)數(shù) n 很大時(shí), 如果用無序表形式的靜態(tài)搜索結(jié)構(gòu)存儲(chǔ), 采用順序搜索, 則搜索效率極低。如果采用有序表存儲(chǔ)形式的靜態(tài)搜索結(jié)構(gòu), 則插入新記錄進(jìn)行排序, 時(shí)間開銷也很可觀。這時(shí)可采用索引方法來實(shí)現(xiàn)存儲(chǔ)和搜索。,線性索引 (Linear

2、Index List),,,,,,,,,100140180220260300340380,key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220,,,,,,,,,,職工號(hào) 姓名 性別 職務(wù) 婚否 83 張珊 女 教師 已婚 … 08

3、 李斯 男 教師 已婚 ... 03 王魯 男 教務(wù)員 已婚 ... 95 劉琪 女 實(shí)驗(yàn)員 未婚 ... 24 岳跋 男 教師 已婚 ... 47 周斌 男 教師 已婚 ... 17 胡江 男 實(shí)驗(yàn)員 未婚 ... 51

4、 林青 女 教師 未婚 ...,,,,,,,,,,,,,,索引表,數(shù)據(jù)表,假設(shè)內(nèi)存工作區(qū)僅能容納 64k 字節(jié)的數(shù)據(jù), 在某一時(shí)刻內(nèi)存最多可容納 64 個(gè)對(duì)象以供搜索。如果對(duì)象總數(shù)有 14400 個(gè), 不可能把所有對(duì)象的數(shù)據(jù)一次都讀入內(nèi)存。無論是順序搜索或折半搜索, 都需要多次讀取外存記錄。如果在索引表中每一個(gè)索引項(xiàng)占4個(gè)字節(jié), 每個(gè)索引項(xiàng)索引一個(gè)職工對(duì)象, 則 14400 個(gè)索引項(xiàng)需要 56.25k

5、 字節(jié), 在內(nèi)存中可以容納所有的索引項(xiàng)。,這樣只需從外存中把索引表讀入內(nèi)存, 經(jīng)過搜索索引后確定了職工對(duì)象的存儲(chǔ)地址, 再經(jīng)過 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ì)

6、象(子表)。,在子表中, 所有對(duì)象可能按關(guān)鍵碼有序地存放, 也可能無序地存放。但所有這些子表必須分塊有序, 后一個(gè)子表中所有對(duì)象的關(guān)鍵碼均大于前一個(gè)子表中所有對(duì)象的關(guān)鍵碼。它們都存放在數(shù)據(jù)區(qū)中。另外建立一個(gè)索引表。索引表中每一表目叫做索引項(xiàng)，它記錄了子表中最大關(guān)鍵碼max _key以及該子表在數(shù)據(jù)區(qū)中的起始位置obj _ addr。第 i 個(gè)索引項(xiàng)是第 i 個(gè)子表的索引項(xiàng), i = 0, 1, …, n-1。這樣的索引結(jié)構(gòu)叫做

7、索引順序結(jié)構(gòu)。,對(duì)索引順序結(jié)構(gòu)進(jìn)行搜索時(shí)，一般分為兩級(jí)搜索:先在索引表 ID 中搜索給定值 K, 確定滿足 ID[i-1].max_key < K ? ID[i].max_key,,,,,22 12 13 30 29 33,,,,,,,,,,,,,,,,,,,,,36 42 44 48 39 40,60 74 56 79 80 66,92 82 88 98 94,子表1,子表2,

8、子表3,子表4,數(shù)據(jù)區(qū),,33488098,,,,,索引表,1234,,,,,max_ max_ key addr,的 i 值, 即待查對(duì)象可能在的子表的序號(hào)。然后再在第 i 個(gè)子表中按給定值搜索要求的對(duì)象。索引表是按max_key有序的, 且長(zhǎng)度也不大,可以折半搜索，也可以順序搜索。各子表內(nèi)各個(gè)對(duì)象如果也按對(duì)象關(guān)鍵碼有序, 可以采用折半搜索或順序搜索; 如果不是按對(duì)象關(guān)鍵碼有序, 只能順序搜索。,索引

9、順序搜索的搜索成功時(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ì)象的搜索概率相等，則每個(gè)子表的搜索概率為1/b，子表內(nèi)各對(duì)象的搜索概率為

10、 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)，但比折半

11、搜索差。但如果子表存放在外存時(shí)，還要受到頁塊大小的制約。若采用折半搜索確定對(duì)象所在的子表, 則搜索成功時(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í)，最

12、常用的是針對(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) 列出所有教師的名單；,對(duì)象關(guān)鍵碼 key 對(duì)象存放地址 addr,,(2) 已婚的女性職工有哪些人？這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問

13、題，只能到表或文件中去順序搜索，搜索效率極低。因此，除主關(guān)鍵碼外，可以把一些經(jīng)常搜索的屬性設(shè)定為次關(guān)鍵碼，并針對(duì)每一個(gè)作為次關(guān)鍵碼的屬性，建立次索引。在次索引中，列出該屬性的所有取值，并對(duì)每一個(gè)取值建立有序鏈表，把所有具有相同屬性值的對(duì)象按存放地址遞增的順序或按主關(guān)鍵碼遞增的順序鏈接在一起。,次索引的索引項(xiàng)由次關(guān)鍵碼、鏈表長(zhǎng)度和鏈表本身等三部分組成。例如，為了回答上述的查詢，我們可以分別建立“性別”、“婚否”和“職務(wù)”次索引。,性

14、別次索引,,,,次關(guān)鍵碼 男 女 計(jì) 數(shù) 5 3 地址指針,,,,指針 03 08 17 24 47 51 83 95,,,,,,,,,,,,婚否次索引,,,,次關(guān)鍵碼 已婚 未婚 計(jì) 數(shù) 5 3 地址指針,,,,指針 03 08 24 47 83 17 51 95,,,,,,,,,,,職務(wù)次索引

15、,,,,次關(guān)鍵碼 教師 教務(wù)員 實(shí)驗(yàn)員 計(jì) 數(shù) 5 1 2 地址指針,,,指針 08 24 47 51 83 03 17 95,,,,,,,,,,,,,(1) 列出所有教師的名單；(2) 已婚的女性職工有哪些人？通過順序訪問“職務(wù)”次索引中的“教師”鏈，可以回答上面的查詢(1)。通過對(duì)“性別”和“婚否”次索引中的“女性”鏈和“已婚

16、”鏈進(jìn)行求“交”運(yùn)算，就能夠找到所有既是女性又已婚的職工對(duì)象，從而回答上面的查詢(2)。倒排表是次索引的一種實(shí)現(xiàn)。在表中所有次關(guān)鍵碼的鏈都保存在次索引中，僅通過搜索次索引就能找到所有具有相同屬性值的對(duì)象。,在次索引中記錄對(duì)象存放位置的指針可以用主關(guān)鍵碼表示: 可通過搜索次索引確定該對(duì)象的主關(guān)鍵碼, 再通過搜索主索引確定對(duì)象的存放地址。在倒排表中各個(gè)屬性鏈表的長(zhǎng)度大小不一,管理比較困難。為此引入單元式倒排表。在單元式倒排表中, 索引

17、項(xiàng)中不存放對(duì)象的存儲(chǔ)地址, 存放該對(duì)象所在硬件區(qū)域的標(biāo)識(shí)。硬件區(qū)域可以是磁盤柱面、磁道或一個(gè)頁塊, 以一次 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ì)象。如果在硬件區(qū)域1，……中有要求的

18、對(duì)象。然后將硬件區(qū)域1，……等讀入內(nèi)存，在其中進(jìn)行檢索，確定就可取出所需對(duì)象。,單元式倒排表結(jié)構(gòu),,m 路靜態(tài)搜索樹,當(dāng)數(shù)據(jù)對(duì)象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。此時(shí), 可以建立索引的索引(二級(jí)索引)。二級(jí)索引可以常駐內(nèi)存，二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址。,,,,,如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越?/p>

19、二級(jí)索引的索引(三級(jí)索引)。這時(shí)，訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對(duì)象。,,02 06,,11 15,,18 23,,,29 32,,,38 41,,,45 49,,,52 60,,77 95,,,(06, ) (15, ) (23, ),(06, ) (15, ) (23, ),,(32, ) (41, ) (49, ),,(60, ) (95, ),,(23, ) (41, ) (95, ),,roo

20、t,,,,,,,,,,,,,head,必要時(shí), 還可以有4級(jí)索引, 5極索引, …。這種多級(jí)索引結(jié)構(gòu)形成一種 m 叉樹。樹中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊, 它最多存放 m 個(gè)索引項(xiàng), 每個(gè)索引項(xiàng)分別給出各子樹結(jié)點(diǎn) (低一級(jí)索引塊) 的最大關(guān)鍵碼和結(jié)點(diǎn)地址。樹的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對(duì)象的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級(jí)索引，就是m路搜索樹。m路搜索樹可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型

21、，在整個(gè)運(yùn)行期間，樹的結(jié)構(gòu)不發(fā)生變化。,,,,,,,,,多級(jí)索引結(jié)構(gòu)形成 m 路搜索樹,,m路搜索樹還可能是動(dòng)態(tài)索引結(jié)構(gòu), 即在整個(gè)系統(tǒng)運(yùn)行期間, 樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整, 以保持最佳的搜索效率。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

22、,,,,,,,,,,,數(shù)據(jù)區(qū),一級(jí)索引,二級(jí)索引,三級(jí)索引,四級(jí)索引,動(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 ?

23、i ? n < m; Ki 是關(guān)鍵碼, 1 ? i ? n < m。 Ki < Ki+1, 1 ? i < n。,動(dòng)態(tài)的 m 路搜索樹,在子樹 Pi 中所有的關(guān)鍵碼都小于 Ki+1, 且大于 Ki，0 < i < n。 在子樹 Pn 中所有的關(guān)鍵碼都大于Kn； 在子樹 P0 中的所有關(guān)鍵碼都小于 K1。 子樹 Pi 也是 m 路搜索樹，0 ? i ? n。,一棵3路搜索樹的示例,35,20 4

24、0,a,b,c,d,e,,25 30,,10 15,,45 50,,m 路搜索樹的類定義template class Mtree { //基類 public: Triple & Search ( const Type & );protected: Mnode root; int m;},AVL樹是2路搜索樹。如果已知 m 路搜索樹的度 m 和它的

25、高度 h, 則樹中的最大結(jié)點(diǎn)數(shù)為,(等比級(jí)數(shù)前 h 項(xiàng)求和),,每個(gè)結(jié)點(diǎn)中最多有 m-1 個(gè)關(guān)鍵碼，在一棵高度為 h 的 m 路搜索樹中關(guān)鍵碼的最大個(gè)數(shù)為 mh+1-1。高度 h=2 的二叉樹, 關(guān)鍵碼最大個(gè)數(shù)為7；高度 h=3 的3路搜索樹, 關(guān)鍵碼最大個(gè)數(shù)為 34-1 = 80。,struct Triple { Mnode * r; //結(jié)點(diǎn)地址指針 int i; int tag;

26、 //結(jié)點(diǎn)中關(guān)鍵碼序號(hào) i}; //tag=0,搜索成功；tag=1,搜索不成功,標(biāo)識(shí) m 路搜索樹搜索結(jié)果的三元組表示,m 路搜索樹上的搜索算法,在 m 路搜索樹上的搜索過程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和自根結(jié)點(diǎn)向下逐個(gè)結(jié)點(diǎn)搜索的交替的過程。,35,20 40,a,b,c,d,e,,25 30,,10 15,,45 50,,,root,,,搜索35,template Triple & Mtree

27、 :: Search ( const Type& x ) { Triple result; //記錄搜索結(jié)果三元組 GetNode ( root ); //讀入根結(jié)點(diǎn) Mnode *p = root, *q = NULL; while ( p != NULL ) { //從根開始檢測(cè) int i = 0; p->ke

28、y[(p->n)+1] = MAXKEY; while ( p->key[i+1] key[i+1] == x ) { //搜索成功 result.r = p; result.i = i+1; result.tag = 0; return result; },q = p; p = p->ptr[i]; //向下一層結(jié)點(diǎn)搜索

29、 GetNode (p); //讀入該結(jié)點(diǎn) } result.r = q; result.i = i; result.tag = 1; return result; //搜索失敗,返回插入位置},提高搜索樹的路數(shù) m, 可以改善樹的搜索性能。對(duì)于給定的關(guān)鍵碼數(shù) n，如果搜索樹是平衡的，可以使 m 路搜索樹的性能接近最佳。下面將討論一種稱之為B 樹的平衡的

30、 m 路搜索樹。,B 樹,一棵 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)。事實(shí)上，在B 樹的每個(gè)結(jié)點(diǎn)中還包含有一組指針D[m]，指向?qū)嶋H對(duì)象的存放地址。,30,,,K[i]與D[i] (1 ? i

31、? n < m) 形成一個(gè)索引項(xiàng)(K[i], D[i])，通過K[i]可找到某個(gè)對(duì)象的存儲(chǔ)地址D[i]。一棵B 樹是平衡的 m 路搜索樹，但一棵平衡的 m 路搜索樹不一定是B 樹。,35,20 40,,25 30,,10 15,,45 50,,root,45 50,35,40,20,,root,,,,10 15,,25,,非B 樹 B 樹,,B 樹的類定義和B 樹結(jié)點(diǎn)類定義templa

32、te class Btree : public Mtree {//繼承 m 路搜索樹的所有屬性和操作public: int Insert ( const Type& x ); int Remove ( const Type& x );};template class Mnode { // B 樹結(jié)點(diǎn)類定義private:,int n;

33、 //結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) Mnode *parent; //雙親指針 Type key[m+1]; //關(guān)鍵碼數(shù)組 1?m-1 Mnode *ptr[m+1]; //子樹指針數(shù)組};,B 樹的搜索算法,B 樹的搜索算法繼承了 m 路搜索樹Mtree上的搜索算法。B 樹的搜索過程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過程

34、。,B 樹的搜索時(shí)間與B 樹的階數(shù) m 和B 樹的高度h直接有關(guān), 必須加以權(quán)衡。在B 樹上進(jìn)行搜索, 搜索成功所需的時(shí)間取決于關(guān)鍵碼所在的層次; 搜索不成功所需的時(shí)間取決于樹的高度。如果定義B 樹的高度h 為失敗結(jié)點(diǎn)所在的層次，需要了解樹的高度h 與樹中的關(guān)鍵碼個(gè)數(shù) N 之間的關(guān)系。如果讓B 樹每層結(jié)點(diǎn)個(gè)數(shù)達(dá)到最大，且設(shè)關(guān)鍵碼總數(shù)為N, 則樹的高度達(dá)到最?。?h = ?logm( N*(m-2)/(m-1)+

35、1)? -1,設(shè)在 m 階B 樹中每層結(jié)點(diǎn)個(gè)數(shù)達(dá)到最少, 則B 樹的高度可能達(dá)到最大。設(shè)樹中關(guān)鍵碼個(gè)數(shù)為 N，從B 樹的定義知： 0層 1 個(gè)結(jié)點(diǎn) 1層 至少 2 個(gè)結(jié)點(diǎn) 2層 至少 2 ?m / 2? 個(gè)結(jié)點(diǎn) 3層 至少 2 ?m / 2? 2 個(gè)結(jié)點(diǎn) 如此類推，?? h-1 層 至少有 2 ?m / 2? h-2 個(gè)結(jié)點(diǎn)。所有這些結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。,高度h與關(guān)鍵碼個(gè)數(shù)N之間的關(guān)系,若樹中關(guān)鍵碼有N個(gè),

36、 則失敗結(jié)點(diǎn)數(shù)為N+1。這是因?yàn)槭?shù)據(jù)一般與已有關(guān)鍵碼交錯(cuò)排列。因此，有 N +1 = 失敗結(jié)點(diǎn)數(shù) = 位于第 h 層的結(jié)點(diǎn)數(shù) ? 2 ?m / 2? h-1 ? N ? 2 ?m / 2? h-1-1 ? h-1 ? log ?m / 2? ( (N +1) / 2 )所有的非失敗結(jié)點(diǎn)所在層次為0 ? h-1。示例：若B 樹的階數(shù) m = 199, 關(guān)鍵碼總數(shù) N

37、 = 1999999，則B 樹的高度 h 不超過 log100 1000000 +1= 4,m值的選擇,如果提高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í)間總量

38、達(dá)到最小。這個(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) (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 =

39、a + bm,B 樹的插入,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)為,( m,

40、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, ……, K?m/2? -1, P?m/2? -1) 結(jié)點(diǎn) q：(m-?m/2?, P?m/2?, K?m/2?+1, P?m/2?+1, ……, Km,

41、Pm)位于中間的關(guān)鍵碼 K?m/2? 與指向新結(jié)點(diǎn) q 的指針形成一個(gè)二元組 ( K?m/2?, q )，插入到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)中去。,結(jié)點(diǎn)“分裂”的示例,,,,,,,2 53 75,n P0 K1 P1 K2 P2,p,,,,,3 53 75 139,n P0 K1 P1 K2 P2 K3 P3,p,,,,,,,,,,,,,加入

42、139, 結(jié)點(diǎn)溢出,,1 75,n P0 K1 P1,,,,,,,1 53,n P0 K1 P1,,,,,,,1 139,n P0 K1 P1,,,,,,,,,,,結(jié)點(diǎn)分裂,P,q,49 75,示例:從空樹開始加入關(guān)鍵碼建立3階B 樹,n=1 加入53,53,,,n=2 加入75,53 75,,,,n=3 加入139,75,,,139,,,53,,,n=5 加

43、入49,145,75,,,139 145,,,49 53,,,,,n=6 加入36,,,139 145,,,,53,36,,,,,,在插入新關(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 加入101,49,,,53,,,36,,,139,,,145,,,101,,,75,,,B 樹的插入算

44、法template int Btree :: Insert ( const Type & x ) { Triple loc = Search (x); //找x的位置 if ( !loc.tag ) return 0; //找到,不再插入 Mnode *p = loc.r, *q; //未找到,插入 Mnode *ap = NULL, *t; Type

45、K = x; int j = loc.i; //插入位置p, j while (1) { if ( p->n < m-1) { //當(dāng)前結(jié)點(diǎn)未滿 insertkey ( p, j, K, ap ); //(K,ap)插入 j后 PutNode (p); return 1; //寫出,}

46、 //結(jié)點(diǎn)已滿,分裂 int s = (m+1)/2; //求 ?m/2? insertkey ( p, j, K, ap ); //(K,ap)插入 j后 q = new Mnode; //建立新結(jié)點(diǎn) move ( p, q, s, m );

47、 //從 p向q 搬送 K = p->key[s]; ap = q; //分界碼上移 if ( p->parent != NULL ) { //雙親不是根 t = p->parent; GetNode (t); //讀入雙親 j = 0; t->key[(t->n)+1] = MAXK

48、EY; while ( t->key[j+1] parent = p->parent; PutNode (p); PutNode (q);,p = t; } //繼續(xù) while(1) 循環(huán),向上調(diào)整 else {

49、 //雙親是根 root = new Mnode; //創(chuàng)建新根 root->n = 1; root->parent = NULL; root->key[1] = K; root->ptr[0] = p; root->ptr[1] = ap; q->parent = p->parent =

50、 root; PutNode (p); PutNode (q); PutNode (root); return 1; //跳出返回} }},當(dāng)分裂一個(gè)非根的結(jié)點(diǎn)時(shí)需要向磁盤寫出 2 個(gè)結(jié)點(diǎn), 當(dāng)分裂根結(jié)點(diǎn)時(shí)需要寫出 3 個(gè)結(jié)點(diǎn)。如果我們所用的內(nèi)存工作區(qū)足夠大, 使得在向下搜索時(shí), 讀入的結(jié)點(diǎn)在插入后向上分裂時(shí)不必再?gòu)拇疟P讀入, 那么, 在完成一次插入操作時(shí)需要讀寫磁盤的次數(shù)

51、= = 找插入結(jié)點(diǎn)向下讀盤次數(shù) + + 分裂非根結(jié)點(diǎn)時(shí)寫盤次數(shù) + + 分裂根結(jié)點(diǎn)時(shí)寫盤次數(shù) = = h+2(h-1)+3 = = 3h+1。,B 樹的刪除,在B 樹上刪除一個(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)

52、鍵碼之后, 應(yīng)以該結(jié)點(diǎn) Pi 所指示子樹中的最小關(guān)鍵碼 x 來代替被刪關(guān)鍵碼 Ki 所在的位置, 然后在 x 所在的葉結(jié)點(diǎn)中刪除 x。在葉結(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é)束。 被刪

53、關(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á)到新的平衡。,36 49,,,,m = 3,,刪除36,49,,,55 58,,刪除55,簡(jiǎn)單刪除,75 80,,,,m = 3,,刪除55,10,,,40,,,,,65,,,60 70,,,,30,,,50,,,a,

54、c,b,d,e,f,g,h,,58,75 80,,,,10,,,40,,,,65,,,60 70,,,,30,,,50,,,a,c,b,d,e,f,g,h,,將雙親結(jié)點(diǎn)中剛剛大于 (或小于) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 ? i ? n) 下移；將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最小 (或最大)關(guān)鍵碼上移到雙親結(jié)點(diǎn)的 Ki 位置；將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最左 (或最右) 子樹指針平移到被刪關(guān)鍵碼所在結(jié)點(diǎn)中最后 (或

55、最前) 子樹指針位置；在右兄弟 (或左兄弟) 結(jié)點(diǎn)中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補(bǔ)、調(diào)整。再將結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減1。,結(jié)點(diǎn)聯(lián)合調(diào)整,55 58,75 80,,,,m = 3,,刪除65,10,,,40,,,,,65,,,60 70,,,,30,,,50,,,a,c,b,d,e,f,g,h,,55 58,80,,,10,,,40,,,,,70,,,60 75,,,,30,,,50,,,a,c,b,d,e

56、,f,g,h,,調(diào)整g,c,h,,刪除65,,70,,刪除70,55 58,80,,,m = 3,,刪除70,10,,,40,,,,,,,60 75,,,,30,,,50,,,a,c,b,d,e,f,g,h,,55,80,,,10,,,40,,,,,60,,,58 75,,,,30,,,50,,,a,c,b,d,e,f,g,h,調(diào)整f,c,g,,結(jié)點(diǎn)聯(lián)合調(diào)整,被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù) n = ?m/2? -1, 若這時(shí)

57、與該結(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)鍵碼下移到選定保留的結(jié)點(diǎn)中。若要合并 p 中的子樹指針 Pi 與 Pi+1 所指的結(jié)點(diǎn), 且保留 Pi 所指結(jié)點(diǎn),則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點(diǎn)中。 把 p 中子樹指針 Pi+1 所指結(jié)點(diǎn)中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點(diǎn)的后面。刪去 Pi+1 所指的結(jié)點(diǎn)。,在結(jié)

58、點(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)的過程中, 雙親結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減少了。若雙親結(jié)點(diǎn)是根結(jié)點(diǎn)且結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)減到 0, 則將該雙親結(jié)點(diǎn)刪去, 合并后保留的結(jié)點(diǎn)成為新的根結(jié)點(diǎn); 否則將雙親結(jié)點(diǎn)與合并后保留的結(jié)點(diǎn)都寫回磁盤, 刪除處理結(jié)束。若雙親結(jié)點(diǎn)不是根結(jié)點(diǎn)且關(guān)鍵碼個(gè)數(shù)減到?m/2? -2，又要與它自己的兄弟結(jié)點(diǎn)合并, 重復(fù)上面的合并

59、步驟。最壞情況下這種結(jié)點(diǎn)合并處理要自下向上直到根結(jié)點(diǎn)。,55,,刪除55,結(jié)點(diǎn)合并,80,,,m = 3,,刪除55,10,,,40,,,,60,,,58 75,,,,30,,,50,,,a,c,b,d,e,f,g,h,,合并f, g,,58 60,80,,,10,,,40,,,,,75,,,30,,,50,,,a,c,b,d,e,f,h,,80,55,,刪除80,結(jié)點(diǎn)合并,,,m = 3,,刪除80,10,,,40,,,,60,,

60、,58 75,,,,30,,,50,,,a,c,b,d,e,f,g,h,,合并g, h,,60 75,55,,,10,,,40,,,,,58,,,30,,,50,,,a,c,b,d,e,f,h,,55,非葉結(jié)點(diǎn)刪除,,刪除50,,,刪除55,55 58,75 80,,,,m = 3,,刪除50,10,,,40,,,,,65,,,60 70,,,,30,,,50,,,a,c,b,d,e,f,g,h,,58,75 80,,,,,

61、刪除55,10,,,40,,,,65,,,60 70,,,,30,,,,,a,c,b,d,e,f,g,h,,用55取代,用58取代,,58,,75 80,,,,10,,,40,,,,65,,,60 70,,,,30,,,,,a,c,b,d,e,f,g,h,,,,合并f, g,58,75 80,,,,10,,,40,,,60 65,,70,,,30,,,,,a,c,b,d,e,f,h,,,結(jié)點(diǎn)合并與調(diào)整,,刪除70,58,80,

62、,,10,,,40,,,60 65,,75,,,30,,,,,a,c,b,d,e,f,h,,,,刪除70,用75取代,,刪除75,58,,,,10,,,40,,,60 65,,80,,,30,,,,,a,c,b,d,e,f,h,,,,刪除75,用80取代調(diào)整f, c, h,,58,80,,,10,,,40,,,60,65,,,30,,,,,a,c,b,d,e,f,h,,,,刪除10,,,80,,,30 40,,,60,f,h,,

63、,,58 65,d,,,,b,B 樹的關(guān)鍵碼刪除算法template int Btree ::Delete ( const Type & x ) { Triple loc = Search (x); //搜索x if ( loc.tag ) return 0; //未找到,不刪除 Mnode *p = loc.r, *q, *s; //找到,刪除 int j

64、 = loc.i; if ( p->ptr[j] != NULL ) { //非葉結(jié)點(diǎn) s = p->ptr[j]; GetNode (s); q = p; while ( s != NULL ) { q = s; s = s->ptr[0]; } p->key[j] = q->key[1]; //從葉

65、結(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) {

66、 //調(diào)整或合并 if ( p->n parent; //找到雙親 GetNode (q); while ( j n && q->ptr[j] != p ) j++; if ( !j ) LeftAdjust ( p, q, d, j ); //調(diào)整

67、else RightAdjust ( p, q, d, j );,p = q; //向上調(diào)整 if ( p == root ) break; } else break; } if ( !root->n ) { //調(diào)整后根的n減到0 p = root->ptr[0];

68、delete root; root = p; //刪根 root->parent = NULL; //新根 }},B+樹,一棵 m 階B+樹可以定義如下： 樹中每個(gè)非葉結(jié)點(diǎn)最多有 m 棵子樹； 根結(jié)點(diǎn)(非葉結(jié)點(diǎn))至少有 2 棵子樹。除根結(jié)點(diǎn)外, 其它的非葉結(jié)點(diǎn)至少有 ?m/2? 棵子樹; 有 n 棵子樹的非葉結(jié)點(diǎn)有 n-1 個(gè)關(guān)鍵碼。 所有葉結(jié)點(diǎn)都處于同一層次上, 包含了全部關(guān)鍵

69、碼及指向相應(yīng)數(shù)據(jù)對(duì)象存放地址的指針, 且葉結(jié)點(diǎn)本身按關(guān)鍵碼從小到大順序鏈接；,葉結(jié)點(diǎn)的子樹棵數(shù) n 可以多于 m, 可以少于 m, 視關(guān)鍵碼字節(jié)數(shù)及對(duì)象地址指針字節(jié)數(shù)而定。若設(shè)結(jié)點(diǎn)可容納最大關(guān)鍵碼數(shù)為 m1, 則指向?qū)ο蟮牡刂分羔樢灿?m1 個(gè)。,,10 15,,18 20 22,,23 31,,33 45,,48 52,,,,,,,,18 23,,,,,,33,,33,,,,葉結(jié)點(diǎn)中的子樹棵數(shù) n 應(yīng)滿足