B树

B树的引入

       B树是BST的一个变种，将BST中每k层具有父子关系的节点合并在一起形成一个超级节点，则每个超级节点内

所含关键码的个数应满足以下条件：

（1）最多为1+2+4+..+2^(k-1)=2^k-1个节点，具有2^k个外部分支；

        最多的情况按照每一个节点都有2个孩子计算

（2）最少为1+2+4+2^(k-2)+1=2^(k-1)个节点，具有2^(k-1)+1个外部分支。

        为了

B树需满足以下条件：

（1）除了根节点外，所有节点最多含有m个分支，最少含有cei（m/2）个分支；

（2）叶节点的高度相同，均指向null表示为外部节点；

（3）除根节点外，每个节点含有(cei(m/2),m)个关键码；

因此b树也叫做（cei（m/2）,m）树。

B树的每个节点中，包含了父节点，n个关键码，以及n+1个子树的引用。

B树的Search函数

（1）将根节点作为当前节点；

（2）在当前节点中顺序查找关键码；

（3）找到则返回查找成功：否则沿着引用转到对应的子树；

（4）从（1）开始下一层的查找。

template<typename T>
BTNodePosi(T) BTree<T>::Search(const T& e)
{
BinNodePosi(T) v=_root;

BinNodePosi(T)_hot=NULL;
while(v)
{
    int i=v->key.Search();
    if(i>0 && v->key[i]==e)return v;
    _hot=v;
    v=v->child[i+1];
}
return NULL;
}

B树的Insert函数

（1）调用BTree::Search(),确定待插入的节点不存在，并且确定插入位置；

（2）将关键码插至对应的位置；

（3）创建一个空子树指针；

（4）更新B树的规模，解决节点上溢；

       每次定位之后插入一个元素，可能导致该节点上溢，如果发生上溢的情况，则以中位数

为界进行分裂，将中位数key上移一层，左右两边分离为单独的节点，但如此一来，上一层

可能也发生上溢，如此迭代，最多传到根节点。

B树的Remove函数

（1）删除的key所在的节点可以左顾右盼

       当删除的key所在的节点不是底层节点时，一直往下找到他的后继的key，然后交换两个key值，等效为在底层节点中删

除key。当左兄弟或右兄弟有多余的关键码时，可向兄弟节点借出关键码，但为保证中序序列，采用迂回的方法，需要关键码

的节点先向父节点借出，然后兄弟节点再补给父节点。

（2）删除Key所在的节点左右兄弟中不能借出关键码

如果兄弟节点不能借出关键码，则可从父节点中取出一个关键码，连接该节点和兄弟节点，但这样可能导致更高层的节点下溢。