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

我們看看它的結點的結構，如下圖所示:

每個結點存放著關鍵字和指向子結點的指針，很容易看出指針比關鍵碼多一個。

由B樹的定義我們可以看出它的一些特點：
1.樹高平衡，所有葉結點在同一層；
2.關鍵字沒有重復，按升序排序，父結點的關鍵碼是子結點的分界；
3.B樹把值接近的相關記錄放在同一磁盤頁中，從而利用了訪問局部性原理；
4.B樹保證一定比例的結點是滿的，能改進空間利用率。

B樹結點的大小怎么確定呢？為了最小化磁盤操作，通常把結點大小設為一個磁盤頁的大小。一般樹的高度不會超過3層，也就是說，查找一個關鍵碼只需要3次磁盤操作就可以了。
在實現(xiàn)的時候，我是參照了《算法導論》的內容，先假定：
1.B樹的根結點始終在主存中，不需要讀磁盤操作；但是，根結點改變后要進行一次寫磁盤操作；
2.任何結點被當做參數(shù)傳遞的時候，要讀磁盤。

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

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