b+树地实现算法(c++版)

《b+树地实现算法(c++版)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用标准文案B+树算法与源码（C++语言描述）B+树可以看作是B树的变形，对于存放在外存贮器上的字典，B+树比B树更为常用。　　一个m阶的B+树满足下列条件∶　　(1)每个结点至多有m棵子树。　　(2)除根结点外，其它每个分支至少有m/2棵子树。　　(3)非叶结点的根结点至少有两棵子树。　　(4)有n棵子树的结点有n个关键码，叶结点中至少包含n/2个关键码。　　(5)叶结点都在同一层中，其中存放数据文件中记录的关键码及指向该记录的指针，或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值

2、大小顺序链接。可以把每个叶结点看成是一个基本索引块(直接指向数据文件中的记录)。　　(6)所有分支结点可看成是索引的索引。使结点中仅包含它的各个子结点中最大(或最小)关键码的分界值及指向子结点的指针。/**test.cpp**Createdon:2012-10-10*Author:charle*///typedefchar*CHARPTR;#include#includeusingnamespacestd;#defineMAX_CNT5#defineMIN_CNT2ty

3、pedefstructBTreeNode{//最大key个数为5，最小为2intkey[5];//关键字数组intnodetype;//节点类型：0-根，1-内部节点，2-外节点boolisleaf;//是否为叶节点intnsize;//关键字个数；BTreeNode*succeedingnode[6];BTreeNode*parentnode;}_BTreeNode;_BTreeNode*Create_BTree(intkey){_BTreeNode*root;文档实用标准文案root=new_BTre

4、eNode();root->isleaf=0;for(inti=0;i<6;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

5、;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;}/***文档实用标准文案*查询功能*/_BTre

6、eNode*selectKey(_BTreeNode*root,intkey){_BTreeNode*p=root;_BTreeNode*result=NULL;inti;if(p->isleaf){intc=p->nsize;for(i=0;ikey[i]==key){result=p->succeedingnode[i];break;}}}else{intc=p->nsize;for(i=0;ikey[i]==key){result=select

7、Key(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

8、;returnstate;}_BTreeNode*p=startnode;intc=p->nsize;inti;if(p->isleaf)//叶子节点{//节点未满,则插入if(c<5){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{