0.序
本人現讀本科大二，這學期學習數據結構，老師為我們的期末作業布置一道任選題，而我一直以來都有聽說B樹是一棵挺神奇的樹，所以我選擇了它，當然更重要的原因是因為B樹的難度最高，我喜歡做有挑戰性的工作。同時，我聽我基友說他熱衷於將自己所學所想分享到博客園上，故才有了這樣一篇文章。希望我能夠在寫博客的同時學習到更多東西，同時也能幫助到其他遇到或者即將遇到雷同問題的初學者們。
1.關於B樹
B樹是一種稱之為查找樹的樹，與之類似的有查找二叉樹，平衡二叉樹，除此之外，還有各種B樹的兄弟姐妹B+樹、B-樹、B*樹等，他們共同的特點就是都是按照一定的順序規律存儲的。B樹的應用也是很廣泛的，B樹是幾乎所有數據庫的默認索引結構，也是用的最多的索引結構。B樹是一種多叉樹，根據其最多叉的數目可以直接稱為M階B樹。根據算法導論上敘述，還可按B樹每個節點最少的分支確定一棵B樹的階，但是這樣的話B樹的階便必須為偶數。我個人是使用根據最大分支的數目確定B樹的階的。
下圖就是某一棵B樹，每一個結點中都包含有數個數據元素，而同時一定會有數據元素的個數加一個的子樹。
一棵M階B樹或為空樹，或為滿足下列特性的M叉樹：
（1）樹中每個結點最多含有M棵子樹；
（2）若根結點不是葉子結點，則至少有2棵子樹；
（3）除根結點之外的所有非終端結點至少有[m/2]棵子樹；
（4）每個非終端結點中包含的信息keynum，ptr[0],key[1],ptr[1],key[2],ptr[2],……key[keynum],ptr[keynum];
其中，key為關鍵字，且關鍵字按升序排序，ptr為指向子樹的根結點指針
2.思路及實現
B樹的接口主要是插入（包括空樹插入一個元素）和刪除操作，而插入和刪除操作不可避免的都會用到查找操作，而查找的主要思路比較簡單，主要是利用B樹是一種排序樹的原理，可以很快找到要插入位置或者要刪除結點。這裡的關鍵是注意返回內容包括查找結果所在結點，以及該元素所在位置，這是為了方便接下來的操作比較簡單。
插入：
通過對B樹進行遍歷，找出要插入的結點以及結點位置，如果找到的key值在B樹當中已經存在，則說明插入失敗，否則，就可以進行插入操作。這裡可以先不管是否超出M階樹的上限要求，因為我們在定義的時候會故意留下一個位置，可以存放多余的一個元素，插入之後，通過判斷是否達到M階樹上限要求，再進行遞歸的分裂操作。
/***
* @name Status insertBTree(BTree &T, Record e)
* @description 插入實現元素的插入
* @return 成功返回OK,如果存在則返回FALSE，否則返回ERROR
* @notice
***/
Status insertBTree(BTree &T, Record e)
{
BTree p;
int index, temp;
Status find_flag;
if (NULL == T)//考慮B樹為空樹的情況
{
T = (BTree)malloc(BTLEN);
if (NULL == T) return OVERFLOW;
T->keynum = 1;
T->parent = NULL;
for (index = 0;index <= m; ++index)
{
T->ptr[index] = NULL;
T->key[index] = 0;
}
T->key[1] = e.key;
return OK;
}
find_flag = findBTree(T, p, temp, e.key);//尋找插入節點
if (find_flag == TRUE)
{
return FALSE;
}
if (find_flag == FALSE)
{ //不管怎樣先直接插入
p->keynum++;
for (index = p->keynum;index > temp;--index)
{
p->key[index] = p->key[index - 1];
p->ptr[index] = p->ptr[index - 1];
}
p->ptr[temp] = NULL;
p->key[temp] = e.key;
if (p->keynum == m) //這種情況得分裂
{
splitBTree(p);
}
renewParent(T);
return OK;
}
return ERROR;
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2015-07/120035p2.htm
