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

.,B-樹,前面討論的查找算法都是在內(nèi)存中進(jìn)行的，它們適用于較小的文件，而對(duì)較大的、存放在外存儲(chǔ)器上的文件就不合適了。 1972年R.Bayer和E.M.McCreight提出了一種稱為B-樹的多路平衡查找樹，它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表。,一. B-樹的定義,B-樹是一種平衡的多路查找樹，在文件系統(tǒng)中，成為索引文件的一種有效結(jié)構(gòu)，得到廣泛應(yīng)用。,.,一棵m階（m3）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（1in）為關(guān)鍵字，且ki<ki+1（1in）； pj（0jn）為指向子樹根結(jié)點(diǎn)的指針,且pj（0j<n）所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于kj+1，pn所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于kn，n（m/2-1nm-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)原來(lái)非滿（結(jié)點(diǎn)中原有關(guān)鍵字總數(shù)小于m-1），則插入k并不會(huì)破壞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)鍵字keym/2為劃分點(diǎn)，將該結(jié)點(diǎn)（即p）（m，p0，k1，p1，km，pm）分裂為兩個(gè)結(jié)點(diǎn)左邊:（m/2-1，p0，k1，km/2-1，pm/2-1）右邊:（m-m/2，pm/2，km/2+1，km，pm）同時(shí)把中間關(guān)鍵字km/2插入到雙親結(jié)點(diǎn)中。于是雙親結(jié)點(diǎn)中指向被插入結(jié)點(diǎn)的指針pre改成pre、km/2、pre三部分。指針pre指向分裂后的左邊結(jié)點(diǎn)，指針pre指向分裂后的右邊結(jié)點(diǎn)。由于將km/2插入雙親時(shí)，雙親結(jié)點(diǎn)亦可能原本為滿，若如此，則需對(duì)雙親做分裂操作。分裂過(guò)程的例子如圖所示。,B-樹的基本操作,.,2 80 220,4 90 120 140 160,p,3 80 120 220 ,2 90 100,2 140 160,pre,pre,pre,km/2,插入100以前,插入100以后,B-樹的基本操作,.,例如初始時(shí)B-樹為空樹，通過(guò)逐個(gè)向B-樹中插入新結(jié)點(diǎn)，可生成一棵B-樹。下圖說(shuō)明了一棵5階B-樹的生長(zhǎng)過(guò)程。,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)中（若沒(méi)有右兄弟，則合并至左兄弟結(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)整，最壞的情況下，合并操作會(huì)向上傳播至根，當(dāng)根中只有一個(gè)關(guān)鍵字時(shí)，合并操作將會(huì)使根結(jié)點(diǎn)及其兩個(gè)孩子合并成一個(gè)新的根，從而使整棵樹的高度減少一層。,.,例刪除關(guān)鍵字8關(guān)鍵字所在結(jié)點(diǎn)無(wú)左兄弟，只檢查其右兄弟，然而右兄弟關(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é)果如圖所示。,