B樹是為磁盤或其他直接存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹。如下圖所示。每一個(gè)結(jié)點(diǎn)箭頭指向的我們稱為入度，指出去的稱為出度。樹結(jié)構(gòu)的結(jié)點(diǎn)入度都是1，不然就變成圖了，所以我們一般說(shuō)樹的度就是指樹結(jié)點(diǎn)的出度，也就是一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)。有了度的概念我們就簡(jiǎn)單定義一下B樹(假設(shè)一棵樹的最小度數(shù)為M)：
1.每個(gè)結(jié)點(diǎn)至少有M-1個(gè)關(guān)鍵碼，至多有2M-1個(gè)關(guān)鍵碼；
2.除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)至少有M個(gè)子結(jié)點(diǎn)，至多有2M個(gè)子結(jié)點(diǎn)；
3.根結(jié)點(diǎn)至少有2個(gè)子結(jié)點(diǎn)，唯一例外是只有根結(jié)點(diǎn)的情況，此時(shí)沒(méi)有子結(jié)點(diǎn)；
4.所有葉子結(jié)點(diǎn)在同一層。
我們看看它的結(jié)點(diǎn)的結(jié)構(gòu)，如下圖所示:
每個(gè)結(jié)點(diǎn)存放著關(guān)鍵字和指向子結(jié)點(diǎn)的指針，很容易看出指針比關(guān)鍵碼多一個(gè)。
由B樹的定義我們可以看出它的一些特點(diǎn)：
1.樹高平衡，所有葉結(jié)點(diǎn)在同一層；
2.關(guān)鍵字沒(méi)有重復(fù)，按升序排序，父結(jié)點(diǎn)的關(guān)鍵碼是子結(jié)點(diǎn)的分界；
3.B樹把值接近的相關(guān)記錄放在同一磁盤頁(yè)中，從而利用了訪問(wèn)局部性原理；
4.B樹保證一定比例的結(jié)點(diǎn)是滿的，能改進(jìn)空間利用率。
B樹結(jié)點(diǎn)的大小怎么確定呢？為了最小化磁盤操作，通常把結(jié)點(diǎn)大小設(shè)為一個(gè)磁盤頁(yè)的大小。一般樹的高度不會(huì)超過(guò)3層，也就是說(shuō)，查找一個(gè)關(guān)鍵碼只需要3次磁盤操作就可以了。
在實(shí)現(xiàn)的時(shí)候，我是參照了《算法導(dǎo)論》的內(nèi)容，先假定：
1.B樹的根結(jié)點(diǎn)始終在主存中，不需要讀磁盤操作；但是，根結(jié)點(diǎn)改變后要進(jìn)行一次寫磁盤操作；
2.任何結(jié)點(diǎn)被當(dāng)做參數(shù)傳遞的時(shí)候，要做一次讀磁盤。
在實(shí)現(xiàn)的時(shí)候其實(shí)還做了簡(jiǎn)化，每個(gè)結(jié)點(diǎn)除了包含關(guān)鍵碼和指針外，還應(yīng)該有該關(guān)鍵碼所對(duì)應(yīng)記錄所在文件的信息的，比如文件偏移量，要不然怎么找到這條記錄呢。在實(shí)現(xiàn)的時(shí)候這個(gè)附加數(shù)據(jù)就沒(méi)有放在結(jié)點(diǎn)里面了，下面是定義樹的結(jié)構(gòu)，文件名為btrees.h，內(nèi)容如下：
/* btrees.h */
# define M 2
/* B樹的最小度數(shù)M>=2
* 每個(gè)非根結(jié)點(diǎn)必須至少有M-1個(gè)關(guān)鍵字。每個(gè)非根結(jié)點(diǎn)至少有M個(gè)子女
* 每個(gè)結(jié)點(diǎn)可包含至多2M-1個(gè)關(guān)鍵字。所以一個(gè)內(nèi)結(jié)點(diǎn)至多可以有2M個(gè)子女
*/
typedef int bool ;
struct btnode{ /* B樹結(jié)點(diǎn) */
int keyNum; /* 節(jié)點(diǎn)中鍵的數(shù)目 */
int k[2*M-1]; /* 鍵 */
struct btnode * p[2*M]; /* 指向子樹的指針 */
bool isleaf;
};
struct searchResult{
struct btnode *ptr; /* 數(shù)據(jù)所在節(jié)點(diǎn)指針 */
int pos; /* 數(shù)據(jù)在節(jié)點(diǎn)中位置 */
};
?
B樹的插入都是在葉子結(jié)點(diǎn)進(jìn)行的，由于B樹的結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)是有限制的，最小度數(shù)為M的B樹的結(jié)點(diǎn)個(gè)數(shù)是從M-1到2M-1個(gè)。比如下圖是最小度數(shù)為2的B樹(又稱為2-3樹)，如下圖所示，它的結(jié)點(diǎn)的個(gè)數(shù)就是1-3個(gè)。
先定位到要插入的位置，如果葉子結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)還沒(méi)達(dá)到上限，比如插入32，就比較簡(jiǎn)單，直接插入就行；如果葉子結(jié)點(diǎn)的關(guān)鍵碼數(shù)到達(dá)了上限，就要分裂成2個(gè)子結(jié)點(diǎn)，把中間的關(guān)鍵碼往上放到父節(jié)點(diǎn)中。但有極端的情況，就是父結(jié)點(diǎn)也是滿的，就需要再次分裂，可能最后要把根結(jié)點(diǎn)也分裂了。但是這種算法不太好實(shí)現(xiàn)。
在《算法導(dǎo)論》中實(shí)現(xiàn)用的是另外一種思想，就是先分裂，在查找插入位置的過(guò)程中，如果發(fā)現(xiàn)有滿的結(jié)點(diǎn)，就先把它分裂了，這就保證了在最后葉結(jié)點(diǎn)上插入數(shù)據(jù)的時(shí)候，這個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)總是不滿的。下面我們看一個(gè)例子：
我們用逐個(gè)結(jié)點(diǎn)插入的方法創(chuàng)建一棵B樹，結(jié)點(diǎn)順序分別是{18, 31, 12, 10, 15, 48, 45, 47, 50, 52, 23, 30, 20}，我們看看具體過(guò)程：
1.創(chuàng)建一個(gè)空的B樹；
2.插入18，這時(shí)候是非滿的，如下所示：
3.同理插入31和12，都比較簡(jiǎn)單，如下所示：
4.插入10，這時(shí)候根結(jié)點(diǎn)是滿的，就要分裂，由于根結(jié)點(diǎn)比較特殊，沒(méi)有父結(jié)點(diǎn)，就要單獨(dú)處理，先生成一個(gè)空結(jié)點(diǎn)做為新的根結(jié)點(diǎn)，再進(jìn)行分裂，如下所示：
5.再插入15，48，45，由于非滿，直接插入，如下所示：
6.插入47，這次葉結(jié)點(diǎn)滿了，就要先分裂，再插入，如下所示：
其他都是同樣的道理，就不贅述了，下面是源碼，加入到btree.c中，最后寫了個(gè)main函數(shù)和一個(gè)廣度優(yōu)先顯示樹的方法，大家可以自己對(duì)比結(jié)果，代碼的實(shí)現(xiàn)參照了《算法導(dǎo)論》和博客
http://hi.baidu.com/kurt023/blog/item/4c368d8b51c59ed3fc1f10cc.html
他博客里面已經(jīng)實(shí)現(xiàn)了，只是在定義B樹的時(shí)候指針數(shù)和關(guān)鍵碼數(shù)成一樣了，我于是自己重寫了一下。
//函數(shù)目的：分裂存儲(chǔ)數(shù)達(dá)到最大的節(jié)點(diǎn)
void btreeSplitChild( struct btnode *parent, int pos, struct btnode *child){
struct btnode *child2;
int i;
//為新分裂出的節(jié)點(diǎn)分配空間
child2 = allocateNode(child2);
//與被分裂點(diǎn)同級(jí)
child2->isleaf = child->isleaf;
//設(shè)置節(jié)點(diǎn)數(shù)
child2->keyNum = M-1;
//復(fù)制數(shù)據(jù)
for (i=0; i
child2->k[i] = child->k[i+M];
//如果不是葉節(jié)點(diǎn)，復(fù)制指針
if (!child->isleaf)
for (i=0; i
child2->p[i] = child->p[i+M];
child->keyNum = M-1;
//將中間數(shù)作為索引插入到雙親節(jié)點(diǎn)中
//插入點(diǎn)后面的關(guān)鍵字和指針都往后移動(dòng)一個(gè)位置
for (i=parent->keyNum; i>pos; i--){
parent->k[i] = parent->k[i-1];
parent->p[i+1] = parent->p[i];
}
parent->k[pos] = child->k[M-1];
parent->keyNum++;
parent->p[pos+1] = child2;
}
/* 函數(shù)目的：向非滿的節(jié)點(diǎn)中插入一個(gè)數(shù)據(jù)
* 注意：插入前保證key在原來(lái)的B樹中不存在
*/
void btreeInsertNoneFull( struct btnode *ptr, int data){
int i;
struct btnode *child; //要插入結(jié)點(diǎn)的子結(jié)點(diǎn)
i = ptr->keyNum;
//如果是葉節(jié)點(diǎn)，直接插入數(shù)據(jù)
if (ptr->isleaf){
while ((i>0) && (data
k[i-1])){
ptr->k[i] = ptr->k[i-1];
i--;
}
//插入數(shù)據(jù)
ptr->k[i] = data;
ptr->keyNum++;
}
else { //不是葉節(jié)點(diǎn)，找到數(shù)據(jù)應(yīng)插入的子節(jié)點(diǎn)并插入
while ((i>0) && (datak[i-1]))
i--;
child = ptr->p[i];
if (child->keyNum == 2*M-1){
btreeSplitChild(ptr, i, child);
if (data > ptr->k[i])
i++;
}
child = ptr->p[i];
btreeInsertNoneFull(child, data); //在子樹中遞歸
}
}
/* 插入一個(gè)結(jié)點(diǎn) */
struct btnode * btreeInsert( struct btnode *root, int data){
struct btnode * new ;
/* 檢查是否根節(jié)點(diǎn)已滿，如果已滿，分裂并生成新的根節(jié)點(diǎn) */
if (root->keyNum == 2*M-1){
new = allocateNode( new );
new ->isleaf = 0;
new ->keyNum = 0;
new ->p[0] = root;
btreeSplitChild( new , 0, root);
btreeInsertNoneFull( new , data);
return new ;
}
else { //還沒(méi)到最大數(shù)據(jù)數(shù)，直接插入
btreeInsertNoneFull(root, data);
return root;
}
}
//函數(shù)目的：廣度優(yōu)先顯示樹
void btreeDisplay( struct btnode *root){
int i, queueNum=0;
int j;
struct btnode *queue[20];
struct btnode *current;
//加入隊(duì)列
queue[queueNum] = root;
queueNum++;
while (queueNum>0){
//出隊(duì)
current = queue[0];
queueNum--;
//移出第一個(gè)元素后后面的元素往前移動(dòng)一個(gè)位置
for (i=0; i queue[i] = queue[i+1];
//顯示節(jié)點(diǎn)
j = current->keyNum;
printf ( "[ " );
for (i=0; i printf ( "%d " , current->k[i]);
}
printf ( "] " );
//子節(jié)點(diǎn)入隊(duì)
if (current!=NULL && current->isleaf!=1){
for (i=0; ikeyNum); i++){
queue[queueNum] = current->p[i];
queueNum++;
}
}
}
printf ( "/n" );
}
int main()
{
struct btnode *root;
int a[13] = {18, 31, 12, 10, 15, 48, 45, 47, 50, 52, 23, 30, 20};
int i;
root = btreeCreate(root);
for (i=0; i root = btreeInsert(root, a[i]);
btreeDisplay(root);
}
return 0;
}?
?
?
?
運(yùn)行結(jié)果：
同樣一批關(guān)鍵碼用不同算法生成的B樹可能是不同的，比如4個(gè)關(guān)鍵碼的結(jié)點(diǎn)[1，2，3，4]分裂的時(shí)候，把2或3放上去都可以；同樣的算法插入順序不同也可能不同。
附件中是源碼，在Linux下編譯通過(guò)。
以上就是深入理解C語(yǔ)言B樹原理的全部?jī)?nèi)容，感謝大家的閱讀，更多內(nèi)容請(qǐng)關(guān)注武林技術(shù)頻道網(wǎng)站。
