B+树的实现算法(C++版)

B+树算法与源码（C++语言描述）B+树可以看作是B树的变形，对于存放在外存贮器上的字典，B+树比B树更为常用。一个m阶的B+树满足下列条件∶(1)每个结点至多有m棵子树。(2)除根结点外，其它每个分支至少有m/2棵子树。(3)非叶结点的根结点至少有两棵子树。(4)有n棵子树的结点有n个关键码，叶结点中至少包含n/2个关键码。(5)叶结点都在同一层中，其中存放数据文件中记录的关键码及指向该记录的指针，或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值大小顺序链接。可以把每个叶结点看成是一个基本索引块(直接指向数据文件中的记录)。(6)所有分支结点可看成是索引的索引。使结点中仅包含它的各个子结点中最大(或最小)关键码的分界值及指向子结点的指针。/**test.cpp**Createdon:2012-10-10*Author:charle*///typedefchar*CHARPTR;#includeiostream#includecstdiousingnamespacestd;#defineMAX_CNT5#defineMIN_CNT2typedefstructBTreeNode{//最大key个数为5，最小为2intkey[5];//关键字数组intnodetype;//节点类型：0-根，1-内部节点，2-外节点boolisleaf;//是否为叶节点intnsize;//关键字个数；BTreeNode*succeedingnode[6];BTreeNode*parentnode;}_BTreeNode;_BTreeNode*Create_BTree(intkey){_BTreeNode*root;root=new_BTreeNode();root-isleaf=0;for(inti=0;i6;i++)root-succeedingnode[i]=NULL;root-parentnode=NULL;root-nsize=0;Insert_BTree(root,key);returnroot;}intmiddleNode(_BTreeNode*p,intkey){intcnt;intc=p-nsize;inttmp[c+1];boolflag=false;intj=c;for(inti=c-1;i=0&&j=0;i--){if(p-key[i]key){tmp[j--]=p-key[i];}elseif(p-key[i]=key&&flag==false){tmp[j--]=key;tmp[j--]=p-key[i];flag=true;}else{tmp[j--]=p-key[i];}}returntmp[(c+1)/2];}_BTreeNode*createNode(){_BTreeNode*p=new_BTreeNode();returnp;}/****查询功能*/_BTreeNode*selectKey(_BTreeNode*root,intkey){_BTreeNode*p=root;_BTreeNode*result=NULL;inti;if(p-isleaf){intc=p-nsize;for(i=0;ic;i++){if(p-key[i]==key){result=p-succeedingnode[i];break;}}}else{intc=p-nsize;for(i=0;ic;i++){if(p-key[i]==key){result=selectKey(p-succeedingnode[i+1],key);break;}elseif(p-key[i]key){result=selectKey(p-succeedingnode[i],key);break;}}}returnresult;}/***向下INSERT*/boolInsert_BTree(_BTreeNode*startnode,intkey){_BTreeNode*p;boolstate=false;if(startnode==NULL){state=false;returnstate;}_BTreeNode*p=startnode;intc=p-nsize;inti;if(p-isleaf)//叶子节点{//节点未满,则插入if(c5){for(i=c;i=0;i--){if(p-key[i]key)p-key[i+1]=p-key[i];elsebreak;}p-key[i]=key;p-nsize++;state=true;}//节点满，则分裂节点else{splitNode(p,key);}}else//内节点{//找到key的查找分支for(i=0;ic;i++){if(p-key[i]key)break;}//顺着分支执行插入if(ic)state=Insert_BTree(p-succeedingnode[i],key);elsestate=Insert_BTree(p-succeedingnode[c],key);}returnstate;}/****向上INSERT*/boolInsert_BTree2(_BTreeNode*startnode,intkey,_BTreeNode*oldnode,_BTreeNode*newnode){_BTreeNode*p=startnode;boolstate=false;inti;if(p-nodetype==0||p-nodetype==1){intc=p-nsize;if(p-nsizec-1){for(i=c-1;i=0;i--){if(p-key[i]key)p-key[i+1]=p-key[i];else{break;}}p-key[i]=key;p-succeedingnode[i]=oldnode;p-succeedingnode[i+1]=newnode;p-nsize+=1;state=true;}else{for(i=0;ic;i++){if(p-key[i]key)break;}state=splitInterNode(p,newnode,i,key);}}returnstate;}boolsplitNode(_BTreeNode*p,intkey){boolstate=false;if(p!=NULL){if(p-isleaf){intc=p-nsize;inti;for(i=0;ic;i++)if(p-key[i]=key)break;intmid=(c+1)/2;//构建新的子树节点_BTreeNode*node=createNode();if(imid)//插入的关键字存在左子树{intj;for(j=mid-2;j=0;j--){if(p-key[j]key){p-key[j+1]=p-key[j];}elsebreak;}p-key[j]=key;//暂不考虑关键字对应的记录的存放位置。//将剩余的节点复制到新节点中。for(j=mid-1;jc;j++){node-key[j-mid]=p-key[j];p-key[j]=0;}node-nsize=c-mid+1;node-nodetype=p-nodetype;node-isleaf=p-isleaf;intmidKey=middleNode(p,key);if(p-parentnode==NULL){_BTreeNode*parentNode=createNode();parentNode-key[0]=midKey;parentNode-isleaf=false;parentNode-nodetype=0;//根节点parentNode-nsize=1;parentNode-parentnode=NULL;p-parentnode=node-parentnode=parentNode;parentNode-succeedingnode[0]=p;parentNode-succeedingnode[1]=node;}else{node-parentnode=p-parentnode;Insert_BTree2(p-parentnode,midKey,p,node);}}else//插入右子树{intj,pos;pos=0;boolflag=false;//是否添加for(j=mid;jc;j++){if(p-key[j]key){node-key[pos++]=p-key[j];}elseif(p-key[j]=key&&flag==false){node-key[pos++]=key;node-key[pos++]=p-key[j];flag=true;}else{node-key[pos++]=p-key[j];}p-key[j]=0;}node-nsize=c-mid+1;node-parentnode=p-parentnode;node-nodetype=p-nodetype;node-isleaf=p-isleaf;}intmidKey=middleNode(p,key);if(p-parentnode==NULL){_BTreeNode*parentNode=createNode();parentNode-key[0]=midKey;parentNode-isleaf=false;parentNode-nodetype=0;//根节点parentNode-nsize=1;parentNode-parentnode=NULL;p-parentnode=node-parentnode=parentNode;parentNode-succeedingnode[0]=p;parentNode-succeedingnode[1]=node;}else{node-parentnode=p-parentnode;Insert_BTree2(p-parentnode,midKey,p,node);}state=true;}}returnstate;}/****分裂内部节点*/boolsplitInterNode(_BTreeNode*internode,_BTreeNode*succeedingnode,intsplitpos,intkey){boolstate=false;_BTreeNode*p=internode;if(p!=NULL){//存在父节点_BTreeNode*node=new_BTreeNode();intc=p-nsize;inti;for(i=0;ic;i++)if(p-key[i]=key)break;//构建新的子树节点_BTreeNode*node=createNode();if(splitpos0&&splitposc){node-succeedingnode[0]=succeedingnode;for(i=splitpos;ic;i++){node-key[i-splitpos]=p-key[i];node-succeedingnode[i-splitpos+1]=p-succeedingnode[i+1];p-key[i]=p-succeedingnode[i+1]=0;}node-nsize=c-splitpos;node-isleaf=p-isleaf;node-nodetype=p-nodetype;node-parentnode=p-parentnode;p-nsize=splitpos;if(p-nodetype==0){_BTreeNode*newroot=new_BTreeNode();newroot-key[0]