快捷導(dǎo)航

c語言B樹深入理解

更新時(shí)間：2012年11月26日 11:02:43 投稿：whsnow

B樹是為磁盤或其他直接存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹，本文將詳細(xì)介紹c語言B樹,需要的朋友可以參考下

B樹是為磁盤或其他直接存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹。如下圖所示。每一個(gè)結(jié)點(diǎn)箭頭指向的我們稱為入度，指出去的稱為出度。樹結(jié)構(gòu)的結(jié)點(diǎn)入度都是1，不然就變成圖了，所以我們一般說樹的度就是指樹結(jié)點(diǎn)的出度，也就是一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)。有了度的概念我們就簡單定義一下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í)沒有子結(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)鍵字沒有重復(fù)，按升序排序，父結(jié)點(diǎn)的關(guān)鍵碼是子結(jié)點(diǎn)的分界；
3.B樹把值接近的相關(guān)記錄放在同一磁盤頁中，從而利用了訪問局部性原理；
4.B樹保證一定比例的結(jié)點(diǎn)是滿的，能改進(jìn)空間利用率。

B樹結(jié)點(diǎn)的大小怎么確定呢？為了最小化磁盤操作，通常把結(jié)點(diǎn)大小設(shè)為一個(gè)磁盤頁的大小。一般樹的高度不會(huì)超過3層，也就是說，查找一個(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í)還做了簡化，每個(gè)結(jié)點(diǎn)除了包含關(guān)鍵碼和指針外，還應(yīng)該有該關(guān)鍵碼所對(duì)應(yīng)記錄所在文件的信息的，比如文件偏移量，要不然怎么找到這條記錄呢。在實(shí)現(xiàn)的時(shí)候這個(gè)附加數(shù)據(jù)就沒有放在結(jié)點(diǎn)里面了，下面是定義樹的結(jié)構(gòu)，文件名為btrees.h，內(nèi)容如下：

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

/* 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)中位置 */
};

他博客里面已經(jīng)實(shí)現(xiàn)了，只是在定義B樹的時(shí)候指針數(shù)和關(guān)鍵碼數(shù)成一樣了，我于是自己重寫了一下。
[code]
void btreeSplitChild( struct btnode *parent, int pos, struct btnode *child){
struct btnode *child2;
int i;
child2 = allocateNode(child2);
child2->isleaf = child->isleaf;
//設(shè)置節(jié)點(diǎn)數(shù)
child2->keyNum = M-1;
//復(fù)制數(shù)據(jù)
for (i=0; i<M-1; i++)
child2->k[i] = child->k[i+M];
//如果不是葉節(jié)點(diǎn)，復(fù)制指針
if (!child->isleaf)
for (i=0; i<M; i++)
child2->p[i] = child->p[i+M];
child->keyNum = M-1;
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;
}