數據結構與算法：B-樹和B+樹

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

一B-樹的定義B-樹是一種平衡的多路查找樹。一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：

1．樹中每個結點至多有m棵子樹，m-1個關鍵字；

2．若根結點不是葉子結點，則至少有兩棵子樹；

3．除根之外的所有非終端結點至少有棵子樹，至少有-1個關鍵字；4．所有的非終端結點中包含下列信息數據：

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

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

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

二、圖形表示圖1 一棵4階的B-樹tabcfegdh135111243781181271391993475364FFFFFFFFFFFF結點中關鍵字個數為1<=n<=3

子樹數量范圍為2<=k<=49.5.1B-樹

從根結點出發(fā)，沿指針搜索結點和在結點內進行順序（或折半）查找兩個過程交叉進行。三、查找

若查找成功，則返回指向被查關鍵字所在結點的指針和關鍵字在結點中的位置；若查找不成功，則返回插入位置。9.5.1B-樹

#define m 3 //B-樹的階，暫設為3typedefstructBTNode{ int keynum//結點中關鍵字個數，即結點的大小

structBTNode*parent;//指向雙親結點

KeyType key[m+1];//關鍵字向量，0號單元未用

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

}BTNode,*BTree;B-樹結構體B-樹查詢結構體typedefstruct{ BTNode *pt; //指向找到的結點

int i; //1..m，在結點中的關鍵字序號

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

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

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

9.5.1B-樹

四、B-樹的查找

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

四、B-樹的查找查找分析這就是說，在含有N個關鍵字的B-樹上進行查找時，從根結點到關鍵字所在結點的路徑上涉及的結點數不超過9.5.1B-樹

四、B-樹的查找四、B-樹的插入（重點和考點）1．算法思想：由于B-樹結點中的關鍵字個數必須

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

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

9.5.1B-樹

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

3．例子例如，圖2所示為3階B-樹（圖中略去F結點，即葉子結點），假設需一次插入關鍵字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-樹中進行插入（省略葉子結點）五、B-樹的插入

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

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

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

-1，則一次類推作相應處理。

六、B-樹的刪除bta45b24c312

d37f50h100g6170e53902．例子

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

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

六、B-樹的刪除bt45ab24c3d37

h100g6170e90(c)

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

六、B-樹的刪除

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

六、B-樹的刪除

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

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

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