B树简介

B树，是为磁盘或其他直接存取辅助存储设备二设计的一种平衡查找树，由于它的特殊结构，可以大大减少访问磁盘I/O的次数，因此在数据库系统常使用Ｂ数或Ｂ树的变形来存储信息。

Ｂ树满足某种条件，与红黑树或其他搜索树不同，一棵M（M>2）的B树，是一棵M路的平衡搜索树，它允许有多条分支子树，它可以是一条空树，或者满足以下性质：

1、根节点至少有两个孩子

2、每个非根节点有[ M/2，M ]个孩子

3、每个非根节点有[ (M/2) -1，M-1 ]个关键字，并且以升序排序

4、key[i]和key[i+1]之间的孩子节点的值介于两者之间

5、所有的叶子节点都在同一层

B树是一棵向上生长的树，当一个节点中的关键字个数达到上限之后，会进行分裂，同时会向上产生一个新的节点，分裂得到两个子节点和一个父节点，父节点只有原来节点中的中间key值，两个子节点将平分原来节点中剩下的key和孩子。这些原因使得B树满足上述条件2~5。接下来看张图，理解一下B树是如何生长的。没有完全看明白先放下，这里只需要知道B树是一棵多路的平衡搜索树。在树不为空树的前提下，如果M=2，那么所有节点内最多会有M-1个关键字key值，每个节点都会有M个孩子。在一个节点内，关键字是从小到大排列的，关键字和孩子是插空分布的，这也保证了B树的平衡搜索性。

接下来通过B树的基本算法来了解一下树。

B树算法

关键字：分裂算法、插入算法、查找算法、中序遍历算法

首先，根据上述B树的要求，这里给出一张B树的示意图（M=3）

上面说过，M表示的是每个结点孩子的个数，但是很明显，在上图中，孩子给出了4个，那么对应的关键字会有3个，和一开始的理论不相符。这里需要说明一下，因为每次向B树中插入节点之后，会进行判断，该节点的关键字个数是否超过了M，如果超过，我们需要进行分裂算法（后面会提到）。

经过简单分析，这里给出B树的节点的定义及构造函数。

template<typenameK,intM>structBTreeNode{K_key[M];//关键字数组BTreeNode<K,M>*_sub[M+1];//指向孩子节点的指针数组BTreeNode<K,M>*_parent;//指向父节点的指针size_t_size;//该节点中已经插入的关键字的个数BTreeNode():_parent(NULL),_size(0){size_ti=0;for(i=0;i<M;i++){_key[i]=K();_sub[i]=NULL;}_sub[i]=NULL;}}

第一步：查找算法 Find()

为什么这里要先来实现B树的查找呢？因为对一棵树的查找来说，并不会影响到树的结构，另外，通过查找，也可以帮助我们得到一些其他的更有利的信息，方便其他功能的实现。

以上面给出的B树为例，在B树中查找一个结点，和普通的平衡树基本思路一样，比该点的key大就向右查找，比该点的key值小，就向左查找。只不过对于B树而言，每个节点有M-1个关键字。因此在向下查找的同时，需要对每个节点中的每个key进行比较。

由于每个节点这里有M个关键字，下标从0~M-1，每个节点有M+1个孩子，指针数组的下标从0~M，仔细观察上树，对于某个节点node而言，比节点中的某个key小的一个值，下一次查找的孩子应该和该key的下标相同。

还需要注意的一点，就是我这里的Find函数是希望能够被其他函数使用的，不仅仅是希望得到一个bool值或找到的Node*，在这里设计Find函数，是希望当找到该key值的话返回key所在节点的下标，同时返回一个指向该节点的指针；没有找到返回 -1，同时返回该节点应该所在位置的父节点。初衷很简单，是为了给待会需要实现的Insert函数调用，达到代码的复用性。如果我们只是判断该节点在不在B树内，那对返回值我们就只需要关注bool即可。要实现返回两个参数，有两种思路：第一就是通过函数传参数的方式，传递引用达到目的，第二就是使用pair类型。

Pair是库中定义好的一个双变量结构体，这里给出库中pair的实现

template<class_Ty1,class_Ty2>structpair{//storeapairofvaluestypedef_Ty1first_type;typedef_Ty2second_type;}

下面是Find函数的实现代码：

typedefpair<Node*,int>FindType;FindTypeFind(constK&key){Node*parent=NULL;Node*cur=_root;while(cur){size_ti=0;while(i<cur->_size){if(key>cur->_key[i]){i++;}elseif(key<cur->_key[i]){break;}else{returnFindType(cur,i);}}parent=cur;cur=cur->_sub[i];}returnFindType(parent,-1);}

第二步：插入算法Insert()与分裂

插入算法应该是比较复杂的了。

我们先考虑这样一个问题，当插入一个元素之后（树不为空树），应该会有两种情况，一种是该节点中关键字的个数并没有超过或等于M，这个时候完全不需要调整，可以直接结束。另一种情况，也就是我们需要考虑的，当插入一个关键字之后，该节点的key满了，这时候，就需要用到分裂算法。

我们来考虑，在下图中的B树中插入56，会发生哪些事。

首先，我们应该先找到56应该插入的位置。这里Find()函数就可以帮得上忙。如果Find查找到了该key，就不需要再插入，如果没有找到，返回最终找到空节点的父节点，直接在该节点中插入即可。在上图中，用Find()函数查找56，返回的指针应该是指向右下角的结点，接下来开始插入节点。

需要注意的是，这里把56插入之后，还做了件其他的事，57的左右孩子也跟着向右移动，因为它的左右孩子都是空结点，因此这里并没有直接画出来。

接下来的任务就是开始分裂。

对B树的分裂，实际上是将关键字超出M-1的节点的中间关键字提取出来，同时将两侧分成两个子节点。注意，这里只是把中间的关键字取出来，然后把中间的关键字再次插入到它的父节点中，同时将分裂产生的的新节点连接到父节点上。连接到父节点上的位置，与向父节点中插入新的关键字的位置有关，如图：

调整之后如果发现，父节点的关键字个数又超出了范围，如上图，则再向上分裂增长，直到某一次插入之后，关键字的个数不超过M-1，则停止分裂并返回，或者某次分裂到根节点之后，对根节点特殊处理，之后直接结束程序。这就是分裂算法。

多注意一点的是，我们第二次插入的过程中，插入了key值，同时将分裂产生的节点也连接到了父节点上，因此，这里对插入key的过程做了一次封装，实现如下：

voidInsertKey(Node*node,constK&key,Node*sub){size_tindex=node->_size-1;//比key小的关键字连带孩子节点同时向后移动while(index>=0){if(node->_key[index]>key){//向后移动node->_key[index+1]=node->_key[index];node->_sub[index+2]=node->_sub[index+1];}else//(node->_key[index]<key){break;}--index;}//将key插入到node结点当中node->_key[index+1]=key;//将分裂产生的结点连接在node节点上node->_sub[index+2]=sub;if(sub!=NULL)sub->_parent=node;//对node的size调整node->_size++;}

下面是插入节点实现代码：

boolInsert(constK&key){//树是空树if(_root==NULL){_root=newNode;_root->_key[0]=key;_root->_parent=NULL;_root->_size=1;returntrue;}//在树中Find该结点FindNoderet=Find(key);if(ret.second!=-1)//树中找到该节点returnfalse;Node*cur=ret.first;Node*parent=cur->_parent;Node*sub=NULL;intnewkey=key;while(1){//在cur节点里面插入key、sub//如果cur没满，跳出循环//cur->key满了，向上分裂InsertKey(cur,newkey,sub);if(cur->_size<M)returntrue;//开始分裂size_tmid=cur->_size/2;newkey=cur->_key[mid];//获取下一次要插入的值Node*tmp=newNode;size_tj=0;size_ti=0;size_tsz=cur->_size;for(i=mid+1;i<sz;i++){tmp->_key[j]=cur->_key[i];tmp->_sub[j]=cur->_sub[i];//注意子节点的父指针if(tmp->_sub[j])tmp->_sub[j]->_parent=tmp;j++;tmp->_size++;//调整sizecur->_size--;cur->_key[i]=K();//将cur分裂出去的部分恢复默认值cur->_sub[i]=NULL;}tmp->_sub[j]=cur->_sub[i];//注意子节点的父指针if(tmp->_sub[j])tmp->_sub[j]->_parent=tmp;cur->_sub[i]=NULL;//清空原来的key[mid]结点cur->_key[mid]=K();cur->_size--;//根节点if(parent==NULL){_root=newNode;_root->_key[0]=newkey;_root->_size=1;_root->_sub[0]=cur;_root->_sub[1]=tmp;cur->_parent=_root;tmp->_parent=_root;returntrue;}//非根节点cur=parent;parent=parent->_parent;sub=tmp;}returntrue;}

要实现插入算法，就是要通过分裂实现，通过判断结点关键字的个数，决定是否分裂，分裂就是以中间的关键字为断点，一分为二，提出中间关键字继续向上插入。两个分节点连接到上一层结点。

第三步：中序遍历算法

之所以要实现中序遍历，是因为对于一棵平衡搜索树而言，中序遍历的结果是有序的，中序遍历采用递归实现并不难，但要注意的一个问题是对每个key进行访问的同时，我们不能再对两个孩子进行递归访问，因为这会对中间的孩子访问两次。如下图：

对中间的结点访问了两次，因此在普通二叉搜索树上除了要增加对每个结点中key的访问，也要禁止对左右子树都遍历，于是有如下实现代码：

//实现代码1void_InOrder(Node*root){if(root==NULL)return;size_ti=0;for(i=0;i<root->_size;i++){_InOrder(root->_sub[i]);cout<<root->_key[i]<<"";}_InOrder(root->_sub[i]);}

//实现代码2void_InOrder(Node*root){if(root==NULL)return;for(size_ti=0;i<root->_size;i++){_InOrder(root->_sub[i]);cout<<root->_key[i]<<"";//遍历过程中存在冲突，因为存在两个指针指向一个结点的情况//解决方案：只打印前一半，到最后一个key的时候再打印后一半if(i==root->_size-1)_InOrder(root->_sub[i+1]);}}

关于测试用例，最直接的就是直接插入1到20，经过测试，1~20 依次插入，包含了所有情况，如果中序遍历可以有序输出，那么表明B树的实现基本已经可以满足要求。

B树及B树的变形，都是减少为了对磁盘的操作，上面看到当我们插入多个节点，它会进行多次的分裂，但当我们把M放到很大，那么它的高度就会成M的指数下降。

当 M=1024 的时候，三层可以容纳10亿个结点，换句话说，10亿结点我们只需要查找三次，对于每个节点中的key值，因为是有序的，采用二分查找不过10次，因此，在查找速度上是非常快的，也就减少了访问磁盘的次数。

对B树的应用，主要都体现在B树的变形上的应用，这也是大多数数据库设计的底层实现。