[转]B+树的结构和实现代码

wapysun

浏览: 21497581 次
性别:
来自: 杭州

最近访客更多访客>>

devcang

hunankeda110

辽东小小

apex53

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2012-06 ( 77)
2012-05 ( 587)
2012-04 ( 177)
更多存档...

B+树实现代码

来源：http://supercyber.139.com/article/253784.html

这个结构一般用于数据库的索引，综合效率非常高，像 Berkerly DB , sqlite , mysql 数据库都使用了这个算法处理索引。
如果想自己做个小型数据库，可能参考一下这个算法的实现，可能会对你有所帮助。

其中的注册很详细，不用再多说了。

/*btrees.h*/
/*
*平衡多路树的一种重要方案。
*在1970年由R.Bayer和E.McCreight发明。
*/
#defineM1
/*B树的阶，即非根节点中键的最小数目。
*有些人把阶定义为非根节点中子树的最大数目。
*/
typedefinttypekey;
typedefstructbtnode{/*B-Tree节点*/
intd;/*节点中键的数目*/
typekeyk[2*M];/*键*/
char*v[2*M];/*值*/
structbtnode*p[2*M+1];/*指向子树的指针*/
}node,*btree;
/*
*每个键的左子树中的所有的键都小于这个键，
*每个键的右子树中的所有的键都大于等于这个键。
*叶子节点中的每个键都没有子树。
*/

/*当M等于1时也称为2-3树
*+----+----+
*|k0|k1|
*+-+----+----+---
*|p0|p1|p2|
*+----+----+----+
*/
externintbtree_disp;/*查找时找到的键在节点中的位置*/
externchar*InsValue;/*与要插的键相对应的值*/

externbtreesearch(typekey,btree);
externbtreeinsert(typekey,btree);
externbtreedelete(typekey,btree);
externintheight(btree);
externintcount(btree);
externdoublepayload(btree);
externbtreedeltree(btree);
/*endofbtrees.h*/

/*******************************************************/

/*******************************************************/

/*btrees.c*/
#include
#include
#include"btrees.h"

btreesearch(typekey,btree);
btreeinsert(typekey,btree);
btreedelete(typekey,btree);
intheight(btree);
intcount(btree);
doublepayload(btree);
btreedeltree(btree);

staticvoidInternalInsert(typekey,btree);
staticvoidInsInNode(btree,int);
staticvoidSplitNode(btree,int);
staticbtreeNewRoot(btree);

staticvoidInternalDelete(typekey,btree);
staticvoidJoinNode(btree,int);
staticvoidMoveLeftNode(btreet,int);
staticvoidMoveRightNode(btreet,int);
staticvoidDelFromNode(btreet,int);
staticbtreeFreeRoot(btree);

staticbtreedelall(btree);
staticvoidError(int,typekey);

intbtree_disp;/*查找时找到的键在节点中的位置*/
char*InsValue=NULL;/*与要插的键相对应的值*/
staticintflag;/*节点增减标志*/
staticintbtree_level=0;/*多路树的高度*/
staticintbtree_count=0;/*多路树的键总数*/
staticintnode_sum=0;/*多路树的节点总数*/
staticintlevel;/*当前访问的节点所处的高度*/
staticbtreeNewTree;/*在节点分割的时候指向新建的节点*/
statictypekeyInsKey;/*要插入的键*/

btreesearch(typekeykey,btreet)
{
inti,j,m;
level=btree_level-1;
while(level>=0){
for(i=0,j=t->d-1;it->k[m])?(i=m+1):(j=m));
if(key==t->k){
btree_disp=i;
returnt;
}
if(key>t->k)/*i==t->d-1时有可能出现*/
i++;
t=t->p;
level--;
}
returnNULL;
}

btreeinsert(typekeykey,btreet)
{
level=btree_level;
InternalInsert(key,t);
if(flag==1)/*根节点满之后，它被分割成两个半满节点*/
t=NewRoot(t);/*树的高度增加*/
returnt;
}

voidInternalInsert(typekeykey,btreet)
{
inti,j,m;

level--;
if(level0){/*到达了树的底部:指出要做的插入*/
NewTree=NULL;/*这个键没有对应的子树*/
InsKey=key;/*导致底层的叶子节点增加键值+空子树对*/
btree_count++;
flag=1;/*指示上层节点把返回的键插入其中*/
return;
}
for(i=0,j=t->d-1;it->k[m])?(i=m+1):(j=m));
if(key==t->k){
Error(1,key);/*键已经在树中*/
flag=0;
return;
}
if(key>t->k)/*i==t->d-1时有可能出现*/
i++;
InternalInsert(key,t->p);

if(flag==0)
return;
/*有新键要插入到当前节点中*/
if(t->d2*M){/*当前节点未满*/
InsInNode(t,i);/*把键值+子树对插入当前节点中*/
flag=0;/*指示上层节点没有需要插入的键值+子树，插入过程结束*/
}
else/*当前节点已满，则分割这个页面并把键值+子树对插入当前节点中*/
SplitNode(t,i);/*继续指示上层节点把返回的键值+子树插入其中*/
}

/*
*把一个键和对应的右子树插入一个节点中
*/
voidInsInNode(btreet,intd)
{
inti;
/*把所有大于要插入的键值的键和对应的右子树右移*/
for(i=t->d;i>d;i--){
t->k=t->k[i-1];
t->v=t->v[i-1];
t->p[i+1]=t->p;
}
/*插入键和右子树*/
t->k=InsKey;
t->p[i+1]=NewTree;
t->v=InsValue;
t->d++;
}
/*
*前件是要插入一个键和对应的右子树，并且本节点已经满
*导致分割这个节点，插入键和对应的右子树，
*并向上层返回一个要插入键和对应的右子树
*/
voidSplitNode(btreet,intd)
{
inti,j;
btreetemp;
typekeytemp_k;
char*temp_v;
/*建立新节点*/
temp=(btree)malloc(sizeof(node));
/*
*+---+--------+-----+-----+--------+-----+
*|0|......|M|M+1|......|2*M-1|
*+---+--------+-----+-----+--------+-----+
*|||
*/
if(d>M){/*要插入当前节点的右半部分*/
/*把从2*M-1到M+1的M-1个键值+子树对转移到新节点中,
*并且为要插入的键值+子树空出位置*/
for(i=2*M-1,j=M-1;i>=d;i--,j--){
temp->k[j]=t->k;
temp->v[j]=t->v;
temp->p[j+1]=t->p[i+1];
}
for(i=d-1,j=d-M-2;j>=0;i--,j--){
temp->k[j]=t->k;
temp->v[j]=t->v;
temp->p[j+1]=t->p[i+1];
}
/*把节点的最右子树转移成新节点的最左子树*/
temp->p[0]=t->p[M+1];
/*在新节点中插入键和右子树*/
temp->k[d-M-1]=InsKey;
temp->p[d-M]=NewTree;
temp->v[d-M-1]=InsValue;
/*设置要插入上层节点的键和值*/
InsKey=t->k[M];
InsValue=t->v[M];

}
else{/*d*/
/*把从2*M-1到M的M个键值+子树对转移到新节点中*/
for(i=2*M-1,j=M-1;j>=0;i--,j--){
temp->k[j]=t->k;
temp->v[j]=t->v;
temp->p[j+1]=t->p[i+1];
}
if(d==M)/*要插入当前节点的正中间*/
/*把要插入的子树作为新节点的最左子树*/
temp->p[0]=NewTree;
/*直接把要插入的键和值返回给上层节点*/
else{/*(d/*把节点当前的最右子树转移成新节点的最左子树*/
temp->p[0]=t->p[M];
/*保存要插入上层节点的键和值*/
temp_k=t->k[M-1];
temp_v=t->v[M-1];
/*把所有大于要插入的键值的键和对应的右子树右移*/
for(i=M-1;i>d;i--){
t->k=t->k[i-1];
t->v=t->v[i-1];
t->p[i+1]=t->p;
}
/*在节点中插入键和右子树*/
t->k[d]=InsKey;
t->p[d+1]=NewTree;
t->v[d]=InsValue;
/*设置要插入上层节点的键和值*/
InsKey=temp_k;
InsValue=temp_v;
}
}
t->d=M;
temp->d=M;
NewTree=temp;
node_sum++;
}

btreedelete(typekeykey,btreet)
{
level=btree_level;
InternalDelete(key,t);
if(t->d==0)
/*根节点的子节点合并导致根节点键的数目随之减少，
*当根节点中没有键的时候，只有它的最左子树可能非空*/
t=FreeRoot(t);
returnt;
}

voidInternalDelete(typekeykey,btreet)
{
inti,j,m;
btreel,r;
intlvl;

level--;
if(level0){
Error(0,key);/*在整个树中未找到要删除的键*/
flag=0;
return;
}
for(i=0,j=t->d-1;it->k[m])?(i=m+1):(j=m));
if(key==t->k){/*找到要删除的键*/
if(t->v!=NULL)
free(t->v);/*释放这个节点包含的值*/
if(level==0){/*有子树为空则这个键位于叶子节点*/
DelFromNode(t,i);
btree_count--;
flag=1;
/*指示上层节点本子树的键数量减少*/
return;
}else{/*这个键位于非叶节点*/
lvl=level-1;
/*找到前驱节点*/
r=t->p;
while(lvl>0){
r=r->p[r->d];
lvl--;
}
t->k=r->k[r->d-1];
t->v=r->v[r->d-1];
r->v[r->d-1]=NULL;
key=r->k[r->d-1];
}
}
elseif(key>t->k)/*i==t->d-1时有可能出现*/
i++;
InternalDelete(key,t->p);
/*调整平衡*/
if(flag==0)
return;
if(t->p->dM){
if(i==t->d)/*在最右子树中发生了删除*/
i--;/*调整最右键的左右子树平衡*/
l=t->p;
r=t->p[i+1];
if(r->d>M)
MoveLeftNode(t,i);
elseif(l->d>M)
MoveRightNode(t,i);
else{
JoinNode(t,i);
/*继续指示上层节点本子树的键数量减少*/
return;
}
flag=0;
/*指示上层节点本子树的键数量没有减少，删除过程结束*/
}
}

/*
*合并一个节点的某个键对应的两个子树
*/
voidJoinNode(btreet,intd)
{
btreel,r;
inti,j;
l=t->p[d];
r=t->p[d+1];

/*把这个键下移到它的左子树*/
l->k[l->d]=t->k[d];
l->v[l->d]=t->v[d];
/*把右子树中的所有键值和子树转移到左子树*/
for(j=r->d-1,i=l->d+r->d;j>=0;j--,i--){
l->k=r->k[j];
l->v=r->v[j];
l->p=r->p[j];
}
l->p[l->d+r->d+1]=r->p[r->d];
l->d+=r->d+1;
/*释放右子树的节点*/
free(r);
/*把这个键右边的键和对应的右子树左移*/
for(i=d;it->d-1;i++){
t->k=t->k[i+1];
t->v=t->v[i+1];
t->p[i+1]=t->p[i+2];
}
t->d--;
node_sum--;
}
/*
*从一个键的右子树向左子树转移一些键，使两个子树平衡
*/
voidMoveLeftNode(btreet,intd)
{
btreel,r;
intm;/*应转移的键的数目*/
inti,j;
l=t->p[d];
r=t->p[d+1];
m=(r->d-l->d)/2;

/*把这个键下移到它的左子树*/
l->k[l->d]=t->k[d];
l->v[l->d]=t->v[d];
/*把右子树的最左子树转移成左子树的最右子树
*从右子树向左子树移动m-1个键+子树对*/
for(j=m-2,i=l->d+m-1;j>=0;j--,i--){
l->k=r->k[j];
l->v=r->v[j];
l->p=r->p[j];
}
l->p[l->d+m]=r->p[m-1];
/*把右子树的最左键提升到这个键的位置上*/
t->k[d]=r->k[m-1];
t->v[d]=r->v[m-1];
/*把右子树中的所有键值和子树左移m个位置*/
r->p[0]=r->p[m];
for(i=0;id-m;i++){
r->k=r->k[i+m];
r->v=r->v[i+m];
r->p=r->p[i+m];
}
r->p[r->d-m]=r->p[r->d];
l->d+=m;
r->d-=m;
}
/*
*从一个键的左子树向右子树转移一些键，使两个子树平衡
*/
voidMoveRightNode(btreet,intd)
{
btreel,r;
intm;/*应转移的键的数目*/
inti,j;
l=t->p[d];
r=t->p[d+1];

m=(l->d-r->d)/2;
/*把右子树中的所有键值和子树右移m个位置*/
r->p[r->d+m]=r->p[r->d];
for(i=r->d-1;i>=0;i--){
r->k[i+m]=r->k;
r->v[i+m]=r->v;
r->p[i+m]=r->p;
}
/*把这个键下移到它的右子树*/
r->k[m-1]=t->k[d];
r->v[m-1]=t->v[d];
/*把左子树的最右子树转移成右子树的最左子树*/
r->p[m-1]=l->p[l->d];
/*从左子树向右子树移动m-1个键+子树对*/
for(i=l->d-1,j=m-2;j>=0;j--,i--){
r->k[j]=l->k;
r->v[j]=l->v;
r->p[j]=l->p;
}
/*把左子树的最右键提升到这个键的位置上*/
t->k[d]=l->k;
t->v[d]=l->v;
l->d-=m;
r->d+=m;
}
/*
*把一个键和对应的右子树从一个节点中删除
*/
voidDelFromNode(btreet,intd)
{
inti;
/*把所有大于要删除的键值的键左移*/
for(i=d;it->d-1;i++){
t->k=t->k[i+1];
t->v=t->v[i+1];
}
t->d--;
}
/*
*建立有两个子树和一个键的根节点
*/
btreeNewRoot(btreet)
{
btreetemp;
temp=(btree)malloc(sizeof(node));
temp->d=1;
temp->p[0]=t;
temp->p[1]=NewTree;
temp->k[0]=InsKey;
temp->v[0]=InsValue;
btree_level++;
node_sum++;
return(temp);
}
/*
*释放根节点，并返回它的最左子树
*/
btreeFreeRoot(btreet)
{
btreetemp;
temp=t->p[0];
free(t);
btree_level--;
node_sum--;
returntemp;
}

voidError(intf,typekeykey)
{
if(f)
printf("Btreeserror:Insert%d! ",key);
else
printf("Btreeserror:delete%d! ",key);
}

intheight(btreet)
{
returnbtree_level;
}

intcount(btreet)
{
returnbtree_count;
}
doublepayload(btreet)
{
if(node_sum==0)
return1;
return(double)btree_count/(node_sum*(2*M));
}
btreedeltree(btreet)
{
level=btree_level;
btree_level=0;
returndelall(t);

}
btreedelall(btreet)
{
inti;
level--;
if(level>=0){
for(i=0;it->d;i++)
if(t->v!=NULL)
free(t->v);
if(level>0)
for(i=0;it->d;i++)
t->p=delall(t->p);
free(t);
}
returnNULL;
}

/*endofbtrees.c*/

B+树的组织结构

来源：http://www.blogjava.net/titan/articles/30387.html

1、B+树索引的总体结构
①B⁺树索引是一个多级索引，但是其结构不同于多级顺序索引；
②B⁺树索引采用平衡树结构，即每个叶结点到根的路径长度都相同；
③每个非叶结点有到n个子女，n对特定的树是固定的；
④B⁺树的所有结点结构都相同，它最多包含n-1个搜索码值K1、K2、…、Kn-1，以及n个指针P1、P2、…、Pn，每个结点中的搜索码值按次序存放，即如果i<j class="part">图8-3-1所示。<br></j>

图8-3-1：B⁺树的结点结构

2、B⁺树索引的叶结点
①指针Pi(i=1,2,…,n-1)指向具有搜索码值Ki的一个文件记录或一个指针（存储）桶，桶中的每个指针指向具有搜索码值Ki的一个文件记录。指针桶只在文件不按搜索码顺序物理存储时才使用。指针Pn具有特殊的作用；
②每个叶结点最多可有n-1个搜索码值，最少也要有

个搜索码值。各个叶结点中搜索码值的范围互不相交。要使B+树索引成为稠密索引，数据文件中的各搜索码值都必须出现在某个叶结点中且只能出现一次；
③由于各叶结点按照所含的搜索码值有一个线性顺序，所以就可以利用各个叶结点的指针Pn将叶结点按搜索码顺序链接在一起。这种排序能够高效地对文件进行顺序处理，而B⁺树索引的其他结构能够高效地对文件进行随机处理，如图8-3-2所示。

图8-3-2：B+树索引的叶结点结构示例