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

B樹(shù)結(jié)點(diǎn)的大小怎么確定呢？為了最小化磁盤操作，通常把結(jié)點(diǎn)大小設(shè)為一個(gè)磁盤頁(yè)的大小。一般樹(shù)的高度不會(huì)超過(guò)3層，也就是說(shuō)，查找一個(gè)關(guān)鍵碼只需要3次磁盤操作就可以了。
在實(shí)現(xiàn)的時(shí)候，我是參照了《算法導(dǎo)論》的內(nèi)容，先假定：
1.B樹(shù)的根結(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)里面了，下面是定義樹(shù)的結(jié)構(gòu)，文件名為btrees.h，內(nèi)容如下：

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

最新評(píng)論