B樹是為磁盤或其他直接存儲設(shè)備設(shè)計的一種平衡查找樹。如下圖所示。每一個結(jié)點(diǎn)箭頭指向的我們稱為入度，指出去的稱為出度。樹結(jié)構(gòu)的結(jié)點(diǎn)入度都是1，不然就變成圖了，所以我們一般說樹的度就是指樹結(jié)點(diǎn)的出度，也就是一個結(jié)點(diǎn)的子結(jié)點(diǎn)個數(shù)。有了度的概念我們就簡單定義一下B樹(假設(shè)一棵樹的最小度數(shù)為M)：
1.每個結(jié)點(diǎn)至少有M-1個關(guān)鍵碼，至多有2M-1個關(guān)鍵碼；
2.除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，每個結(jié)點(diǎn)至少有M個子結(jié)點(diǎn)，至多有2M個子結(jié)點(diǎn)；
3.根結(jié)點(diǎn)至少有2個子結(jié)點(diǎn)，唯一例外是只有根結(jié)點(diǎn)的情況，此時沒有子結(jié)點(diǎn)；
4.所有葉子結(jié)點(diǎn)在同一層。

我們看看它的結(jié)點(diǎn)的結(jié)構(gòu)，如下圖所示:

每個結(jié)點(diǎn)存放著關(guān)鍵字和指向子結(jié)點(diǎn)的指針，很容易看出指針比關(guān)鍵碼多一個。

由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è)為一個磁盤頁的大小。一般樹的高度不會超過3層，也就是說，查找一個關(guān)鍵碼只需要3次磁盤操作就可以了。
在實(shí)現(xiàn)的時候，我是參照了《算法導(dǎo)論》的內(nèi)容，先假定：
1.B樹的根結(jié)點(diǎn)始終在主存中，不需要讀磁盤操作；但是，根結(jié)點(diǎn)改變后要進(jìn)行一次寫磁盤操作；
2.任何結(jié)點(diǎn)被當(dāng)做參數(shù)傳遞的時候，要讀磁盤。

在實(shí)現(xiàn)的時候其實(shí)還做了簡化，每個結(jié)點(diǎn)除了包含關(guān)鍵碼和指針外，還應(yīng)該有該關(guān)鍵碼所對應(yīng)記錄所在文件的信息的，比如文件偏移量，要不然怎么找到這條記錄呢。在實(shí)現(xiàn)的時候這個附加數(shù)據(jù)就沒有放在結(jié)點(diǎn)里面了，下面是定義樹的結(jié)構(gòu)，文件名為btrees.h，內(nèi)容如下：

他博客里面已經(jīng)實(shí)現(xiàn)了，只是在定義B樹的時候指針數(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;
}

最新評論