B树的实现算法C版

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

2、各个子结点中最大（或最小）关 键码的分界值及指向子结点的指针。/* test.c PP* Created on: 2012-10-10Author: charle*/typ edef char* CHAR PTR;#in clude <iostream>#in clude <cstdio> using n ames pace std;#defi ne MAX_CNT 5#define MIN CNT 2 typ edef struct BTreeNode/最大key个数为5,最小为2int key5;/关键字数组int nodetype;/节点类型：0-根，1-内部节点

3、,2-外节点bool isleaf;/是否为叶节点int nsize;/关键字个数；BTreeNode* succeedi ngno de6;BTreeNode* parentnode;_BTreeNode;_BTreeNode* Create_BTree(i nt key)_BTreeNode *root;root = new _BTreeNode(); root->isleaf = 0;for(i nt i = 0;i<6;i+)root->succeedi ngno dei = NULL; root- >parentnode = NULL; root- >n

4、 size = 0;In sert_BTree(root,key); return root; int middleNode(_BTreeNode* p,i nt key) int ent;int c = p->n size;int tmpc + 1;bool flag = false;int j = c;for(i nt i = c-1;i>=0 && j>=0;i-)if(p->keyi>key)tmpj- = p->keyi;else if(p->keyiv=key && flag = false)tmp j- =

5、 key;tmp j- = p->keyi;flag = true;elsetmp j- = 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->n size;for

6、(i = 0;i<c;i+)if(p->keyi = key)result = p->succeedi ngno dei; break;elseint c = p->n size;for(i = 0;ivc;i+)if(p->keyi = key)resultselectKey( p->succeedi ngno dei + 1,key); break;else if(p->keyi > key)resultselectKey( p->succeedi ngno dei,key);break;retur n result;/* 向下 INS

7、ERT*/bool In sert_BTree(_BTreeNode*start no de,i ntkey)_BTreeNode* p;bool state = false;if(start node = NULL)state = false;return state;_BTreeNode* p = start node; int c = p->n size;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->n size +;state = true;节点满，则分裂节点elsesplitNode(p,key);else /内节点找到key的查找分支for(i=0;i<c;i+)if(p->keyi > key) break;顺着分支执行插入if(i < c)stateIn sert_BTree( p->succeedi ngno dei,key);elsestateIn sert_BTree( p->succeedi ngno dec,key); return state;

9、9;*向*/INSERTbool In sert_BTree2(_BTreeNode* start no de,i nt key,_BTreeNode*old node,_BTreeNode*newno de)_BTreeNode* p = start no de;bool state = false;int i;if(p->no detype = 0 | p->no detype = 1)int c = p->n size;if(p->n size < c-1 )for(i = c-1;i>=0;i-)if(p->keyi > key)p-&g

10、t;keyi+1 = p->keyi;else break;p->keyi = key;p->succeedi ngno dei = old no de;p->succeedi ngno dei+1 = newno de; p->n size += 1;state = true;elsefor(i = 0;i<c;i+)if(p->keyi > key) break;state = split In terNode(p, newno de,i,key);return state;bool sp litNode(_BTreeNode *p ,i n

11、t key)bool state = false;if(p != NULL)if(p->isleaf)int c = p->n size;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->key|j>key)p->keyj+1 = p->keyj;el

12、se break;p->keyj = key;/暂不考虑关键字对应的记录的存放位置。将剩余的节点复制到新节点中for(j = mid - 1；j<c;j+)no de->keyj-mid = p->keyj; p->keyj = 0;no de->n size = c-mid+1;no de->no det ype = p->no det ype; no de->isleaf = p->isleaf;int midKey = middleNode( p,key);if(p->parentnode = NULL)BTreeNode

13、* paren tNodecreateNode();paren tNode->key0 = midKey;paren tNode->isleaf = false;parentNode->nodetype = 0;/ 根节点paren tNode->n size = 1;paren tNode->parentnode = NULL;p->p are ntnode = no de->p are ntnode =paren tNode;paren tNode->succeedi ngno de0= p;paren tNode->succeedi

14、ngno de1node;elseno de->parentnodep->parentno de;In sert_BTree2( p->parentno de,midKey, p,node)；else/插入右子树intj,p os;pos = 0;bool flag = false;/ 是否添加for(j = mid;j<c;j+)if(p->keyj<key)no de->keypos+ = p->keyj;else if(p->key|j>=key && flag =false)no de->key po s

15、+ = key;no de->keypos+ = p->keyj; flag = true; elseno de->keypos+ = p->keyj;p->keyj = 0;no de->n size = c-mid+1;no de->p are ntnode = p->p are ntno de;no de->no det ype = p->no det ype;no de->isleaf = p->isleaf;int midKey = middleNode( p,key); if(p->parentnode

16、= NULL)paren tNode_BTreeNode*createNode();p are ntNode->keyO = midKey;p are ntNode->isleaf = false;parentNode->nodetype = 0;/ 根节点paren tNode->n size = 1;paren tNode->parentnode = NULL;p->p are ntnode = no de->p are ntnode = paren tNode;paren tNode->succeedi ngno de0 = p;paren

17、 tNode->succeedi ngno de1= no de;else no de->p are ntnode = p->p are ntno de;In sert_BTree2( p->parentno de,midKey, p,node)； state = true;return state;*分裂内部节点*/boolspl iti nterNode(_BTreeNode*in ternode,_BTreeNode*succeedi ngno de,i ntsp lit po s,i nt key)bool state = false;_BTreeNode *p

18、 = interno de;if(p != NULL)存在父节点_BTreeNode *node = new _BTreeNode();int c = p->n size;int i;for(i = 0;i<c;i+)if(p->keyi>=key)break;构建新的子树节点_BTreeNode* node = createNode();if(sp lit po s>0 && sp lit po s<c)no de->succeedi ngno de0=succeedi ngno de;for(i=s plit po s;i<c

19、;i+)no de->keyi-s plit pos = p->keyi;no de->succeedi ngno dei-s plit po s+1 p->succeedi ngno dei+1;p->keyi=p->succeedi ngno dei+1=0; no de->n size = c-s plit pos;no de->isleaf = p->isleaf;no de->no det ype = p->no det ype;no de->p are ntnode = p->p are ntno de;

20、 p->n size = sp lit pos;if(p->no detype = 0)newBTreeNode* newroot_BTreeNode();n ewroot->key0 = key;n ewroot- >n size = 1;n ewroot- >no det ype = 0; n ewroot->isleaf = false; n ewroot->succeedi ngno de0 = p;n ewroot->succeedi ngno de1 = no de; p->no det ype = no de->no d

21、et ype = 1; p->p are ntnode = no de->p are ntnode = n ewroot;state = true;elsestateIn sert_BTree2( p->parentno de,key, p,no de); else if(splitpos = 0)int tmp = key;key = p->key0;no de->key0 = tmp;no de->succeedi ngno de0p->succeedi ngno de0;no de->succeedi ngno de1 succeedi n

22、gno de;no de->n size = 1;no de->isleaf = p->isleaf;no de->no det ype = p->no det ype;no de->p are ntnode = p->p are ntno de;int c = p->n size;int i;for(i=0;i<c-1;i+)p->keyi = p->keyi+1;p->succeedi ngno deip->succeedi ngno dei+1;p->succeedi ngno dec-1p->su

23、cceedi ngno dec;p->n size = c-1;if(p->no detype = 0)newBTreeNode*n ewroot_BTreeNode();n ewroot->key0 = key;n ewroot- >n size = 1;n ewroot- >no det ype = 0; n ewroot->isleaf = false; n ewroot->succeedi ngno de0 = no de;n ewroot->succeedi ngno de1 = p; p->no det ype = no de-

24、>no det ype = 1;p->p are ntnode = no de->p are ntnode = n ewroot;state = true;elsestateIn sert_BTree2( p->parentno de,key, no de, p); else if(splitpos = c)int tmp = key;key = p->keyc-1;no de->key0 = tmp;no de->succeedi ngno de0p->succeedi ngno dec;no de->succeedi ngno de1

25、succeedi ngno de;no de->n size = 1;no de->isleaf = p->isleaf;no de->no det ype = p->no det ype;no de->p are ntnode = p->p are ntno de; int c = p->n size;int i;p->keyc-1 = 0;p->succeedi ngno dec = 0;p->n size = c-1;if(p->no detype = 0)newBTreeNode* newroot_BTreeNod

26、e();n ewroot->key0 = key;n ewroot- >n size = 1;n ewroot- >no det ype = 0;n ewroot->isleaf = false;n ewroot->succeedi ngno de0 = p;n ewroot->succeedi ngno de1 = no de; p->no det ype = no de->no det ype = 1; p->p are ntnode = no de->p are ntnode = n ewroot;state = true;el

27、sestateIn sert_BTree2( p->parentno de,key, p,no de);return state;'*删除节点*删除节点N后，如果N节点的个数少于最少 值，先从左右兄弟借，然后再合并；*当左兄弟（或右兄弟）的键个数大于最小值, 且N节点个数小于最小值时，从左兄弟（或右 兄弟）借一个给N*当无处可借时，则与左兄弟（或右兄弟）合 并，合并后父节点需调整。*/bool Delete_Node（_BTreeNode *n ode,i nt key）bool state = false;_BTreeNode *p = node;if(p->isleaf

28、)/node 为叶子节点int c = p->n size;int spo s,e po s,i;spos = epos = -1;for(i = 0;ivc;i+)if(p->keyi = key && spos = -1)spos = i;else if(p->keyi > key && epos = -1) epos = i;break;if(spos = -1)/没找到 key込ods sod H z一SUAdM + sod Npou6u 一 p oonsAd n + sodsNpou6u 一 p oonsAd 三 + sodMM

29、Ad H = + sodsMMAd(+xovxsod H 一)04万ods H z_SUAd6 H 曰pou6u一poonsAd6 H DM孕d(+xovxsods H 一)04A雯 殴屛if唳蕪sods W/(L hh sod)七s©um 玄-国H 2e4sstate = checkJoin(p);/检查是否要合并else/node为非叶子节点int c = p->n size;int i;/bool flag = false;找到第一个大于等于key的键，然后顺着 向下找for(i = O;ivc;i+)if(p->keyi = key)Delete_Node (p-

30、>succeedi ngno dei+1,key); break;else if(p->keyi > key)Delete_Node( p->succeedi ngno dei,key); break;if(i = c)state = false; return state;state = true;return state;'*检查节点是否需要合并*/ bool checkJo in (_BTreeNode *no de)bool state = false;_BTreeNode *p = no de;_BTreeNode *left = fin dBroth

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

32、gt;succeedi ngno dei+2p->succeedi ngno dei+1;p->succeedi ngno de1p->succeedi ngno de0;p->key0 = left->keyleft->n size - 1;p->succeedi ngno de0left->succeedi ngno deleft- >n size; left->keyleft-> nsize-1 = 0; left->succeedi ngno deleft- >n size = NULL; left- >

33、;n size-;p->n size+;int pos = findPos(p);if(pos = -1) return false;_BTreeNode *fatherNode = p->parentnode;如果是叶子节点，则将父节点对应键换为 该节点的最小键if(p->isleaf)fatherNode->key pos =p->key0;如果非叶节点，则将父节点对应键与该节 点的最小键对换else int tmp = fatherNode->key po s; fatherNode->key pos = p->key0; p->ke

34、y0 = tmp;elseif(p->n size< MIN_CNT &&right- >n size > MIN_CNT)/p节点的键数小于最小节点数，且右兄弟键 数大于最小节点数，则借其右兄弟第一个键及节 点指针int i;int c = p->n size;p->keyc = right->key0;p->succeedi ngno dec+1 left->succeedi ngno de0;for(i=0;i<left- >n size;i+)left->keyi = left->keyi+1

35、; left->succeedi ngno deiIeft->succeedi ngno dei+1;left->keyleft-> nsize-1 = 0;left->succeedi ngno deleft- >n size = NULL; left- >n size-;p->n size+;int pos = findPo s(right);if(pos = -1)return false;_BTreeNode *fatherNode = p->parentnode;如果是叶子节点，则将父节点中右兄弟对 应键换为其右兄弟的最小键if(

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

37、)int c = p->n size;for(i = 0;i<c;i+)left->keyleft- >n size + i = p->keyi;left->succeedi ngno deleft->n size + i= p->succeedi ngno dei;left->n size += p->n size;int pos = findPo s(left);statedelete Paren tNode( p->parentno de, po s);state &= deleteNode( p);state &

38、amp;= checkJoi n(left->parentno de); elseint c = p->n size;left->keyleft- >n size p->succeedi ngno de0->key0;for(i = 0;i<c;i+)1 left->keyleft-> nsize+ i +p->keyi;left->succeedi ngno deleft->n size1 = p->succeedi ngno dei;c + 1left->succeedi ngno deleft- >

39、n size +=p->succeedi ngno dec;left->n size += (c + 1);state &= deleteNode( p);state &= checkJoi n(left->parentno de);else if(p->n size < MIN_CNT && right- >n size < MIN_CNT)本节点及右兄弟都小于最小节点数，则与 右兄弟合并int i;if(p->isleaf)int c = right->n size;for(i = 0;i<c;i+)p->keyleft->n size + i = nght->keyi;p->succeedi ngno deleft->n size + i right->succeedi ngno dei;p->n size += right- >n size;int pos = findPos(p);st