B树是一种多叉的平衡搜索树，适合外查找。
一棵M叉（M>2）的B树，可以是一棵空树，也可以是具有如下的性质的B树：（M为）
1.根节点至少有两个孩子
2.每个非根结点有[M/2，M]个孩子
3.每个非根结点有[M/2-1，M-1]个关键字，并且是以升序排列
4.key[i]与key[i+1]之间的孩子结点的值介于key[i]与key[i+1]之间
5.所有叶子节点在同一层
以这组数据为例：{1,5,16,17,18,20,30,35,36,40,45,46,50,55,56}; 假设M=3：
一、BTreeNode的定义
从上边的图我们就可以看出B树与之前的二叉树不同：1.它有M叉；2.关键字key可以有多个；3.指向孩子结点的指针有多个。因此我们在定义节点的时候应该给一个数组来存这些关键字，用一个指针数组来存放指向孩子结点的指针。
那数组的大小给多少呢？！当一个结点中的关键字满了之后要进行分裂，我们就多给出一个空间的位置，方便分裂（分裂后边会讲到~）
template<class K,int M>
struct BTreeNode
{
//K _keys[M-1]; //关键字数组
//BTreeNode<K,M>* _subs[M]; //指向孩子结点的指针数组
//多给一个空间位置，方便分裂
K _keys[M]; //关键字数组
BTreeNode<K,M>* _subs[M+1]; //指向孩子结点的指针数组
BTreeNode<K,M>* _parent; //指向父亲节点的指针
size_t _size; //关键字个数
BTreeNode()
:_parent(NULL)
,_size(0)
{
for (size_t i=0; i<M; ++i)
{
//_keys[i] = 0;
_keys[i] = K();
_subs[i] = NULL;
}
_subs[M] = NULL;
}
};
1.查找
查找一个关键字key，当key小于当前的根节点的_key[0]，就应该去它的左孩子中遍历；当key大于当前根节点的_key[0],就应该继续与该数组后边的数据比较，当这个结点的_key[]遍历完后没找到的话就去遍历其下一个孩子结点
bool Find(const K& key)
{
if (_root == NULL)
return false;
Node* cur = _root;
size_t i = 0;
while (cur)
{
while (i < cur->_size) //先在当前结点的_key[]中查找
{
if (cur->_keys[i] < key)
++i;
else if (cur->_keys[i] > key)
cur = cur->_subs[i];
else
return true;
}
cur = cur->_subs[i]; //如果没找到就去下一个孩子结点中找
}
return false;
}
（1）当_root为空的情况下，直接创建一个新结点将key值插入；
（2）当_root不为空的情况下，插入key值时应该先检查该key是否已经存在(key不能冗余)；不存在时再查找这个key值合适的位置，查找的方式与Find一样，因此可以复用Find函数()；找到这个位置后先进行插入，再来判断这时关键字的个数_size是否满足性质3，当_size>M时就要对该节点进行分裂
Find函数的复用：
上边实现的Find函数只能判断key值是否存在而不能修改。但在Insert复用时，不仅要找到key是否存在，还要在找到位置后进行插入，因此返回值不能只用false和true判断，我们可以改为pair结构体作为返回值，pair.first存结点，pair.second存value或-1，当找到这个key时，就返回父结点并返回对应的value值(便于插入)；当找不到时就返回父节点和-1，因此判断是否存在只能通过pair.second是否为-1来判断
pair<Node* ,int> Find(const K& key)
{
Node* cur = _root;
Node* parent = NULL;
size_t i = 0;
while (cur)
{
while (i < cur->_size)
{
if (cur->_keys[i] < key)
++i;
else if (cur->_keys[i] > key)
{
break;
}
else
{
//如果找到就返回key的父节点以便于插入
return pair<Node* ,int> (parent,i);
}
}
parent = cur;
cur = cur->_subs[i];
}
//没找到就返回-1
return pair<Node* ,int> (parent,-1);
}
key的插入：
当找到位置后无论如何先插入，再判断需不需要分裂，这样就比较好分析一点！
分裂：· 当一个结点的关键字个数多余M-1时，就要对该节点进行分裂，使其重新满足该条件
· 分裂的方法：找出_key[]数组的中间值_key[mid]，并重新创建一个根节点和一个孩子节点tmp，将_key[mid]赋给该根节点；以_key[mid]为分界点，将其右半区间的值拷贝给tmp。注意拷贝key数据时应该把孩子结点也拷贝过来！拷贝完成后将当前节点cur与新的孩子结点tmp重新作为新的根节点的孩子！
· 分裂何时停止：停止的条件有俩个，当分裂出一个新的根结点_root 或 当某个结点满足_size<M时 即可停止分裂；否则就要继续向上分裂。
bool Insert(const K& key)
{
if (_root == NULL)
{
_root = new Node;
_root->_keys[0] = key;
_root->_size++;
return true;
}
//key不冗余
pair<Node* ,int> ret = Find(key);
if (ret.second != -1)
return false;
//cur从需要插入key的位置父节点开始
Node* cur = ret.first;
Node* sub = NULL;
K newkey = key;
while (1)
{
//1.插入key和sub
InsertKey(cur,newkey,sub);
//2.如果cur不满，就停止
if (cur->_size < M)
return true;
//3.如果cur满了，就继续向上分裂
else
{
Node* tmp = new Node;
size_t mid = cur->_size / 2; //找到cur->_keys中间位置
size_t j = 0;
size_t i=mid+1;
//拷贝右半区间的key和孩子
for ( ; i<cur->_size; ++i)
{
tmp->_keys[j] = cur->_keys[i];
tmp->_subs[j] = cur->_subs[i];
if (cur->_subs[i]) //如果该位置的孩子不为NULL就使其指向新分裂的父节点
cur->_subs[i] = tmp;
tmp->_size++;
cur->_keys[i] = K();
cur->_subs[i] = NULL;
cur->_size--;
j++;
}
//将cur中最后一个孩子拷贝过来
tmp->_subs[j] = cur->_subs[i];
if (cur->_subs[i])
cur->_subs[i]->_parent = tmp;
//如果没分裂到根结点，则继续向上分裂
newkey = cur->_keys[mid];
cur->_keys[mid] = K();
cur->_size--;
sub = tmp;
//如果重新分裂出一个根节点，则停止分裂
if (cur->_parent == NULL)
{
_root = new Node;
_root->_keys[0] = newkey;
_root->_subs[0] = cur;
_root->_subs[1] = tmp;
_root->_size = 1;
cur->_parent = _root;
tmp->_parent = _root;
return true;
}
cur = cur->_parent;
}
}
}
void InsertKey(Node* cur,const K& key,Node* sub)
{
//挪动key和孩子结点
int i = cur->_size-1;
while (i>=0)
{
if (cur->_keys[i] < key)
break;
else
{
cur->_keys[i+1] = cur->_keys[i];
cur->_subs[i+2] = cur->_subs[i+1];
--i;
}
}
cur->_keys[i+1] = key;
cur->_subs[i+2] = sub;
if (sub)
sub->_parent = cur;
cur->_size++;
}
根据BTree的性质3我们可以给出中序遍历，这样得到的结果就是一个升序的数组。与之前相同的是都要找到最左结点然后开始遍历。但不同的是要先遍历完一个结点的_Key[]数组，然后才能遍历下一个结点。
void _InOrder(Node* root)
{
if (root == NULL)
return ;
Node* cur = root;
size_t i=0;
for (; i<cur->_size; ++i)
{
_InOrder(cur->_subs[i]);
cout<<cur->_keys[i]<<" ";
}
_InOrder(cur->_subs[i]);
}