深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017-B-樹演示文檔

.,B-樹,前面討論的查找算法都是在內(nèi)存中進(jìn)行的，它們適用于較小的文件，而對較大的、存放在外存儲器上的文件就不合適了。 1972年R.Bayer和E.M.McCreight提出了一種稱為B-樹的多路平衡查找樹，它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表。,一. B-樹的定義,B-樹是一種平衡的多路查找樹，在文件系統(tǒng)中，成為索引文件的一種有效結(jié)構(gòu)，得到廣泛應(yīng)用。,,.,一棵m階（m?3）B-樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹： （1）樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹； （2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，至少有兩棵子樹； （3）所有的非終端結(jié)點(diǎn)中包含下列信息 （n，p0，k1，p1，k2，p2，…，kn，pn） 其中：ki（1?i?n）為關(guān)鍵字，且ki<ki+1（1?i?n）； pj（0?j?n）為指向子樹根結(jié)點(diǎn)的指針,且pj（0?j<n）所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于kj+1， pn所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于kn， n（?m/2?-1?n?m-1)為關(guān)鍵字的個(gè)數(shù)（n+1為子樹個(gè)數(shù)）。,B-樹,,.,（4）除根結(jié)點(diǎn)之外所有非終端結(jié)點(diǎn)至少有?m/2?棵子樹，也即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有?m/2?-1個(gè)關(guān)鍵字； （5）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，并且不帶信息（可看作外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。,B-樹,,.,2 50 80,,,,,,,,,,,,,root,,,,,2 20 40,,,,,,2 55 70,,,,,,,,,,,,,[例]一棵3階的B-樹,B-樹,,.,B-樹的基本操作,B-樹的查找運(yùn)算,2 50 80,,,,,,,,,,,,,root,,,,,2 20 40,,,,,,2 55 70,,,,,,,,,,,,,,.,B-樹的插入運(yùn)算,在B-樹中插入關(guān)鍵字k的方法： 首先在樹中查找k，找到,直接返回（假設(shè)不處理相同關(guān)鍵字的插入）； 否則查找操作必失敗于某個(gè)葉子結(jié)點(diǎn)上，可以確定關(guān)鍵字k的插入位置，將k插入到所指葉結(jié)點(diǎn)位置上。 若該葉結(jié)點(diǎn)原來非滿（結(jié)點(diǎn)中原有關(guān)鍵字總數(shù)小于m-1），則插入k并不會破壞B-樹的性質(zhì)，故插入操作完成，例如，在下圖所示5階B-樹的某結(jié)點(diǎn)（假設(shè)為p結(jié)點(diǎn)）中插入新的關(guān)鍵字150時(shí)的結(jié)果。,B-樹的基本操作,,.,2 100 190,,,,,,,,,,,,3 100 150 190,,,,,,,,,,,,,,,,在關(guān)鍵字個(gè)數(shù)不滿的結(jié)點(diǎn)中插入關(guān)鍵字,若p所指示的葉結(jié)點(diǎn)原為滿，則插入后破壞了B-樹的性質(zhì)（1），須調(diào)整使其維持B-樹的性質(zhì)不變。,B-樹的基本操作,,.,調(diào)整方法: 將違反性質(zhì)（1）的結(jié)點(diǎn)以中間位置的關(guān)鍵字key[?m/2?]為劃分點(diǎn)，將該結(jié)點(diǎn)（即p） （m，p0，k1，p1，…，km，pm） 分裂為兩個(gè)結(jié)點(diǎn) 左邊:（?m/2?-1，p0，k1，…k?m/2?-1，p?m/2?-1） 右邊:（m-?m/2?，p?m/2?，k?m/2?+1，…，km，pm） 同時(shí)把中間關(guān)鍵字k?m/2?插入到雙親結(jié)點(diǎn)中。于是雙親結(jié)點(diǎn)中指向被插入結(jié)點(diǎn)的指針pre改成pre、k?m/2?、pre’三部分。指針pre指向分裂后的左邊結(jié)點(diǎn)，指針pre’指向分裂后的右邊結(jié)點(diǎn)。由于將k?m/2?插入雙親時(shí)，雙親結(jié)點(diǎn)亦可能原本為滿，若如此，則需對雙親做分裂操作。分裂過程的例子如圖所示。,B-樹的基本操作,,.,2 … 80 220…,,,,,,4 90 120 140 160,,,,,,,,,,,,,,,,,,,,,,p,3 … 80 120 220 …,,,,,,,,2 90 100,,,,,,2 140 160,,,,,,,,,,,,,,,,,,,,pre,pre,pre’,k?m/2?,,插入100以前,插入100以后,B-樹的基本操作,,.,[例]如初始時(shí)B-樹為空樹，通過逐個(gè)向B-樹中插入新結(jié)點(diǎn)，可生成一棵B-樹。下圖說明了一棵5階B-樹的生長過程。,6 8 15 16,6 8,15,16 22,,,6 8 10,15,16 18 22 32,,,（a）插入6、8、15、16 （b）插入22 （c）插入10、18、32,6 8 10,15 20,16 18,22 32,6 8 10 12,15 20,16 18 19,22 32 40 50,6 8 10 12,15 20 40,16 18 19,22 32,50 56,,,,,,,,,,,（d）插入20 （e）插入12、19、40、50 （f）插入56,B-樹的基本操作,,.,6 8,9 15 20 40,16 18 19,22 26 32 36,50 52 55 56,10 12,,,,,,6 8,9 15,16 18 19,22 26,50 52 55 56,10 12,36 38,20,32 40,,,,,,,,,（g）插入9、26、36、52、55 （h）插入38,.,B-樹的基本操作,B-樹的刪除運(yùn)算,在B-樹上刪除一個(gè)關(guān)鍵字，首先找到該關(guān)鍵字所在結(jié)點(diǎn)及其在結(jié)點(diǎn)中的位置?？煞譃閮煞N情況： （1）被刪除結(jié)點(diǎn)ki在最下層的非終端結(jié)點(diǎn)（即葉子結(jié)點(diǎn)的上一層），則刪除ki及它右邊的指針pi。 刪除后若結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目不少于?m/2?-1，刪除完成，否則進(jìn)行“合并”結(jié)點(diǎn)的操作。 （2）若刪結(jié)點(diǎn)ki是最下層的非終端結(jié)點(diǎn)以上某層的結(jié)點(diǎn)，根據(jù)B-樹的特性可知，可以用ki右邊指針pi所指子樹中最小關(guān)鍵字y代替ki，然后在相應(yīng)的結(jié)點(diǎn)中刪除y，或用ki左邊指針pi-1所指子樹中最大關(guān)鍵字x代替ki，然后在相應(yīng)的結(jié)點(diǎn)中刪除x。,,.,[例] :刪除圖所示3階B-樹中的關(guān)鍵字50，可以用它右邊指針?biāo)缸訕渲凶钚￡P(guān)鍵字60代替50，爾后轉(zhuǎn)化為刪除葉子上面一層的結(jié)點(diǎn)中的60，刪除后得到的B-樹如圖所示。,.,90 115,,,,8,,,,,40,,28,,,,,,,150 200,,,,,,,85 120,50,60 80,,,,,,,,,,,,,,90 115,,,,8,,,,,40,,28,,,,,,,150 200,,,,,,,85 120,60,,,,,,,,,,,80,,3階B-樹中刪除50以60代替50,.,刪除B-樹葉子上面一層結(jié)點(diǎn)中的關(guān)鍵字的方法，分三種情形：,1）被刪關(guān)鍵字所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于?m/2?，則只需要從該結(jié)點(diǎn)中刪去關(guān)鍵字ki和相應(yīng)的指針pi，樹的其它部分不變。,例：,刪除60與115,.,2）被刪關(guān)鍵字所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于?m/2?-1，而與該結(jié)點(diǎn)相鄰的右兄弟結(jié)點(diǎn)（或左兄弟結(jié)點(diǎn)）中的關(guān)鍵字?jǐn)?shù)目大于?m/2?-1，則需要將其右兄弟的最小關(guān)鍵字（或其左兄弟的最大關(guān)鍵字）移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點(diǎn)中。例如從圖中刪除關(guān)鍵字90，結(jié)果如圖所示。,.,3）被刪關(guān)鍵字所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于?m/2?-1，則第（2）種情況中采用的移動(dòng)方法將不奏效，此時(shí)須將被刪關(guān)鍵字所有結(jié)點(diǎn)與其左或右兄弟合并。 不妨設(shè)該結(jié)點(diǎn)有右兄弟，但其右兄弟地址由雙親結(jié)點(diǎn)指針pi所指，則在刪除關(guān)鍵字之后，它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針加上雙親結(jié)點(diǎn)中的關(guān)鍵字ki一起合并到pi所指兄弟結(jié)點(diǎn)中（若沒有右兄弟，則合并至左兄弟結(jié)點(diǎn)中）。,.,[例]刪去關(guān)鍵字120，則應(yīng)刪去120所在結(jié)點(diǎn)，并將雙親結(jié)點(diǎn)中的150與200合并成一個(gè)結(jié)點(diǎn)，刪除后的樹如圖所示。如這一操作使雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目小于?m/2?-1，則依同樣方法進(jìn)行調(diào)整，最壞的情況下，合并操作會向上傳播至根，當(dāng)根中只有一個(gè)關(guān)鍵字時(shí)，合并操作將會使根結(jié)點(diǎn)及其兩個(gè)孩子合并成一個(gè)新的根，從而使整棵樹的高度減少一層。,.,[例]刪除關(guān)鍵字8 關(guān)鍵字所在結(jié)點(diǎn)無左兄弟，只檢查其右兄弟，然而右兄弟關(guān)鍵字?jǐn)?shù)目等于?m/2?-1，此時(shí)應(yīng)檢查其雙親結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目是否大于等于?m/2?-1，但此處其雙親結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目等于?m/2?-1，從而進(jìn)一步檢查雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目是否均等于?m/2?-1，這里關(guān)鍵字28所在的結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目正好等于?m/2?-1，因此將28和40結(jié)合成一個(gè)結(jié)點(diǎn)，50和85結(jié)合成一個(gè)結(jié)點(diǎn)，使得樹變矮，刪除結(jié)點(diǎn)8后的結(jié)果如圖所示。,