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* Created on: 2012-10-10* Author: charle* /typedef char* CHARPTR;#include <iostream>#include <cstdio>using namespace std;#define MAX_CNT 5#define MIN_CNT 2typedef struct BTreeNode/ 最大 key 个数为5，最小为2int key5;/ 关键字数组

3、int nodetype;/ 节点类型：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->paren

4、tnode = NULL;root->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;int j = c;for(int i = c-1;i>=0 && j>=0;i-)if(p->keyi>key)tmpj- = p->keyi;else if(p->keyi<=key && fla

5、g = false)tmp j- = key;tmpj- = p->keyi;flag = true;elsetmpj- = p->keyi;return tmp(c+1)/2;_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->

6、;nsize;for(i = 0;i<c;i+)if(p->keyi = key)result = p->succeedingnodei;break;elseint c = p->nsize;文档for(i = 0;i<c;i+)if(p->keyi = key)result = selectKey(p->succeedingnodei + 1,key);break;else if(p->keyi > key)result = selectKey(p->succeedingnodei,key);break;return result;

7、/*INSERT*/bool Insert_BTree(_BTreeNode* 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-

8、>keyi;elsebreak;p->keyi = key;p->nsize +;state = true;/ 节点满，则分裂节点elsesplitNode(p,key);else / 内节点/ 找到 key 的查找分支for(i=0;i<c;i+)if(p->keyi > key)break;/ 顺着分支执行插入if(i < c)state = Insert_BTree(p->succeedingnodei,key);elsestate = Insert_BTree(p->succeedingnodec,key);return state

9、;/* 向上 INSERT*/key,_BTreeNode*boolInsert_BTree2(_BTreeNode*startnode,intoldnode,_BTreeNode* newnode)_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 =

10、p->keyi;elsebreak;p->keyi = key;p->succeedingnodei = 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

11、 != NULL)if(p->isleaf)int c = p->nsize;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->key j+1 = p->keyj;elsebreak;p->keyj = key;/ 暂不考

12、虑关键字对应的记录的存放位置。/ 将剩余的节点复制到新节点中。for(j = mid - 1;j<c;j+)node->keyj-mid = p->keyj;p->key j = 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();parentNod

13、e->key0 = midKey;parentNode->isleaf = false;parentNode->nodetype = 0;/ 根节点parentNode->nsize = 1;parentNode->parentnode = NULL;p->parentnode = node->parentnode = parentNode;parentNode->succeedingnode0 = p;parentNode->succeedingnode1 = node;elsenode->parentnode = p->pa

14、rentnode;Insert_BTree2(p->parentnode,midKey,p,node);else/ 插入右子树int j,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;els

15、enode->keypos+ = p->keyj;p->key j = 0;node->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 = midKe

16、y;parentNode->isleaf = false;parentNode->nodetype = 0;/ 根节点parentNode->nsize = 1;parentNode->parentnode = NULL;p->parentnode = node->parentnode = parentNode;parentNode->succeedingnode0 = p;parentNode->succeedingnode1 = node;elsenode->parentnode = p->parentnode;Insert_BT

17、ree2(p->parentnode,midKey,p,node);state = true;return state;/* 分裂内部节点*/bool splitInterNode(_BTreeNode*internode,_BTreeNode*succeedingnode,intsplitpos,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&

18、lt;c;i+)if(p->keyi>=key)break;/ 构建新的子树节点_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-&g

19、t;succeedingnodei+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->key0 = key;newroot->nsize = 1;newroot->node

20、type = 0;newroot->isleaf = false;newroot->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 =

21、p->key0;node->key0 = tmp;node->succeedingnode0 = 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->ke

22、yi = p->keyi+1;p->succeedingnodei = p->succeedingnodei+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-&g

23、t;succeedingnode0 = node;newroot->succeedingnode1 = 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->succ

24、eedingnode0 = p->succeedingnodec;node->succeedingnode1 = 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->no

25、detype = 0)_BTreeNode* newroot = new _BTreeNode();newroot->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 = newroo

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

27、;if(p->isleaf)/node 为叶子节点int c = p->nsize;int spos,epos,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)/ 没找到 keystate = false;return state;else if(epos = -1)/ 从 spos 到最后都是keyf

28、or(i = spos;i<c;i+)p->keyi = 0;p->succeedingnodei = 0;p->nsize = spos;else/ 从 spos 到 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 为非叶子节

29、点int c = p->nsize;int i;/bool flag = false;/ 找到第一个大于等于key 的键，然后顺着向下找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;/* 检查节点

30、是否需要合并*/bool checkJoin(_BTreeNode *node)bool state = false;_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 节点的键数小于最小节点数，且左兄弟键

31、数大于最小节点数，则借其左兄弟最后一个键及节点指针int i;int c = p->nsize;for(i = 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->nsiz

32、e;left->keyleft->nsize-1 = 0;left->succeedingnodeleft->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;/ 如果非叶节点，则将父节点对应键与该节点的最小键对

33、换elseint tmp = fatherNode->keypos;fatherNode->keypos = p->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->succ

34、eedingnode0;for(i=0;i<left->nsize;i+)left->keyi = left->keyi+1;left->succeedingnodei = left->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 *fa

35、therNode = p->parentnode;/ 如果是叶子节点，则将父节点中右兄弟对应键换为其右兄弟的最小键if(p->isleaf)fatherNode->keypos = right->key0;/ 如果非叶节点，则将父节点中右兄弟对应键与其右兄弟的最小键对换elseint tmp = fatherNode->keypos;fatherNode->keypos = right->key0;right->key0 = tmp;else if(p->nsize < MIN_CNT && left->nsiz

36、e < MIN_CNT)/ 本节点及左兄弟都小于最小节点数，则与左兄弟合并int i;if(p->isleaf)int c = 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);state = deleteParentNode(p->par

37、entnode,pos);state &= deleteNode(p);state &= checkJoin(left->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 +1p->succeedingnode

38、i; left->succeedingnodeleft->nsize + c + 1 = p->succeedingnodec;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