定義：
一棵m階B-樹是擁有以下性質的多路查找樹：
1、非葉子結點的根結點至少擁有兩棵子樹；
2、每一個非根且非葉子的結點含有k－1個關鍵字以及k個子樹，其中⌈m/2⌉≤k≤m；
3、每一個葉子結點都具有k－1個關鍵字，其中⌈m/2⌉≤k≤m；
4、key[i]和key[i+1]之間的孩子節點的值介於key[i]、key[i+1]之間
5、所有的葉子結點都在同一層。
ps： ⌈m/2⌉是向上取整
建立B-樹的節點：
template<class K,int M=3>
struct BTreeNode
{
K _key[M]; //關鍵字 (有效關鍵字個數為M-1)
BTreeNode<K, M>* _sub[M + 1]; //鏈接子樹的指針數組
size_t _size; //節點中關鍵字的個數
BTreeNode<K, M>* _parent; //指向父節點的指針
BTreeNode()
:_size(0)
, _parent(NULL)
{
for (size_t i = 0; i < M + 1; i++)
{
_sub[i] = NULL;
}
}
};
插入數據key：
M階B樹--M=3：
用例 {53, 75, 139, 49, 145, 36, 101};
template<class K,class V>
struct Pair
{
K _first;
V _second;
Pair(const K &k = K(), const V& v = V())
:_first(k)
, _second(v)
{}
};
返回值類型確定好的，其它的就好辦了：
查找函數思想:
遍歷關鍵字數組_key[]，如果key比它小就 ++i 並繼續往後遍歷
1.如果key=_key[i]則停止遍歷，返回該結構體節點
2.如果key比它大則停止遍歷，此時的子樹_sub[i]指向的關鍵字數組的所有數據都是介於_key[i-1]和_key[i]之間的數據，我們要找的key或許就在其中
3.如果跳出循環則未找到該數據cur=NULL，返回cur的父節點；這時候若是插入key，就插入到parent指向的關鍵字數組中
//遞歸查找key
Pair<BTreeNode<K, M>*, int> Find(const K& key)
{
BTreeNode<K, M>* parent=NULL;
BTreeNode<K, M>* cur=_root;
while (cur!=NULL)
{
size_t i = 0;
while (i < cur->_size&&cur->_key[i] < key)
++i;
if (cur->_key[i] == key)
return Pair<BTreeNode<K, M>*, int>(cur, i);
// key<_key[i] 則走向與key[i]下標相同的子樹
parent = cur;
cur = cur->_sub[i];
}
return Pair<BTreeNode<K, M>*, int>(parent, -1);
}
找到位置後，就可以插入該數據key了
分情況：
1.B-樹為NULL
2.B-樹中已經存在key
3.B-樹中不存在key，先把key以插入排序的方式插入到關鍵字數組中，判斷該關鍵字數組是否已滿，滿了就要進行分裂。注意，這裡的分裂有時可能不止一次！
//插入數據
bool Insert(K& key)
{
// 1.B-樹為空
if (NULL == _root)
{
_root = new BTreeNode<K, M>;
_root->_key[0] = key;
++_root->_size;
return true;
}
Pair<BTreeNode<K, M>*, int> ret = Find(key);
// 2.該數據已經存在
if (ret._second != -1)
return false;
// 3.插入數據到關鍵字數組
BTreeNode<K, M>* cur = ret._first;
BTreeNode<K, M>* sub = NULL;
while (1)
{
int i = 0;
for ( i = cur->_size - 1; i >= 0; )
{ // 把大數往後挪，對應子樹也要進行挪動
if (cur->_key[i] > key)
{
cur->_key[i + 1] = cur->_key[i];
cur->_sub[i + 2] = cur->_sub[i + 1];
i--;
}
else
{
break;
}
}
cur->_key[i + 1] = key;
cur->_sub[i + 2] = sub;
if (sub!=NULL)
cur->_sub[i+2]->_parent = cur;
cur->_size++;
//關鍵字數組未滿，插入成功
if (cur->_size < M)
return true;
//關鍵字數組已滿，需要進行分裂
int mid = M / 2;
BTreeNode<K, M>* tmp = new BTreeNode<K, M>;
int index = 0;
size_t k;
for ( k = mid + 1; k < cur->_size; k++)
{
tmp->_key[index] = cur->_key[k];
if (cur->_sub[k] != NULL)
{
tmp->_sub[index] = cur->_sub[k];
cur->_sub[k] = NULL;
tmp->_sub[index]->_parent = tmp;
}
tmp->_size++;
cur->_size--;
index++;
}
if (cur->_sub[k] != NULL)
{
tmp->_sub[index] = cur->_sub[k];
cur->_sub[k] = NULL;
tmp->_sub[index]->_parent = tmp;
}
//父節點為空時的鏈接
if (cur->_parent == NULL)
{
_root = new BTreeNode<K, M>;
_root->_key[0] = cur->_key[mid];
cur->_size--;
_root->_sub[0] = cur;
_root->_sub[1] = tmp;
_root->_size++;
//鏈接
tmp->_parent = _root;
cur->_parent = _root;
return true;
}
//父節點不為空時的鏈接
key = cur->_key[mid];
cur->_size--;
cur = cur->_parent;
sub = tmp;
}
}
要看完整代碼，可以去我的github查看代碼：https://github.com/Lynn-zhang/BTree
