1 .B-樹定義

B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。

定義：一棵m 階的B-樹，或者為空樹，或?yàn)闈M足下列特性的m 叉樹：
⑴樹中每個(gè)結(jié)點(diǎn)至多有m 棵子樹；
⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；

⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有[m/2] 棵子樹；
⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：

（n，A0，K1，A1，K2，…，Kn，An）
其中：Ki（i=1,2,…,n）為關(guān)鍵碼，且Ki

Ai 為指向子樹根結(jié)點(diǎn)的指針(i=0,1,…,n)，且指針Ai-1 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki (i=1,2,…,n)，An 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn.

n 為關(guān)鍵碼的個(gè)數(shù)。
⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。

即所有葉節(jié)點(diǎn)具有相同的深度，等于樹高度。

如一棵四階B-樹，其深度為4.

B-樹的查找類似二叉排序樹的查找，所不同的是B-樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵碼的有序表，在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在有序表中查找，若找到，則查找成功；否則，到按照對應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對應(yīng)的關(guān)鍵碼。

在上圖的B-樹上查找關(guān)鍵字47的過程如下：

1）首先從更開始，根據(jù)根節(jié)點(diǎn)指針找到 *節(jié)點(diǎn)，因?yàn)?*a 節(jié)點(diǎn)中只有一個(gè)關(guān)鍵字，且給定值47 > 關(guān)鍵字35，則若存在必在指針A1所指的子樹內(nèi)。

2）順指針找到 *c節(jié)點(diǎn)，該節(jié)點(diǎn)有兩個(gè)關(guān)鍵字（43和 78），而43 < 47 < 78,若存在比在指針A1所指的子樹中。

3）同樣，順指針找到 *g節(jié)點(diǎn)，在該節(jié)點(diǎn)找到關(guān)鍵字47,查找成功。

2. 查找算法

復(fù)制代碼 代碼如下:

typedef int KeyType ;
#define m 5 /*B 樹的階，暫設(shè)為5*/
typedef struct Node{
int keynum; /* 結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)，即結(jié)點(diǎn)的大小*/
struct Node *parent; /*指向雙親結(jié)點(diǎn)*/
KeyType key[m+1]; /*關(guān)鍵碼向量，0 號單元未用*/
struct Node *ptr[m+1]; /*子樹指針向量*/
Record *recptr[m+1]; /*記錄指針向量*/
}NodeType; /*B 樹結(jié)點(diǎn)類型*/

typedef struct{
NodeType *pt; /*指向找到的結(jié)點(diǎn)*/
int i; /*在結(jié)點(diǎn)中的關(guān)鍵碼序號，結(jié)點(diǎn)序號區(qū)間[1…m]*/
int tag; /* 1:查找成功，0:查找失敗*/
}Result; /*B 樹的查找結(jié)果類型*/

Result SearchBTree(NodeType *t,KeyType kx)
{
/*在m 階B 樹t 上查找關(guān)鍵碼kx，反回(pt,i,tag)。若查找成功，則特征值tag=1，*/
/*指針pt 所指結(jié)點(diǎn)中第i 個(gè)關(guān)鍵碼等于kx；否則，特征值tag=0,等于kx 的關(guān)鍵碼記錄*/
/*應(yīng)插入在指針pt 所指結(jié)點(diǎn)中第i 個(gè)和第i+1 個(gè)關(guān)鍵碼之間*/
p=t;q=NULL;found=FALSE;i=0; /*初始化，p 指向待查結(jié)點(diǎn)，q 指向p 的雙親*/
while(p&&!found)
{ n=p->keynum;i=Search(p,kx); /*在p-->key[1…keynum]中查找*/
if(i>0&&p->key[i]= =kx) found=TRUE; /*找到*/
else {q=p;p=p->ptr[i];}
}
if(found) return (p,i,1); /*查找成功*/
else return (q,i,0); /*查找不成功，反回kx 的插入位置信息*/
}

從查找算法中可以看出， 在B- 樹中進(jìn)行查找包含兩種基本操作:

( 1) 在B- 樹中查找結(jié)點(diǎn)；

( 2) 在結(jié)點(diǎn)中查找關(guān)鍵字。

由于B- 樹通常存儲在磁盤上， 則前一查找操作是在磁盤上進(jìn)行的， 而后一查找操作是在內(nèi)存中進(jìn)行的， 即在磁盤上找到指針p 所指結(jié)點(diǎn)后， 先將結(jié)點(diǎn)中的信息讀入內(nèi)存， 然后再利用順序查找或折半查找查詢等于K 的關(guān)鍵字。顯然， 在磁盤上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找的時(shí)間消耗多得多.

因此， 在磁盤上進(jìn)行查找的次數(shù)、即待查找關(guān)鍵字所在結(jié)點(diǎn)在B- 樹上的層次樹， 是決定B樹查找效率的首要因素

那么，對含有n 個(gè)關(guān)鍵碼的m 階B-樹，最壞情況下達(dá)到多深呢？可按二叉平衡樹進(jìn)行類似分析。首先，討論m 階B-數(shù)各層上的最少結(jié)點(diǎn)數(shù)。

由B樹定義：B樹包含n個(gè)關(guān)鍵字。因此有n+1個(gè)樹葉都在第J+1 層。

1）第一層為根，至少一個(gè)結(jié)點(diǎn)，根至少有兩個(gè)孩子，因此在第二層至少有兩個(gè)結(jié)點(diǎn)。

2）除根和樹葉外，其它結(jié)點(diǎn)至少有[m/2]個(gè)孩子,因此第三層至少有2*[m/2]個(gè)結(jié)點(diǎn),在第四層至少有2*[m/2]2 個(gè)結(jié)點(diǎn)…

3）那么在第J+1層至少有2*[m/2]J-1個(gè)結(jié)點(diǎn),而J+1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn),于是葉子結(jié)點(diǎn)的個(gè)數(shù)n+1。有：

也就是說在n個(gè)關(guān)鍵字的B樹查找，從根節(jié)點(diǎn)到關(guān)鍵字所在的節(jié)點(diǎn)所涉及的節(jié)點(diǎn)數(shù)不超過：

3.B-樹的插入

B-樹的生成也是從空樹起，逐個(gè)插入關(guān)鍵字而得。但由于B-樹結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須≥ceil(m／2)-1，因此，每次插入一個(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)的“分裂”，

如圖（a） 為3階的B-樹(圖中略去F結(jié)點(diǎn)(即葉子結(jié)點(diǎn)))，假設(shè)需依次插入關(guān)鍵字30，26，85。

1) 首先通過查找確定插入的位置。由根*a 起進(jìn)行查找，確定30應(yīng)插入的在*d 節(jié)點(diǎn)中。由于*d 中關(guān)鍵字?jǐn)?shù)目不超過2（即m-1），故第一個(gè)關(guān)鍵字插入完成：如（b）

2) 同樣，通過查找確定關(guān)鍵字26亦應(yīng)插入 *d. 由于*d節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目超過2，此時(shí)需要將 *d分裂成兩個(gè)節(jié)點(diǎn)，關(guān)鍵字26及其前、后兩個(gè)指針仍保留在 *d 節(jié)點(diǎn)中，而關(guān)鍵字37 及其前、后兩個(gè)指針存儲到新的產(chǎn)生的節(jié)點(diǎn) *d` 中。同時(shí)將關(guān)鍵字30 和指示節(jié)點(diǎn) *d `的指針插入到其雙親的節(jié)點(diǎn)中。由于 *b節(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目沒有超過2，則插入完成.如（c）(d)

3) (e) -(g) 為插入85后;

插入算法：

復(fù)制代碼 代碼如下: