B樹是為磁盤或其他直接存儲設備設計的一種平衡查找樹。如下圖所示。每一個結點箭頭指向的我們稱為入度，指出去的稱為出度。樹結構的結點入度都是1，不然就變成圖了，所以我們一般說樹的度就是指樹結點的出度，也就是一個結點的子結點個數。有了度的概念我們就簡單定義一下B樹(假設一棵樹的最小度數為M)：
1.每個結點至少有M-1個關鍵碼，至多有2M-1個關鍵碼；
2.除根結點和葉子結點外，每個結點至少有M個子結點，至多有2M個子結點；
3.根結點至少有2個子結點，唯一例外是只有根結點的情況，此時沒有子結點；
4.所有葉子結點在同一層。
我們看看它的結點的結構，如下圖所示:
每個結點存放著關鍵字和指向子結點的指針，很容易看出指針比關鍵碼多一個。
由B樹的定義我們可以看出它的一些特點：
1.樹高平衡，所有葉結點在同一層；
2.關鍵字沒有重復，按升序排序，父結點的關鍵碼是子結點的分界；
3.B樹把值接近的相關記錄放在同一磁盤頁中，從而利用了訪問局部性原理；
4.B樹保證一定比例的結點是滿的，能改進空間利用率。
B樹結點的大小怎麼確定呢？為了最小化磁盤操作，通常把結點大小設為一個磁盤頁的大小。一般樹的高度不會超過3層，也就是說，查找一個關鍵碼只需要3次磁盤操作就可以了。
在實現的時候，我是參照了《算法導論》的內容，先假定：
1.B樹的根結點始終在主存中，不需要讀磁盤操作；但是，根結點改變後要進行一次寫磁盤操作；
2.任何結點被當做參數傳遞的時候，要做一次讀磁盤。
在實現的時候其實還做了簡化，每個結點除了包含關鍵碼和指針外，還應該有該關鍵碼所對應記錄所在文件的信息的，比如文件偏移量，要不然怎麼找到這條記錄呢。在實現的時候這個附加數據就沒有放在結點裡面了，下面是定義樹的結構，文件名為btrees.h，內容如下：
代碼如下：
/* btrees.h */
# define M 2
/* B樹的最小度數M>=2
* 每個非根結點必須至少有M-1個關鍵字。每個非根結點至少有M個子女
* 每個結點可包含至多2M-1個關鍵字。所以一個內結點至多可以有2M個子女
*/
typedef int bool ;
struct btnode{ /* B樹結點 */
int keyNum; /* 節點中鍵的數目 */
int k[2*M-1]; /* 鍵 */
struct btnode * p[2*M]; /* 指向子樹的指針 */
bool isleaf;
};
struct searchResult{
struct btnode *ptr; /* 數據所在節點指針 */
int pos; /* 數據在節點中位置 */
};
我們用逐個結點插入的方法創建一棵B樹，結點順序分別是{18, 31, 12, 10, 15, 48, 45, 47, 50, 52, 23, 30, 20}，我們看看具體過程：
1.創建一個空的B樹；
2.插入18，這時候是非滿的，如下所示：
3.同理插入31和12，都比較簡單，如下所示：
4.插入10，這時候根結點是滿的，就要分裂，由於根結點比較特殊，沒有父結點，就要單獨處理，先生成一個空結點做為新的根結點，再進行分裂，如下所示：
5.再插入15，48，45，由於非滿，直接插入，如下所示：
6.插入47，這次葉結點滿了，就要先分裂，再插入，如下所示：
其他都是同樣的道理，就不贅述了，下面是源碼，加入到btree.c中，最後寫了個main函數和一個廣度優先顯示樹的方法，大家可以自己對比結果，代碼的實現參照了《算法導論》和博客
http://hi.baidu.com/kurt023/blog/item/4c368d8b51c59ed3fc1f10cc.html
他博客裡面已經實現了，只是在定義B樹的時候指針數和關鍵碼數成一樣了，我於是自己重寫了一下。
代碼如下：
//函數目的：分裂存儲數達到最大的節點
void btreeSplitChild( struct btnode *parent, int pos, struct btnode *child){
struct btnode *child2;
int i;
//為新分裂出的節點分配空間
child2 = allocateNode(child2);
//與被分裂點同級
child2->isleaf = child->isleaf;
//設置節點數
child2->keyNum = M-1;
//復制數據
for (i=0; i<M-1; i++)
child2->k[i] = child->k[i+M];
//如果不是葉節點，復制指針
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;
}
/* 函數目的：向非滿的節點中插入一個數據
* 注意：插入前保證key在原來的B樹中不存在
*/
void btreeInsertNoneFull( struct btnode *ptr, int data){
int i;
struct btnode *child; //要插入結點的子結點
i = ptr->keyNum;
//如果是葉節點，直接插入數據
if (ptr->isleaf){
while ((i>0) && (data<ptr->k[i-1])){
ptr->k[i] = ptr->k[i-1];
i--;
}
//插入數據
ptr->k[i] = data;
ptr->keyNum++;
}
else { //不是葉節點，找到數據應插入的子節點並插入
while ((i>0) && (data<ptr->k[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); //在子樹中遞歸
}
}
/* 插入一個結點 */
struct btnode * btreeInsert( struct btnode *root, int data){
struct btnode * new ;
/* 檢查是否根節點已滿，如果已滿，分裂並生成新的根節點 */
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 { //還沒到最大數據數，直接插入
btreeInsertNoneFull(root, data);
return root;
}
}
//函數目的：廣度優先顯示樹
void btreeDisplay( struct btnode *root){
int i, queueNum=0;
int j;
struct btnode *queue[20];
struct btnode *current;
//加入隊列
queue[queueNum] = root;
queueNum++;
while (queueNum>0){
//出隊
current = queue[0];
queueNum--;
//移出第一個元素後後面的元素往前移動一個位置
for (i=0; i<queueNum; i++)
queue[i] = queue[i+1];
//顯示節點
j = current->keyNum;
printf ( "[ " );
for (i=0; i<j; i++){
printf ( "%d " , current->k[i]);
}
printf ( "] " );
//子節點入隊
if (current!=NULL && current->isleaf!=1){
for (i=0; i<=(current->keyNum); 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<13; i++){
root = btreeInsert(root, a[i]);
btreeDisplay(root);
}
return 0;
}
