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

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

2、所有分支结点可看成是索引的索引。使 结点中仅包含它的各个子结点中最大(或最小)关 键码的分界值及指向子结点的指针。/* test.cpp* Created on: 2012-10-10* Author: charle* /typedef char* CHARPTR;#include <iostream>#include <cstdio>using namespace std;#define MAX_CNT 5#define MIN_CNT 2 typedef struct BTreeNode/最大key个数为5,最小为2int key5;关键字数组int nodetyp

3、e;节点类型：0-根，1-内部节点,2-外节点bool isleaf;是否为叶节点int nsize;/关键字个数；BTreeNode* succeedingnode6;BTreeNode* parentnode;_BTreeNode;_BTreeNode* Create_BTree(int key)_BTreeNode *root;root = new _BTreeNode();root->isleaf = 0;for(int i = 0;i<6;i+)root->succeedingnodei = NULL;root->parentnode = NULL;root-

4、>nsize = 0;Insert_BTree(root,key);return root;int middleNode(_BTreeNode* p,int key) int cnt;int c = p->nsize;int tmpc + 1;bool flag = false;intj = c;for(int i = c-l;i>=0 && j>=0;i)(if(p->keyi>key)(= p->keyi;)else if(p->key i<=key && flag = false)(= key;= p-

5、>keyi;flag = true;else(tmpj- = p->key|il;)return tmp(c+l)/2J;_BTreeNode* createNode()BTreeNode* p = new BTreeNode();return p;/*查询功能*/_BTreeNode *selectKey(_BTreeNode *root,int key)_BTreeNode *p = root;_BTreeNode *result = NULL;int i;if(p->isleaf)int c = p->nsize;for(i = 0;i<c;i+) if(p

6、->keyi = key) result = p->succeedingnodei; break;elseint c = p->nsize;for(i = 0;i<c;i+)if(p->keyi = key)resultselectKey(p->succeedingnodei + 1,key); break;else if(p->keyi > key)resultselectKey(p->succeedingnodei,key);break;return result;* 向下 INSERT*/bool Insert_BTree(_BTre

7、eNode* startnode,int key)_BTreeNode* p;bool state = false;if(startnode = NULL)state = false;return state;_BTreeNode* p = startnode;int c = p->nsize;int i;if(p->isleaf)/ 叶子节点节点未满，则插入if(c < 5)for(i = c ; i >= 0; i-)if(p->keyi > key) p->keyi+1 = p->keyi;elsebreak;p->keyi = ke

8、y;p->nsize +;state = true;节点满，则分裂节点elsesplitNode(p,key);else 内节点找到key的查找分支for(i=0;i<c;i+)if(p->keyi > key) break;顺着分支执行插入if(i < c)stateInsert_BTree(p->succeedingnodei,key);elsestateInsert_BTree(p->succeedingnodec,key);return state;/* 向上 INSERT*/bool Insert_BTree2(_BTreeNode* sta

9、rtnode,int newnode)key,_BTreeNode*oldnode,_BTreeNode*_BTreeNode* p = startnode;bool state = false;int i;if(p->nodetype = 0 | p->nodetype = 1)int c = p->nsize;if(p->nsize < c-1 )for(i = c-1;i>=0;i-)if(p->keyi > key)p->keyi+1 = p->keyi;else break;p->keyi = key;p->su

10、cceedingnodei = oldnode;p->succeedingnodei+1 = newnode;p->nsize += 1;state = true;elsefor(i = 0;i<c;i+)if(p->keyi > key) break;state = splitInterNode(p,newnode,i,key);return state;bool splitNode(_BTreeNode *p,int key)bool state = false;if(p != NULL)if(p->isleaf)int c = p->nsize;

11、int i;for(i = 0;i<c;i+)if(p->keyi>=key)break;int mid = (c + 1)/2;构建新的子树节点_BTreeNode* node = createNode();if(i < mid)/插入的关键字存在左子树int j ;for(j = mid-2;j>=0;j-)if(p->keyj>key)p->keyj+1 = p->keyj;elsebreak;p->keyj = key；暂不考虑关键字对应的记录的存放 位置。将剩余的节点复制到新节点中。for(j = mid - 1;j<

12、c;j+)node->keyj-mid = p->keyj;p->keyj = 0；node->nsize = c-mid+1;node->nodetype = p->nodetype;node->isleaf = p->isleaf;int midKey = middleNode(p,key);if(p->parentnode = NULL) _BTreeNode* parentNode = createNode();parentNode->key0 = midKey;parentNode->isleaf = false;pa

13、rentNode->nodetype = 0;/ 根节点 parentNode->nsize = 1;parentNode->parentnode = NULL;p->parentnode = node->parentnode =parentNode;parentNode->succeedingnode0 = P;parentNode->succeedingnode1 = node; else node->parentnode=p->parentnode;Insert_BTree2(p->parentnode,midKey,p,nod

14、e )；elseMff入右子树intj,pos;pos = 0;bool flag = false;是否添加for(j = mid;j<c;j+)if(p->keyj<key)node->keypos+ = p->keyj;else if(p->keyj>=key && flag = false)node->keypos+ = key;node->keypos+ = p->keyj; flag = true; else node->keypos+ = p->keyj; p->keyj = 0;node

15、->nsize = c-mid+1;node->parentnode = p->parentnode; node->nodetype = p->nodetype; node->isleaf = p->isleaf;int midKey = middleNode(p,key); if(p->parentnode = NULL) _BTreeNode* parentNode createNode(); parentNode->key0 = midKey; parentNode->isleaf = false;parentNode->

16、nodetype = 0;/ 根节点 parentNode->nsize = 1;parentNode->parentnode = NULL;p->parentnode = node->parentnode = parentNode;parentNode->succeedingnode0 = p;parentNode->succeedingnode1 = node;elsenode->parentnode = p->parentnode;Insert_BTree2(p->parentnode,midKey,p,node );state =

17、true;return state;'*分裂内部节点*/boolsplitInterNode(BTreeNode*internode,_BTreeNode *succeedingnode,int splitpos,int key)bool state = false;_BTreeNode *p = internode;if(p != NULL)存在父节点_BTreeNode *node = new _BTreeNode();int c = p->nsize;int i;for(i = 0;i<c;i+) if(p->keyi>=key)break;构建新的子树节

18、点_BTreeNode* node = createNode(); if(splitpos>0 && splitpos<c) node->succeedingnode0 succeedingnode;for(i=splitpos;i<c;i+)node->keyi-splitpos = p->keyi;node->succeedingnodei-splitpos+1 = p->succeedingnodei+1;p->keyi=p->succeedingnodei+1=0;node->nsize = c-spli

19、tpos;node->isleaf = p->isleaf;node->nodetype = p->nodetype; node->parentnode = p->parentnode;p->nsize = splitpos;if(p->nodetype = 0)_BTreeNode* newroot = new _BTreeNode();newroot->key0 = key;newroot->nsize = 1;newroot->nodetype = 0;newroot->isleaf = false;newroot-

20、>succeedingnode0 = p;newroot->succeedingnode1 = node;p->nodetype = node->nodetype = 1;p->parentnode = node->parentnode =newroot;state = true;elsestate=Insert_BTree2(p->parentnode,key,p,node);else if(splitpos = 0)int tmp = key;key = p->key0;node->key0 = tmp;node->succeed

21、ingnode0=p->succeedingnode0;node->succeedingnode1=succeedingnode;node->nsize = 1;node->isleaf = p->isleaf;node->nodetype = p->nodetype; node->parentnode = p->parentnode; int c = p->nsize;int i;for(i=0;i<c-1;i+)p->keyi = p->keyi+1;p->succeedingnodei=p->suc

22、ceedingnodei+1; p->succeedingnodec-1=p->succeedingnodec;p->nsize = c-1;if(p->nodetype = 0)_BTreeNode* newroot = new _BTreeNode();newroot->key0 = key;newroot->nsize = 1;newroot->nodetype = 0;newroot->isleaf = false;newroot->succeedingnode0 = node;newroot->succeedingnode1

23、 = p;p->nodetype = node->nodetype = 1;p->parentnode = node->parentnode = newroot;state = true;elsestate=Insert_BTree2(p->parentnode,key,node,p);else if(splitpos = c)int tmp = key;key = p->keyc-1;node->key0 = tmp;node->succeedingnode0=p->succeedingnodec;node->succeedingn

24、ode1=succeedingnode;node->nsize = 1;node->isleaf = p->isleaf;node->nodetype = p->nodetype;node->parentnode = p->parentnode;int c = p->nsize;int i;p->keyc-1 = 0;p->succeedingnodec = 0;p->nsize = c-1;if(p->nodetype = 0)_BTreeNode* newroot = new _BTreeNode();newroot-

25、>key0 = key;newroot->nsize = 1;newroot->nodetype = 0;newroot->isleaf = false;newroot->succeedingnode0 = p;newroot->succeedingnode1 = node;p->nodetype = node->nodetype = 1;p->parentnode = node->parentnode = newroot;state = true; elsestateInsert_BTree2（p->parentnode,ke

26、y,p,node）;return state;/* 删除节点* 删除节点N后，如果N节点的个数少于最少 值，先从左右兄弟借，然后再合并；* 当左兄弟（或右兄弟）的键个数大于最小值, 且N节点个数小于最小值时，从左兄弟（或右 兄弟）借一个给N* 当无处可借时，则与左兄弟（或右兄弟）合 并，合并后父节点需调整。* /bool Delete_Node（_BTreeNode *node,int key）bool state = false;_BTreeNode *p = node;if(p->isleaf)/node 为叶子节点int c = p->nsize;int spos,epos,

27、i;spos = epos = -1;for(i = 0;i<c;i+)if(p->keyi = key && spos = -1)spos = i;else if(p->keyi > key && epos = -1)epos = i;break;if(spos = -1)没找至>J key state = false;return state;else if(epos = -1)从 spos 至1J最后者B是 keyfor(i = spos;i<c;i+)p->keyi = 0;p->succeedingnod

28、ei = 0;p->nsize = spos;else/R spos 至1J epos 是 keyfor(i = epos;i<c;i+)p->keyspos + i = p->keyepos + i;p->succeedingnodespos + i p->succeedingnodeepos + i;p->nsize -= epos - spos;state = checkJoin(p);/检查是否要合并else/node为非叶子节点int c = p->nsize;int i;/bool flag = false;找到第一个大于等于key的

29、键，然后顺着 向下找for(i = 0;i<c;i+)if(p->keyi = key)Delete_Node(p->succeedingnodei+1,key);break;else if(p->keyi > key)Delete_Node(p->succeedingnodei,key);break;if(i = c)state = false;return state;state = true;return state; /*检查节点是否需要合并*/ bool checkJoin(_BTreeNode *node)bool state = false;_

30、BTreeNode *p = node;_BTreeNode *left = findBrother(p,1); 寻找左兄弟_BTreeNode *right = findBrother(p,2);/ 寻找右兄弟if(p->nsize >= MIN CNT) return false;else if(p->nsize < MIN_CNT && left->nsize>MIN_CNT)/p节点的键数小于最小节点数，且左兄弟键 数大于最小节点数，则借其左兄弟最后一个键及 节点指针int i;int c = p->nsize;for(i =

31、c-1;i>=0;i-)p->keyi+1 = p->keyi;p->succeedingnodei+2=p->succeedingnodei+1;p->succeedingnode1=p->succeedingnode0;p->key0 = left->keyleft->nsize - 1;p->succeedingnode0= left->succeedingnodeleft->nsize;left->keyleft->nsize-1 = 0;left->succeedingnodeleft-&

32、gt;nsize = NULL;left->nsize-;p->nsize+;int pos = findPos(p);if(pos = -1)return false;_BTreeNode *fatherNode = p->parentnode;如果是叶子节点，则将父节点对应键换为该节点的最小键if(p->isleaf) fatherNode->keypos =p->key0;如果非叶节点，则将父节点对应键与该节 点的最小键对换elseint tmp = fatherNode->keypos; fatherNode->keypos = p-&g

33、t;key0; p->key0 = tmp;else if(p->nsize < MIN_CNT && right->nsize > MIN_CNT)/p节点的键数小于最小节点数，且右兄弟键 数大于最小节点数，则借其右兄弟第一个键及节 点指针int i;int c = p->nsize;p->keyc = right->key0;p->succeedingnodec+1=left->succeedingnode0;for(i=0;i<left->nsize;i+)left->keyi = left-&

34、gt;keyi+1; left->succeedingnodeileft->succeedingnodei+1;left->keyleft->nsize-1 = 0;left->succeedingnodeleft->nsize = NULL;left->nsize-;p->nsize+;int pos = findPos(right);if(pos = -1)return false;_BTreeNode *fatherNode = p->parentnode;如果是叶子节点，则将父节点中右兄弟对 应键换为其右兄弟的最小键if(p->

35、;isleaf)fatherNode->keypos = right->key0;如果非叶节点，则将父节点中右兄弟对应 键与其右兄弟的最小键对换elseint tmp = fatherNode->keypos; fatherNode->keypos = right->key0; right->key0 = tmp;else if(p->nsize < MIN_CNT && left->nsize < MIN_CNT)本节点及左兄弟都小于最小节点数，则与 左兄弟合并int i;if(p->isleaf)int c

36、= p->nsize;for(i = 0;i<c;i+)left->keyleft->nsize + i = p->keyi;left->succeedingnodeleft->nsize + i= p->succeedingnodei;left->nsize += p->nsize;int pos = findPos(left);statedeleteParentNode(p->parentnode,pos);state &= deleteNode(p);state &= checkJoin(left->

37、parentnode);elseint c = p->nsize;left->keyleft->nsize=p->succeedingnode0->key0;for(i = 0;i<c;i+)left->keyleft->nsize + i + 1= p->keyi;left->succeedingnodeleft->nsize + i + 1 = p->succeedingnodei;left->succeedingnodeleft->nsize + c + 1 =p->succeedingnodec;

38、left->nsize += (c + 1);state &= deleteNode(p);state &= checkJoin(left->parentnode);else if(p->nsize < MIN CNT && right->nsize< MIN_CNT)本节点及右兄弟都小于最小节点数，则与 右兄弟合并int i;if(p->isleaf)int c = right->nsize;for(i = 0;i<c;i+)p->keyleft->nsize + i = right->keyi;p->succeedingnodeleft->nsize + i= right->succeedingnodei;p->nsize += right->nsize;int pos =