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樹的插入都是在葉子結點進行的，由于B樹的結點中關鍵碼的個數是有限制的，最小度數為M的B樹的結點個數是從M-1到2M-1個。比如下圖是最小度數為2的B樹(又稱為2-3樹)，如下圖所示，它的結點的個數就是1-3個。
先定位到要插入的位置，如果葉子結點的關鍵碼個數還沒達到上限，比如插入32，就比較簡單，直接插入就行；如果葉子結點的關鍵碼數到達了上限，就要分裂成2個子結點，把中間的關鍵碼往上放到父節點中。但有極端的情況，就是父結點也是滿的，就需要再次分裂，可能最后要把根結點也分裂了。但是這種算法不太好實現。
在《算法導論》中實現用的是另外一種思想，就是先分裂，在查找插入位置的過程中，如果發現有滿的結點，就先把它分裂了，這就保證了在最后葉結點上插入數據的時候，這個葉結點的父結點總是不滿的。下面我們看一個例子：
我們用逐個結點插入的方法創建一棵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
child2->k[i] = child->k[i+M];
//如果不是葉節點，復制指針
if (!child->isleaf)
for (i=0; 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
k[i-1])){
ptr->k[i] = ptr->k[i-1];
i--;
}
//插入數據
ptr->k[i] = data;
ptr->keyNum++;
}
else { //不是葉節點，找到數據應插入的子節點并插入
while ((i>0) && (datak[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 queue[i] = queue[i+1];
//顯示節點
j = current->keyNum;
printf ( "[ " );
for (i=0; i printf ( "%d " , current->k[i]);
}
printf ( "] " );
//子節點入隊
if (current!=NULL && current->isleaf!=1){
for (i=0; ikeyNum); 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 root = btreeInsert(root, a[i]);
btreeDisplay(root);
}
return 0;
}?
?
?
?
運行結果：
同樣一批關鍵碼用不同算法生成的B樹可能是不同的，比如4個關鍵碼的結點[1，2，3，4]分裂的時候，把2或3放上去都可以；同樣的算法插入順序不同也可能不同。
附件中是源碼，在Linux下編譯通過。
以上就是深入理解C語言B樹原理的全部內容，感謝大家的閱讀，更多內容請關注武林技術頻道網站。
