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

B+树算法与源码（C+语言描述）B+树可以看作是B树的变形，对于存放在外存贮器上的字典，B+树比B树更为常用。一个m阶的B+树满足下列条件(1) 每个结点至多有m棵子树。(2) 除根结点外，其它每个分支至少有m/2棵子树。(3) 非叶结点的根结点至少有两棵子树。(4) 有n棵子树的结点有n个关键码，叶结点中至少包含n/2个关键码。(5) 叶结点都在同一层中，其中存放数据文件中记录的关键码及指向该记录的指针，或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值大小顺序链接。可以把每个叶结点看成是一个基本索引块(直接指向数据文件中的记录)。(6) 所有分支结点可看成是索引的索引。使结点中仅包含它的各个子结点中最大(或最小)关键码的分界值及指向子结点的指针。/* * test.cpp * * Created on: 2012-10-10 * Author: charle */typedef char* CHARPTR;#include #include using namespace std;#define MAX_CNT 5#define MIN_CNT 2typedef struct BTreeNode/最大key个数为5，最小为2int key5;/关键字数组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;isucceedingnodei = NULL;root-parentnode = 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-keyikey)tmpj- = p-keyi;else if(p-keyikeyi;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-nsize;for(i = 0;ikeyi = key)result = p-succeedingnodei;break;elseint c = p-nsize;for(i = 0;ikeyi = key)result = selectKey(p-succeedingnodei + 1,key);break;else if(p-keyi key)result = selectKey(p-succeedingnodei,key);break;return result;/* * 向下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 = 0; i-)if(p-keyi key)p-keyi+1 = p-keyi;elsebreak;p-keyi = key;p-nsize +;state = true;/节点满，则分裂节点elsesplitNode(p,key);else/内节点/找到key的查找分支for(i=0;ikeyi key)break;/顺着分支执行插入if(i succeedingnodei,key);elsestate = Insert_BTree(p-succeedingnodec,key);return state;/* * 向上INSERT */bool Insert_BTree2(_BTreeNode* startnode,int key,_BTreeNode* oldnode,_BTreeNode* newnode)_BTreeNode* p = startnode;bool state = false;int i;if(p-nodetype = 0 | p-nodetype = 1)int c = p-nsize;if(p-nsize =0;i-)if(p-keyi key)p-keyi+1 = p-keyi;elsebreak;p-keyi = key;p-succeedingnodei = oldnode;p-succeedingnodei+1 = newnode;p-nsize += 1;state = true;elsefor(i = 0;ikeyi 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;int i;for(i = 0;ikeyi=key)break;int mid = (c + 1)/2;/构建新的子树节点_BTreeNode* node = createNode();if(i =0;j-)if(p-keyjkey)p-keyj+1 = p-keyj;elsebreak;p-keyj = key;/暂不考虑关键字对应的记录的存放位置。/将剩余的节点复制到新节点中。for(j = mid - 1;jkeyj-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;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_BTree2(p-parentnode,midKey,p,node);else/插入右子树int j,pos;pos = 0;bool flag = false;/是否添加for(j = mid;jkeyjkeypos+ = p-keyj;else if(p-keyj=key & flag = false)node-keypos+ = key;node-keypos+ = p-keyj;flag = true;elsenode-keypos+ = p-keyj;p-keyj = 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 = 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-parentnode;Insert_BTree2(p-parentnode,midKey,p,node);state = true;return state;/* * 分裂内部节点 */bool splitInterNode(_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;ikeyi=key)break;/构建新的子树节点_BTreeNode* node = createNode();if(splitpos0 & splitpossucceedingnode0 = succeedingnode;for(i=splitpos;ikeyi-splitpos = p-keyi;node-succeedingnodei-splitpos+1 = p-succeedingnodei+1;p-keyi=p-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-nodetype = 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 = 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;ikeyi = 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-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-succeedingnode0 = 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-nodetype = 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 = newroot;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;if(p-isleaf)/node为叶子节点int c = p-nsize;int spos,epos,i;spos = epos = -1;for(i = 0;ikeyi = 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到最后都是keyfor(i = spos;ikeyi = 0;p-succeedingnodei = 0;p-nsize = spos;else/从spos到epos是keyfor(i = epos;ikeyspos + 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的键，然后顺着向下找for(i = 0;ikeyi = 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;_BTreeNode *p = node;_BTreeNode *left = findBrother(p,1);/寻找左兄弟_BTreeNode *right = findBrother(p,2);/寻找右兄弟if(p-nsize = MIN_CNT)return false;else if(p-nsize nsizeMIN_CNT)/p节点的键数小于最小节点数，且左兄弟键数大于最小节点数，则借其左兄弟最后一个键及节点指针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-nsize;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;/如果非叶节点，则将父节点对应键与该节点的最小键对换elseint tmp = fatherNode-keypos;fatherNode-keypos = p-key0;p-key0 = tmp;else if(p-nsize nsize MIN_CNT)/p节点的键数小于最小节点数，且右兄弟键数大于最小节点数，则借其右兄弟第一个键及节点指针int i;int c = p-nsize;p-keyc = right-key0;p-succeedingnodec+1 = left-succeedingnode0;for(i=0;insize;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 *fatherNode = p-parentnode;/如果是叶子节点，则将父节点中右兄弟对应键换为其右兄弟的最小键if(p-isleaf)fatherNode-keypos = right-key0;/如果非叶节点，则将父节点中右兄弟对应键与其右兄弟的最小键对换elseint tmp = fatherNode-keypos;fatherNode-keypos = right-key0;right-key0 = tmp;else if(p-nsize nsize isleaf)int c = p-nsize;for(i = 0;ikeyleft-nsize + i = p-keyi;left-succeedingnodeleft-nsize + i = p-succeedingnodei;left-nsize += p-nsize;int pos = findPos(left);state = deleteParentNode(p-parentnode,pos);state &= deleteNode(p);state &= checkJoin(left-parentnode);elseint c = p-nsize;left-keyleft-nsize = p-succeedingnode0-key0;for(i = 0;ikeyleft-nsize + i + 1 = p-keyi;left-succeedingnodeleft-nsize + i + 1 = p-succeedingnodei;left-succeedingnodeleft-nsize + c + 1 = p-succeedingnodec;left-nsize += (c + 1);state &= deleteNode(p);state &= checkJoin(left-parentnode);else if(p-nsize nsize isleaf)int c = right-nsize;for(i = 0;ikeyleft-nsize + i = right-keyi;p-succeedingnodeleft-nsize + i = right-succeedingnodei;p-nsize += right-nsize;int pos = findPos(p);state = deleteParentN