您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 中间结点 >

实现B-树的相关运算算法

发布时间:2019-07-02 09:20 来源:未知 编辑:admin

  B-tree即B树,B即Balance,平衡的意思。B-树是一种多路搜索树(并不一定是二叉的)。

  当查找的文件较大,且存放在磁盘等直接存取设备中时,为了减少查找过程中对磁盘的读写次数,提高查找效率,基于直接存取设备的读写操作以页为单位的特征。

  1970年,R.Bayer和E.M.McCreight提出了一种称之为B-树的多路平衡查找树,在文件系统中有所应用,主要用作文件的索引。它是一种平衡的多叉树,称为B树(或B-树、B_树),适合在磁盘等直接存取设备上组织动态的查找表。

  B-树中所有结点中孩子结点个数的最大值称为B-树的阶,通常用m表示,从查找效率考虑,一般要求m=3。

  一棵m阶B-树或者是一棵空树,或者是满足以下条件的m(m=3)叉树:

  (1)根结点只有1个,关键字字数的范围[1,m-1],分支个数取值范围[2,m]

  (3)每一个叶子节点都包含k-1个元素,其中 m/2 = k = m,即每一个叶子结点最多包含m-1个关键字

  (4)所有的叶子结点都位于同一层,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。即所有叶子节点具有相同的深度,等于树高度。如一棵四阶B-树,其深度为4

  (5)每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划

  B-树的查找类似二叉排序树的查找,所不同的是B-树每个结点上是多关键码的有序表,在到达某个结点时,先在有序表中查找,若找到,则查找成功;否则,到按照对应的指针信息指向的子树中去查找,当到达叶子结点时,则说明树中没有对应的关键码。

  给出如下的一棵4阶(B-树中所有结点中孩子结点个数的最大值)的B-树结构:

  1)从根结点出发,发现根结点a有1个关键字为35,其中4535,往右子树走,进入结点c

  3)发现结点g有3个关键字,其中34547,所以继续往下走,发现进入了结束符结点:F,所以45不在B-树中

  由于B- 树通常存储在磁盘上, 则前一查找操作是在磁盘上进行的, 而后一查找操作是在内存中进行的,即 在磁盘上找到指针p 所指结点后, 先将结点中的信息读入内存, 然后再利用顺序查找或折半查找查询等于K 的关键字。显然, 在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多。

  因此, 在磁盘上进行查找的次数、即待查找关键字所在结点在B-树上的层次数, 是决定B树查找效率的首要 因素,对于有n个关键字的m阶B-树,从根结点到关键字所在结点的路径上路过的结点数不超过:

  1)使用查找算法查找出关键字的插入位置,如果在B-树中查找到了关键字,则直接返回。否则,它一定会失败在某个最底层的终端结点上。

  2)然后,判断那个终端结点上的关键字数量是否满足:n=m-1,如果满足的话,直接在该终端结点上添加一个关键字,否则,需要产生结点的“分裂”。

  分裂的方法是:生成一新结点。把原结点上的关键字和需要插入的值key按升序排序后,从中间位置把关键字(不包括中间位置的关键字)分成两部分。左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过(m-1),则要再分裂,再往上插。直至这个过程传到根结点为止。

  此时如图所示,在插入的终端结点中,它的关键字数已经超过了m-1=2,需要对结点进分裂,先对关键字排序,得到:26 30 37 ,所以左部分为(不包括中间值):26,中间值为:30,右部分为:37,左部分放在原来的结点,右部分放入新的结点,而中间值则插入到父结点,并且父结点会产生一个新的指向子树的指针,指向新的结点的位置,如下图所示:

  此时如图所示,在插入的终端结点中,它的关键字数已经超过了m-1=2,需要对结点进分裂,先对关键字排序,得到:61 70 85,所以左部分为(不包括中间值):61,中间值为:70,右部分为:85,左部分放在原来的结点,右部分放入新的结点,而中间值则插入到父结点,如下图所示:

  当分裂完后,发现之前的那个结点的父亲结点的度为4,说明它的关键字数超过了m-1,所以需要对其父结点进行“分裂”操作,得到如下的结果:

  到了这里,需要继续对父亲结点进行分裂操作,因为它的关键字数超过了:m-1

  此时,根结点关键字数量超过m-1,需要对父亲结点进行分裂操作,但是根结点不存在父亲结点,需要重新创建根结点。

  1、利用B-树的查找算法找出该关键字所在的结点,然后根据 k(需要删除的关键字)所在结点是否为叶子结点有不同的处理方法。如果没有找到,则直接返回。

  2、若该结点为非叶子结点,且被删关键字为该结点中第i个关键字key[i],则可从指针son[i]所指的子树中找出最小关键字min_key,代替key[i]的位置,然后在叶子结点中删去min_key。

  1、如果被删关键字所在结点的原关键字个数n=[m/2] ( 上取整),说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单,只需删除对应的关键字:k和指针:A 即可。

  关键字的个数不小于(向上取整:不管四舍五入的规则, 只要后面有小数前面的整数就加1)[m/2],如下图删除关键字:12

  2、如果被删关键字所在结点的关键字个数n等于( 向上取整)[ m/2 ]-1,说明删去该关键字后该结点将不满足B-树的定义,需要调整。

  如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 向上取整)[m/2]-1。则可将右兄弟(或左兄弟)结点中最小关键字(或最大的关键字)上移至双亲结点。而将双亲结点中小(大)于该上移关键字的关键字下移至被删关键字所在结点中。

  关键字个数n等于( 向上取整)[ m/2 ]-1,而且该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 向上取整)[m/2]-1。

  如上图所示,要删除关键字50,需要把50的右兄弟中最小的关键字:61上移到其父结点,然后替换小于61的关键字53的位置,53则放至50的结点中。得到如下的结果:

  3、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于(向上取整)[m/2]-1。假设该结点有右兄弟,且其右兄弟结点地址由双亲结点中的指针Ai所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起,合并到 Ai所指兄弟结点中(若没有右兄弟,则合并至左兄弟结点中)。

  关键字个数n等于( 向上取整)[ m/2 ]-1,而且被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于(向上取整)[m/2]-1

  如上图所示,要删除关键字53,就要把53所在结点的其他关键字(这里没有其他关键字了)和父亲结点的关键字61一起合并到关键字70所在的结点。得到如下所示的结果:

  *        编写程序实现B-树的相关运算,在此基础上完成如下功能:

  *    2、在b中分别删除关键字为8和1的结点,并以括号表示法输出删除后的B-树。

  *   字等于k;否则标志tag = 0,等于k的关键字应插入在指针pt

  *       将结点q分成两个结点,前一半保留,后一半移入新生结点ap

  *       关键字删除后,调整B-树,找到一个关键字将其插入到p-ptr[i]中

  *       在结点p中查找关键字key的位置i,成功时返回1,否则返回0

  *       从B-树root中删除关键字key,若在一个结点中删除指定的关键字后

  1.B树  在笔者上篇文章中,我们说到二叉查找树的时间复杂度最好情况为,最差情况为。最差情况是所有的数据全部在一端时,那怎样避免出现这种情况,让二叉查找树所有查找的时间复杂度均为呢,为了达到这一目标,...博文来自:梦的天空一片蓝

  B-树B-树是一种多路搜索树(并不一定是二叉的)1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。一棵m阶B树(bala...博文来自:水越帆的博客

  一、定义B树是一种平衡的多分树,通常我们说m阶的B树,它必须满足如下条件:(1)每个结点至多有m个子结点;(2)除根结点和叶结点外,其它每个结点至少有ceil(m/2)个子结点;(3)根结点至少有两个...博文来自:Programming is an art form.

  B树       即二叉搜索树:      1.所有非叶子结点至多拥有两个儿子(Left和Right);      2.所有结点存储一个关键字;      3.非叶子结点的左指针指向小于其关键字的子树...博文来自:cuterabbitbaby的博客

  发布一个B-树的代码 代码下载:树网上的代码很象不是很多,关于它的原理我觉得没有必要要谈了,书上网上太多了。这里我花了几天的时间写...博文来自:BlueDog专栏

  B树的定义B树是一种平衡的多路查找树。一颗m阶B树,或为空树,或为满足下列特性的m叉树。(1)树中每个结点最多含有m棵子树;(2)若根结点不是叶子结点,则至少有两颗子树;(3)除根之外的所有非终端结点...博文来自:geek_jerome的博客

  B-树的定义B-树的查找B-树的插入操作B-树的删除操作B+树博文来自:time-space的博客

  (1)树中每个结点至多有m棵子树。【解释:因为树的阶是m,所有这个是必然】(2)若根结点不是叶子节点,则至少有两棵子树。(3)除根结点之外的所有非叶子结点至少有⌈m/2⌉棵子树。【解释:第一条是用来限...博文来自:根号三

  该代码是根据算法导论中B树的性质,设计方法编写的功能完善的c代码,内带注释,比较容易看懂,并在此基础上编写自己的小型数据库。

  本文对传统的B- 树/B+ 树插入算法进行改进, 提出了B- 树/ B+ 树的批量插入的算 法,在理论上估计了该算法的复杂度, 并进行了比较实验. 实验结果表明: 本算法在对大批量的关 键字建立索引时

  M阶的B-tree是一棵具有下列结构特性的树:(1)树的根或者是一片树叶,或者其儿子树在2到M之间。(2)除根外,所有非树叶节点的儿子数在[M/2]到M之间。(符号[]表示向上取整)(3)所有树叶都在...博文来自:Coding365

  B/B+/B*树采用多叉树结构降低树深度,主要用在磁盘文件系统与数据库。参考自:1))博文来自:mick_seu的博客

  B-树是一种平衡的多叉树,一颗M阶(M2)的B树,是一颗平衡的M路平衡搜索树,可以是空树或者满足下列性质:1.根节点至少有两个孩子2.每个非根节点有[[M/2],M]个孩子3.每个非根节点有[[M/...博文来自:no_name_sky的博客

  B-树 1.多路平衡查找多路搜索树具体地如图8.10所示,比如可以两层为间隔,将各节点与其左、右孩子合并为“大节点”,每个“大节点”拥有四个分支,故称作四路搜索树。一般地,以k层为间隔如此重组,可将二...博文来自:amoscykl的博客

  一、B-树的定义(适合查找的平衡的多叉树。)一颗M阶(Mgt;2)的B-树,是一颗平衡的M路平衡搜索树,可以是空树或者满足B-树的性质二、B-树的性质?(1)根节点至少有两个孩子(2)每个非...博文来自:apt1203JN的博客

  算法导论的课要完成一个小课题,选了B树,花了挺长时间弄完,之前写了几个简单的排序,发现这递归是真的牛批啊。代码部分参考了这位博主。在写前面的插入那一大块,书上有伪代码可以对着写。但是后面的删除部分没有...博文来自:andefine的博客

  二叉树的各种基本运算码文不易,如果帮助到您,希望您可以下载一个压缩包,与您无害,与我有益谢谢支持原创。  欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正错误回答问题。在次谢谢大...博文来自:Logic

  B-树B+树定义与简单的操作B-树的定义节点的孩子节点的最大数称为阶用m表示所有的叶子节点在同一层,并且不带信息每个节点最多含有m颗子树,最多含有m-1个关键字根节点不是终端节点那么根节点至少有两个子...博文来自:JJ_HH

  现代计算机中,在内存与外存(磁盘)组成的二级存储系统中,数据全集往往存放于外存中,计算过程中则可将内存作为外存的高速缓存,存放最常用数据项的复本。借助高效的调度算法,如此便可将内存的“高速度”与外存的...博文来自:不能说的秘密的博客

  B-树是一种平衡的多路查找树,它在文件系统中很有用。[1]B-树主要用作文件的索引,因此它的查找涉及外存的存取。[1]B-树适用于:当文件很大时,索引表(树表)本身也在外存,则查找索引时需多次访问外存...博文来自:weixin_41053675的博客

  B树的定义:B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树结构如下:其中,m是B树的阶,m=...博文来自:cyq6239075的博客

  前言博客编写人:Willam博客编写时间:2017/3/27博主邮箱:(有志同道合之人,可以加qq交流交流编程心得)1、背景知识下面这段摘抄自博客:(从B树、B+树、...博文来自:William

  关于B+树的基本定义,随便一本数据结构的书或者算法导论中都有,就不做介绍了。虽然网上和书本上都有很多对B+树的介绍,但是有很多资料对于B+树的操作或者介绍不全,或者有描写错误的地方,我这里参考这位大神...博文来自:popvip44的博客

  在阅读本篇博客前请先阅读《数据结构和算法B-树详细分析》B+树是由B树变来的,B+树和B树有这样的区别:B+树的非叶子节点不记录数据本身,只记录引用的连接,并且结点中仅含有其子树中的最大(或最小)关...博文来自:挖坑埋你

  什么是B-树呢?B-树全名BalanceTree,读做B树(中间的-,只是分隔作用,不要读做B减树哦)。#B树的特征B树首先它也是属于树结构,除了树结构的节点有序、查找高效外,还有以下特性。以一个...博文来自:卖克的专栏

  数据结构与算法分析——c语言描述第四章树 B-树好久没更新博客,这7天断断续续写B树,学汇编,学计算机组成原理。B树好难啊,还没写完。只写了25%。。。插入剩下两种情况没写:1.祖父未满,父亲满,儿子...博文来自:wwj

  经常不写博客感觉有些知识都有些模糊,闹了许多笑话。现在开始将自己之前接触到的学习过的,还有正准备学习研究的记录下来。方便自己回看,也便于交流。今天看到了一种新的搜索结构B-树。之前刚开始接触二叉树时感...博文来自:Dream_JW的博客

  搜索树(SearchTree)是一个很重要的数据结构。搜索树包括:二叉搜索树、平衡树、红黑树、B-树。今天我们的主角是B-树。在大数据时代,B-树成为一个非常热的数据结构。因为搜索树是进行数据查找非常...博文来自:热情de马金的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的)nn最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦!nnnn//jsn...博文来自:Websites

  :做寻找和输出的那个算法时,为什么可以找到多条路径呀?因为这个“visited[xi][yi]=0”吗?可是为什么呀,不理解。。。

http://cemonstyle.com/zhongjianjiedian/215.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有