加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

B-树

(2013-08-27 23:07:50)
标签:

b-树

算法

查找

删除

定义

it

分类: 数据结构

1、B-树定义

B-树通过降低树的高度来达到最小化记录访问次数的目的。首先在B-树中除了叶子结点外,所有非终端结点没有空子树,这样将关键字划分为子集是最高效的;其次,所有叶子结点在同一层,这样所有的查找将在相同的查找次数后终止。

一棵m阶的B-树,或为空树,或为满足下列特性的m路查找树:

(1)所有的叶子结点都出现在同一层次上,并且不含任何信息;

(2)除了根结点之外,树中所有的非终端结点至多有m棵子树,至少有棵子树;

(3)在每个非终端(内部)结点中,关键字的个数为非空子结点个数减1,这些关键字以查找树的形式将子结点中的关键字分开。非终端结点的结构如下:

(n,P0,K1,P1,K2,P2,…,Kn,Pn)

其中,Ki(1≤i≤n)为关键字,且满足Ki<Ki+1;Pi(0≤i≤n)为指向子树根结点的指针,且Pi所指子树上所有结点的关键字均小于Ki+1或大于Ki;n()为关键字的个数(或n+1为子树个数)。

(4)若根结点不是叶子结点,则至少有两棵子树。

2、B-树的查找算法

实现在B-树查找的C语言算法如算法6-13所示。在该算法中查找关键字并确定目标关键字位置的功能由辅助函数SearchNode完成,该函数返回一个布尔值和targetpos,其中布尔值表示查找是否成功,如果成功,targetpos中存放目标关键字位置。

 

 BTree SearchBTree(BTree root,KeyType target,int *targetpos)

{

//在m阶B-树root上查找目标关键字target

  if (!root)

      return NULL;

  else if (SearchNode(root, target ,targetpos))

    return (ro ot);

    else

       return(SearchBTree(root->branch[*targetpos],target,targetpos));

 }

  

Boolean SearchNode(BTree curr,KeyType target, int *pos) {

//在结点中查找关键字target,返回目标关键字的位置或需要继续查找的子树指针

if (LT(target,curr->key[1]))

{*pos = 0;   return FALSE;}

else {

 for(*pos=curr->keynum;LT(target,curr->key[*pos]&&*pos>1; (*pos)--);

return(EQ(target,curr->key[*pos]));

}

       }

3、实现B-树插入的方法

由于B-树要求所有的叶子结点出现在最后一层,因而相对于二叉查找树的插入操作,B-树不允许在叶结点上增长结点,由此在B-树上插入一个关键字时,只能插入到非终端结点上,并且插入到最低层的非终端结点上。同时,由于B-树的非终端结点对关键字的个数有一定的限制,即关键字个数n满足条件:,因此在插入关键字的过程中,有可能造成某个结点的关键字个数超过m-1,表明结点已满,则这个结点将在同一层被分成两个结点。一般情况下,结点分解方法是:以中间关键字为界把结点一分为二成为两个结点,并把中间关键字向上插入到双亲结点上,若双亲结点已满,则采用同样方法继续分解。最坏情况下,一直分解到树根结点,这时B-树高度增加1。

结点的分解可形式地描述如下:

假设*p结点中已有m—1个关键字,当插入一个关键字之后,结点中含有信息为:

      m,P0,(Kl,P1),…,(Km,Pm)

且其中         Ki < Ki+1,    l≤i≤m

此时可将*p结点分裂为*p和*p′两个结点,其中*p结点中含有信息:

    ,P0,(,),…,(,)

*p′结点中含有信息:

    ,,(,),…,(,)

而关键字和指针*p′一起插入到*p的双亲结点中。

4、B-树删除的实现方法

若在B-树上删除一个关键字,则首先应找到该关键字所在结点,并从树中删除之。若该结点为最下层的非终端结点,且其中的关键字数目不少于,则删除完成,否则要进行“合并”结点的操作。假设B-树的深度为h+1,下面分四种情况讨论关键字的删除。

    (1)若被删除的关键字在B-树的第h层上的某个结点中,并且该结点的关键字个数大于,则直接删除该关键字即可。例如,从图6-18(a)所示的B-树上删除关键字10,删除后的B-树如图6-18(b)。

(2)若被删除的关键字在B-树的第h层上的某个结点中,并且该结点的关键字个数等于,若其左(右)兄弟结点的关键字个数大于,则把左(或右)兄弟结点中的最大(或最小)的关键字上移到其双亲结点中,同时将双亲结点中大于(或小于)上移关键字的关键字下移到被删除关键字的结点中。如图6-18(b)中删除关键字50,需要将其右兄弟结点中最小的关键字61上移*e结点中,而将*e中的关键字53移到*f中,从而使*f和*g中的关键字个数均不小于,如图6-18(c)所示。

(3)被删关键字在B-树的第h层上的某个结点中,并且该结点及其相邻的兄弟结点中的关键字数目均等于。假设该结点有右兄弟,且其右兄弟结点地址由双亲结点中的指针Pi所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起,合并到Pi所指兄弟结点中(若没有右兄弟,则合并至左兄弟结点中)。例如从图6-17(c)所示B-树上删去53,则应删去*f,并将*f中的剩余信息(指针“空”)和双亲*e结点中的61一起合并到右兄弟结点*g中。删除后的树如图6-18(d)所示。如果因此使双亲结点中的关键字数目小于,则依次类推。例如,在图6-18(d)的B-树中删去关键字36之后,双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,如图6-18(e)所示。

(4)若被删除的关键字在B-树的第l(1≤l<h)层上的某个结点中,设被删关键字为所在结点的第i个关键字,则将指针Pi所指结点中的最小关键字放在它的位置上(或将Pi-1所指结点中的最大关键字放在它的位置上)。在图6-17(a)中,删除关键字53后结果如图6-18(f)。

B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时,若非终端结点上的关键字等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+树,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。B+树不仅对查找单个关键字的查询非常有用,而且对查找键值在某个范围的查询也很有用。例如,在B+树上找出范围[a,b]之间的所有关键字值。具体做法:通过一次查找来找出关键字a,不管它是否存在,我们都可以到达可能出现a的叶子结点,然后在叶子结点中查找关键字值等于a或大于a的那些关键字,我们所找到的每个关键字都有一个指针指向相应的记录,这些记录的关键字在所需要的范围。如果我们在当前结点中没有发现大于b的关键字,我们就可以使用当前叶子结点的最后一个指针找到下一个叶子结点,并继续进行同样的处理,直到在某个叶子结点中找到大于b的关键字,我们停止查找。

B+树的插入仅在叶子结点上进行,当结点中的关键字个数大于m时要分裂成两个结点它们所含关键字的个数分别为和。并且,它们的双亲结点中应同时包含这两个结点中的最大关键字。B+树的删除也仅在叶子结点进行,当叶子结点中的最大关键字被删除时,其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于时,其和兄弟结点的合并过程亦和B-树类似。

对于一般数据库,其B+树高度只需三层,除非数据库极大。因此,对B+树查找需要比较的关键字个数较少,查找效率较高。并且如果每个叶子结点中包含的关键字个数m值较大,比如10或更大,那么,分解及合并结点的情况将会很少。即使这样操作是必须的,绝大多数都局限在叶子结点,因此只有两个相邻的叶子结点和它们的双亲结点受影响。所以,基本上可以忽略B+树重组时的I/O开销。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有