數(shù)據(jù)結(jié)構(gòu)與算法：B-樹和B+樹

9.5B-樹和B+樹1、B-樹2B+樹9.5.1B-樹

一B-樹的定義B-樹是一種平衡的多路查找樹。一棵m階的B-樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹：

1．樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹，m-1個(gè)關(guān)鍵字；

2．若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；

3．除根之外的所有非終端結(jié)點(diǎn)至少有棵子樹，至少有-1個(gè)關(guān)鍵字；4．所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)：

(n,A0,K1,A1,K2,A2,…,Kn,An)其中：Ki(i=1,…,n)為關(guān)鍵字，且Ki<Ki+1(i=1,…,n-1)；

Ai(i=1,…,n)為指向子樹根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki(i=1,…,n)，Ai所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Ki，n為關(guān)鍵字的個(gè)數(shù)（或n＋1為子樹個(gè)數(shù)）。一、B-樹的定義9.5.1B-樹

5．所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。一、B-樹的定義9.5.1B-樹

二、圖形表示圖1 一棵4階的B-樹tabcfegdh135111243781181271391993475364FFFFFFFFFFFF結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)為1<=n<=3

子樹數(shù)量范圍為2<=k<=49.5.1B-樹

從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找兩個(gè)過程交叉進(jìn)行。三、查找

若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；若查找不成功，則返回插入位置。9.5.1B-樹

#define m 3 //B-樹的階，暫設(shè)為3typedefstructBTNode{ int keynum//結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，即結(jié)點(diǎn)的大小

structBTNode*parent;//指向雙親結(jié)點(diǎn)

KeyType key[m+1];//關(guān)鍵字向量，0號(hào)單元未用

structBTNode*ptr[m+1]; //子樹指針向量//記錄指針向量，0號(hào)單元未用

}BTNode,*BTree;B-樹結(jié)構(gòu)體B-樹查詢結(jié)構(gòu)體typedefstruct{ BTNode *pt; //指向找到的結(jié)點(diǎn)

int i; //1..m，在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)

int tag; //1:查找成功，0:查找失敗

}Result; //B-樹的查找結(jié)果類型三、B-樹的查找算法代碼9.5.1B-樹

查找分析從上述算法可見，在B-樹上進(jìn)行查找包含兩種基本操作：a.在B-樹中找結(jié)點(diǎn)（操作在磁盤上進(jìn)行）；b.在結(jié)點(diǎn)中找關(guān)鍵字（操作在內(nèi)存中進(jìn)行）。顯然，在磁盤上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)時(shí)間多得多，因此，在磁盤上進(jìn)行查找的次數(shù)、即待查關(guān)鍵字所在結(jié)點(diǎn)在B-樹上的層次數(shù)，是決定B-樹查找效率的首要因素。

9.5.1B-樹

四、B-樹的查找

根據(jù)B-樹的定義，第一層至少有1個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn)；棵子樹，則第三層至少有2()個(gè)結(jié)點(diǎn)；……；依次類推，第l＋1層至少有)l-1由于除根之外的每個(gè)非終端結(jié)點(diǎn)至少有2(個(gè)結(jié)點(diǎn)。而l＋1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。若m階B-樹中具有N個(gè)關(guān)鍵字，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為N＋1，由此有：推得：3．查找分析9.5.1B-樹

四、B-樹的查找查找分析這就是說，在含有N個(gè)關(guān)鍵字的B-樹上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過9.5.1B-樹

四、B-樹的查找四、B-樹的插入（重點(diǎn)和考點(diǎn)）1．算法思想：由于B-樹結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須

。因此，每次插入一個(gè)關(guān)鍵字不是在樹中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過m-1，則插入完成，否則要產(chǎn)生結(jié)點(diǎn)的“分裂”。9.5.1B-樹

五、B-樹的插入2一般情況下，結(jié)點(diǎn)可如下實(shí)現(xiàn)“分裂”：假設(shè)p結(jié)點(diǎn)中已有m-1個(gè)關(guān)鍵字，當(dāng)插入一個(gè)關(guān)鍵字之后，結(jié)點(diǎn)中含有信息為：m,A0,(K1,A1),…,(Km,Am)且其中Ki<Ki+1，1≤i<m，此時(shí)可將p結(jié)點(diǎn)分裂為p和p’兩個(gè)結(jié)點(diǎn)，其中p結(jié)點(diǎn)中含有信息為：

9.5.1B-樹

五、B-樹的插入p’結(jié)點(diǎn)中含有信息：而關(guān)鍵字和其右指針一起上升插入到p的雙親結(jié)點(diǎn)中，該右指針指向p’。9.5.1B-樹

3．例子例如，圖2所示為3階B-樹（圖中略去F結(jié)點(diǎn)，即葉子結(jié)點(diǎn)），假設(shè)需一次插入關(guān)鍵字30，26，85和7。(a) bta45b24c312d37f50h100g6170e5390圖2一棵2-3樹五、B-樹的插入bta45b24c312df50h100g6170e53903037(b)五、B-樹的插入bta45b24c312df50h100g6170e5390263037(c)五、B-樹的插入bta45b2430c312df50h100g6170e53903726d’(d)bta45b2430c312df50h100g617085e53903726d’(e)五、B-樹的插入(f)bta45b2430c312df50h100g61e5370903726d’85g’五、B-樹的插入(g)bta4570b2430c312df50h100g61e533726d’85g’e’90五、B-樹的插入(h)bta4570b72430c3df50h100g61e533726d’85g’e’9012c’五、B-樹的插入bta244570b7c3df50h100g61e5326d’85g’e’9012c’30b’37(i)五、B-樹的插入(j)bta70b7c3df50h100g61e5326d’85g’e’9012c’30b’ma’452437(a)一棵2-3樹；(b)插入30之后；(c)、(d)插入26之后；

(e)~(g) 插入85之后；(h)~(j)插入7之后；圖2 在B-樹中進(jìn)行插入（省略葉子結(jié)點(diǎn)）五、B-樹的插入

五、B-樹的刪除1．算法思想：在B-樹中刪除一個(gè)關(guān)鍵字，則首先應(yīng)找到該關(guān)鍵字所在結(jié)點(diǎn)，并從中刪除之。（1）若所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki，則以指針Ai所指子樹中的最小關(guān)鍵字Y替代Ki，然后在相應(yīng)的結(jié)點(diǎn)中刪去Y。（2）若所刪關(guān)鍵字在最下層非終端結(jié)點(diǎn)中。有下列3種情況：a．被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于，則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵字Ki和相應(yīng)指針Ai，樹的其他部分不變。9.5.1B-樹

b．被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于-1，而與該結(jié)點(diǎn)相鄰的右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于-1，則需將其右兄弟結(jié)點(diǎn)中的最?。ɑ蜃笮值茏畲螅┑年P(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。

六、B-樹的刪除c．被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于-1。假設(shè)該結(jié)點(diǎn)有右兄弟，且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Ai所指，則在刪去關(guān)鍵字之后，它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針，加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki一起，合并到Ai所指兄弟結(jié)點(diǎn)中（若沒有右兄弟，則合并至左兄弟結(jié)點(diǎn)中）。如果因此使雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目小于

-1，則一次類推作相應(yīng)處理。

六、B-樹的刪除bta45b24c312

d37f50h100g6170e53902．例子

六、B-樹的刪除bta45b24c3d37f50h100g6170e5390(a)

六、B-樹的刪除bt45ab24c3d37f53h100g70e6190(b)

六、B-樹的刪除bt45ab24c3d37

h100g6170e90(c)

六、B-樹的刪除ec324h100g61704590bt(d)圖3 在B-樹中刪除關(guān)鍵字的情形

六、B-樹的刪除

說明：（1）從圖2(a)所示B-樹中刪去關(guān)鍵字12，刪除后的B-樹如圖3(a)所示。（2）從圖3(a)中刪去50，需將其右兄弟結(jié)點(diǎn)中的61上移至*e結(jié)點(diǎn)中，而將*e結(jié)點(diǎn)中的53移至*f，從而使*f和*g中關(guān)鍵字?jǐn)?shù)目均不小于－1，而雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不變，如圖3(b)所示。

六、B-樹的刪除

說明：（3）從圖3(b)所示B-樹中刪去53，則應(yīng)刪去*f結(jié)點(diǎn)，并將*f中的剩余信息（指針“空”）和雙親*e結(jié)點(diǎn)中的61一起合并到右兄弟結(jié)點(diǎn)*g中，刪除后的樹如圖3(c)所示。（4）在圖3(c)的B-樹中刪去關(guān)鍵字37之后，雙親b結(jié)點(diǎn)中剩余信息（“指針c”）應(yīng)和其雙親*a結(jié)點(diǎn)中關(guān)鍵字45一起合并至右兄弟結(jié)點(diǎn)*e中，刪除后的B-樹如圖3(d)所示。

六、B-樹的刪除9.5.2B＋樹1、定義

B＋樹是應(yīng)文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B＋樹和m階的B-樹的差異在于：有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字。3.所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含其子樹（根結(jié)點(diǎn)）中的最大（或最?。╆P(guān)鍵字。2.所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。通常在B＋樹上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。9.5.