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

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

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

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

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

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

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

7、索引順序結(jié)構(gòu)。,對索引順序結(jié)構(gòu)進(jìn)行搜索時，一般分為兩級搜索:先在索引表 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 值, 即待查對象可能在的子表的序號。然后再在第 i 個子表中按給定值搜索要求的對象。索引表是按max_key有序的, 且長度也不大,可以折半搜索，也可以順序搜索。各子表內(nèi)各個對象如果也按對象關(guān)鍵碼有序, 可以采用折半搜索或順序搜索; 如果不是按對象關(guān)鍵碼有序, 只能順序搜索。,索引

9、順序搜索的搜索成功時的平均搜索長度 ASLIndexSeq = ASLIndex + ASLSubList其中, ASLIndex 是在索引表中搜索子表位置的平均搜索長度，ASLSubList 是在子表內(nèi)搜索對象位置的搜索成功的平均搜索長度。設(shè)把長度為 n 的表分成均等的 b 個子表，每個子表 s 個對象，則 b = ?n/s?。又設(shè)表中每個對象的搜索概率相等，則每個子表的搜索概率為1/b，子表內(nèi)各對象的搜索概率為

10、 1/s。若對索引表和子表都用順序搜索，則索引順序搜索的搜索成功時的平均搜索長度為 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1,索引順序搜索的平均搜索長度與表中的對象個數(shù) n 有關(guān)，與每個子表中的對象個數(shù) s 有關(guān)。在給定 n 的情況下，s 應(yīng)選擇多大？用數(shù)學(xué)方法可導(dǎo)出, 當(dāng) s = 時, ASLIndexSeq取極小值 +1。這個值比順序搜索強(qiáng)，但比折半

11、搜索差。但如果子表存放在外存時，還要受到頁塊大小的制約。若采用折半搜索確定對象所在的子表, 則搜索成功時的平均搜索長度為 ASLIndexSeq = ASLIndex + ASLSubList ? log2 (b+1)-1 + (s+1)/2 ? log2(1+n / s ) + s/2,倒排表 (Inverted Index List),對包含有大量數(shù)據(jù)對象的數(shù)據(jù)表或文件進(jìn)行搜索時，最

12、常用的是針對對象的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標(biāo)識該對象。用主關(guān)鍵碼建立的索引叫做主索引。主索引的每個索引項給出對象的關(guān)鍵碼和對象在表或文件中的存放地址。但在實際應(yīng)用中有時需要針對其它屬性進(jìn)行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?(1) 列出所有教師的名單；,對象關(guān)鍵碼 key 對象存放地址 addr,,(2) 已婚的女性職工有哪些人？這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問

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

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

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

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

17、項中不存放對象的存儲地址, 存放該對象所在硬件區(qū)域的標(biāo)識。硬件區(qū)域可以是磁盤柱面、磁道或一個頁塊, 以一次 I / O 操作能存取的存儲空間作為硬件區(qū)域為最好。,為使索引空間最小, 在索引中標(biāo)識這個硬件區(qū)域時可以使用一個能轉(zhuǎn)換成地址的二進(jìn)制數(shù),整個次索引形成一個(二進(jìn)制數(shù)的) 位矩陣。例如, 對于記錄學(xué)生信息的文件, 次索引可以是如圖所示的結(jié)構(gòu)。二進(jìn)位的值為 1 的硬件區(qū)域包含具有該次關(guān)鍵碼的對象。如果在硬件區(qū)域1，……中有要求的

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

19、二級索引的索引(三級索引)。這時，訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對象。,,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,必要時, 還可以有4級索引, 5極索引, …。這種多級索引結(jié)構(gòu)形成一種 m 叉樹。樹中每一個分支結(jié)點表示一個索引塊, 它最多存放 m 個索引項, 每個索引項分別給出各子樹結(jié)點 (低一級索引塊) 的最大關(guān)鍵碼和結(jié)點地址。樹的葉結(jié)點中各索引項給出在數(shù)據(jù)表中存放的對象的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級索引，就是m路搜索樹。m路搜索樹可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時就已經(jīng)定型

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

22、,,,,,,,,,,,數(shù)據(jù)區(qū),一級索引,二級索引,三級索引,四級索引,動態(tài)搜索結(jié)構(gòu),現(xiàn)在我們所討論的 m 路搜索樹多為可以動態(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。,動態(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é)點數(shù)為,(等比級數(shù)前 h 項求和),,每個結(jié)點中最多有 m-1 個關(guān)鍵碼，在一棵高度為 h 的 m 路搜索樹中關(guān)鍵碼的最大個數(shù)為 mh+1-1。高度 h=2 的二叉樹, 關(guān)鍵碼最大個數(shù)為7；高度 h=3 的3路搜索樹, 關(guān)鍵碼最大個數(shù)為 34-1 = 80。,struct Triple { Mnode * r; //結(jié)點地址指針 int i; int tag;

26、 //結(jié)點中關(guān)鍵碼序號 i}; //tag=0,搜索成功；tag=1,搜索不成功,標(biāo)識 m 路搜索樹搜索結(jié)果的三元組表示,m 路搜索樹上的搜索算法,在 m 路搜索樹上的搜索過程是一個在結(jié)點內(nèi)搜索和自根結(jié)點向下逐個結(jié)點搜索的交替的過程。,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é)點 Mnode *p = root, *q = NULL; while ( p != NULL ) { //從根開始檢測 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é)點搜索

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

30、 m 路搜索樹。,B 樹,一棵 m 階B 樹是一棵平衡的 m 路搜索樹, 它或者是空樹, 或者是滿足下列性質(zhì)的樹： 根結(jié)點至少有 2 個子女。 除根結(jié)點以外的所有結(jié)點 (不包括失敗結(jié)點)至少有 ?m/2? 個子女。 所有的失敗結(jié)點都位于同一層。在B 樹中的“失敗”結(jié)點是當(dāng)搜索值x不在樹中時才能到達(dá)的結(jié)點。事實上，在B 樹的每個結(jié)點中還包含有一組指針D[m]，指向?qū)嶋H對象的存放地址。,30,,,K[i]與D[i] (1 ? i

31、? n < m) 形成一個索引項(K[i], D[i])，通過K[i]可找到某個對象的存儲地址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é)點類定義templa

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

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

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

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

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

37、 = 1999999，則B 樹的高度 h 不超過 log100 1000000 +1= 4,m值的選擇,如果提高B 樹的階數(shù) m, 可以減少樹的高度, 從而減少讀入結(jié)點的次數(shù), 因而可減少讀磁盤的次數(shù)。事實上，m 受到內(nèi)存可使用空間的限制。當(dāng) m 很大超出內(nèi)存工作區(qū)容量時, 結(jié)點不能一次讀入到內(nèi)存, 增加了讀盤次數(shù), 也增加了結(jié)點內(nèi)搜索的難度。 m值的選擇 : 應(yīng)使得在B 樹中找到關(guān)鍵碼 x 的時間總量

38、達(dá)到最小。這個時間由兩部分組成：,從磁盤中讀入結(jié)點所用時間在結(jié)點中搜索 x 所用時間根據(jù)定義, B 樹的每個結(jié)點的大小都是固定的, 結(jié)點內(nèi)有 m-1 個索引項 (Ki, Di, Pi), 1 ? i < m。其中，Ki 所占字節(jié)數(shù)為?，Di 和 Pi 所占字節(jié)數(shù)為?，則結(jié)點大小近似為 m(?+2?) 個字節(jié)。讀入一個結(jié)點所用時間為： tseek + tlatency + m(? + 2?) ttran =

39、a + bm,B 樹的插入,B 樹是從空樹起, 逐個插入關(guān)鍵碼而生成的。在B 樹，每個非失敗結(jié)點的關(guān)鍵碼個數(shù)都在 [ ?m/2? -1, m-1] 之間。插入在某個葉結(jié)點開始。如果在關(guān)鍵碼插入后結(jié)點中的關(guān)鍵碼個數(shù)超出了上界 m-1，則結(jié)點需要“分裂”，否則可以直接插入。實現(xiàn)結(jié)點“分裂”的原則是：設(shè)結(jié)點 p 中已經(jīng)有 m-1 個關(guān)鍵碼，當(dāng)再插入一個關(guān)鍵碼后結(jié)點中的狀態(tài)為,( m,

40、P0, K1, P1, K2, P2, ……, Km, Pm) 其中 Ki < Ki+1, 1 ? i < m這時必須把結(jié)點 p 分裂成兩個結(jié)點 p 和 q，它們包含的信息分別為： 結(jié)點 p：( ?m/2? -1, P0, K1, P1, ……, K?m/2? -1, P?m/2? -1) 結(jié)點 q：(m-?m/2?, P?m/2?, K?m/2?+1, P?m/2?+1, ……, Km,

41、Pm)位于中間的關(guān)鍵碼 K?m/2? 與指向新結(jié)點 q 的指針形成一個二元組 ( K?m/2?, q )，插入到這兩個結(jié)點的雙親結(jié)點中去。,結(jié)點“分裂”的示例,,,,,,,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é)點溢出,,1 75,n P0 K1 P1,,,,,,,1 53,n P0 K1 P1,,,,,,,1 139,n P0 K1 P1,,,,,,,,,,,結(jié)點分裂,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)鍵碼時，需要自底向上分裂結(jié)點，最壞情況下從被插關(guān)鍵碼所在葉結(jié)點到根的路徑上的所有結(jié)點都要分裂。,若設(shè)B 樹的高度為h, 那么在自頂向下搜索到葉結(jié)點的過程中需要進(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é)點未滿 insertkey ( p, j, K, ap ); //(K,ap)插入 j后 PutNode (p); return 1; //寫出,}

46、 //結(jié)點已滿,分裂 int s = (m+1)/2; //求 ?m/2? insertkey ( p, j, K, ap ); //(K,ap)插入 j后 q = new Mnode; //建立新結(jié)點 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)分裂一個非根的結(jié)點時需要向磁盤寫出 2 個結(jié)點, 當(dāng)分裂根結(jié)點時需要寫出 3 個結(jié)點。如果我們所用的內(nèi)存工作區(qū)足夠大, 使得在向下搜索時, 讀入的結(jié)點在插入后向上分裂時不必再從磁盤讀入, 那么, 在完成一次插入操作時需要讀寫磁盤的次數(shù)

51、= = 找插入結(jié)點向下讀盤次數(shù) + + 分裂非根結(jié)點時寫盤次數(shù) + + 分裂根結(jié)點時寫盤次數(shù) = = h+2(h-1)+3 = = 3h+1。,B 樹的刪除,在B 樹上刪除一個關(guān)鍵碼時, 首先需要找到這個關(guān)鍵碼所在的結(jié)點, 從中刪去這個關(guān)鍵碼。若該結(jié)點不是葉結(jié)點, 且被刪關(guān)鍵碼為 Ki, 1 ? i ? n, 則在刪去該關(guān)

52、鍵碼之后, 應(yīng)以該結(jié)點 Pi 所指示子樹中的最小關(guān)鍵碼 x 來代替被刪關(guān)鍵碼 Ki 所在的位置, 然后在 x 所在的葉結(jié)點中刪除 x。在葉結(jié)點上的刪除有 4 種情況。 被刪關(guān)鍵碼所在葉結(jié)點同時又是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n ? 2，則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤。,被刪關(guān)鍵碼所在葉結(jié)點不是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n ? ?m/2? , 則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤, 刪除結(jié)束。 被刪

53、關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = ?m/2? -1, 若這時與該結(jié)點相鄰的右兄弟 (或左兄弟) 結(jié)點的關(guān)鍵碼個數(shù) n ? ?m/2?，則可按以下步驟調(diào)整該結(jié)點、右兄弟 (或左兄弟) 結(jié)點以及其雙親結(jié)點，以達(dá)到新的平衡。,36 49,,,,m = 3,,刪除36,49,,,55 58,,刪除55,簡單刪除,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é)點中剛剛大于 (或小于) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 ? i ? n) 下移；將右兄弟 (或左兄弟) 結(jié)點中的最小 (或最大)關(guān)鍵碼上移到雙親結(jié)點的 Ki 位置；將右兄弟 (或左兄弟) 結(jié)點中的最左 (或最右) 子樹指針平移到被刪關(guān)鍵碼所在結(jié)點中最后 (或

55、最前) 子樹指針位置；在右兄弟 (或左兄弟) 結(jié)點中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補(bǔ)、調(diào)整。再將結(jié)點中的關(guān)鍵碼個數(shù)減1。,結(jié)點聯(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é)點聯(lián)合調(diào)整,被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = ?m/2? -1, 若這時

57、與該結(jié)點相鄰的右兄弟 (或左兄弟) 結(jié)點的關(guān)鍵碼個數(shù) n = ?m/2? -1, 則必須按以下步驟合并這兩個結(jié)點。將雙親結(jié)點 p 中相應(yīng)關(guān)鍵碼下移到選定保留的結(jié)點中。若要合并 p 中的子樹指針 Pi 與 Pi+1 所指的結(jié)點, 且保留 Pi 所指結(jié)點,則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點中。 把 p 中子樹指針 Pi+1 所指結(jié)點中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點的后面。刪去 Pi+1 所指的結(jié)點。,在結(jié)

58、點 p 中用后面剩余的關(guān)鍵碼和指針填補(bǔ)關(guān)鍵碼 Ki+1 和指針 Pi+1。 修改結(jié)點 p 和選定保留結(jié)點的關(guān)鍵碼個數(shù)。 在合并結(jié)點的過程中, 雙親結(jié)點中的關(guān)鍵碼個數(shù)減少了。若雙親結(jié)點是根結(jié)點且結(jié)點關(guān)鍵碼個數(shù)減到 0, 則將該雙親結(jié)點刪去, 合并后保留的結(jié)點成為新的根結(jié)點; 否則將雙親結(jié)點與合并后保留的結(jié)點都寫回磁盤, 刪除處理結(jié)束。若雙親結(jié)點不是根結(jié)點且關(guān)鍵碼個數(shù)減到?m/2? -2，又要與它自己的兄弟結(jié)點合并, 重復(fù)上面的合并

59、步驟。最壞情況下這種結(jié)點合并處理要自下向上直到根結(jié)點。,55,,刪除55,結(jié)點合并,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é)點合并,,,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é)點刪除,,刪除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à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é)點 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é)點替補(bǔ) compress ( q, 1 ); //在葉結(jié)點刪除,p = q; //轉(zhuǎn)化為葉結(jié)點的刪除 } else compress ( p, j ); //葉結(jié)點,直接刪除 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+樹可以定義如下： 樹中每個非葉結(jié)點最多有 m 棵子樹； 根結(jié)點(非葉結(jié)點)至少有 2 棵子樹。除根結(jié)點外, 其它的非葉結(jié)點至少有 ?m/2? 棵子樹; 有 n 棵子樹的非葉結(jié)點有 n-1 個關(guān)鍵碼。 所有葉結(jié)點都處于同一層次上, 包含了全部關(guān)鍵

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