精华内容
下载资源
问答
  • b*树
    万次阅读 多人点赞
    2019-08-17 14:33:46

    B树、B-树、B+树、B*树之间的关系

    B树

    B-树就是B树(可能有部分人会习惯上把B-树读为B减树,其实并不存在B减树,只是读法上的不同而已),B就是balanced,平衡的意思。B-树就是指的B树,特此说明一下。
    先介绍一下二叉搜索树。

    1. 顾名思义,二叉搜索树,即指最多拥有两个叉,这里的叉即为所有非叶子结点的儿子(Lift和Right);
    2. 所有的结点存储一个关键字;
    3. 非叶子结点的左指针指向小于其关键字的结点,右指针指向对于其关键字的结点,结构如下图:
      图片有点丑别在意,重点是对于二叉搜索树的理解

    二叉搜索树的搜索,从根结点开始,如果查询的关键字与结点关键字相等,则该结点为查询的结点,如果查询关键字比结点关键字小,则进入左子树,反之则进入右子树;如果左子树为空或者右子树为空,则返回查找不到响应的关键字;
    如果二叉搜索树的所有叶子结点的左右子树的树木保持一个平衡即左右子树个数大致相等的话,其搜索则更接近与二分查找;但是它相比连续内存空的二分查找的优点是:改变二叉搜索树的结构(添加或者删除)不需要大段的移动数据,甚至通常都是常数开销;
    如下图:
    红色字体代表插入数据,搜索二叉树在插入结点时,只要根据插入数据的大小查找出他应该插入的位置即可,然而当在一个有序数组插入一个数据的时候,需要查询出他的位置,然后将其添加,后面的数据索引加一,这样的一个完整操作,相比下来二叉树的优点很明显了。

    红色字体代表插入数据
    但是,当一个二叉树经历多次删除操作后,他就可能变换结构,如下图:
    在这里插入图片描述

    右边也是一个搜索二叉树,只不过不在平衡了,他的搜索功能也变成了线性的,同样的关键字可能导致不同的树结构索引,所以,在使用搜索二叉树时,还要烤炉尽可能让B树保持左图的结构,避免和右图类似,这也有事所谓的平衡问题了。

    实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法,即平衡二叉树;如何保持B树节点分布均匀的平衡算法就是平衡二叉树的关键所在,平衡算法是一种在二叉搜索树的插入和删除结点时的一种策略。即:在插入或删除的同时保持二叉搜索树的平衡。

    B树(B-树),是一种多路搜索树(并非二叉的):

    1. 定义任意非叶子节点最多可以有M个儿子节点;且M>2;
    2. 则根节点的儿子数为:[2,M];
    3. 除根节点为的非叶子节点的儿子书为[M/2,M];
    4. 每个结点存放至少M/2 - 1 (去上整)且至多M -1 个关键字;(至少为2);
    5. 非叶子结点的关键字个数 = 指向子节点的指针书 -1;
    6. 非叶子节点的关键字:K[1],K[2],K[3],…,K[M-1;且K[i] < K[i +1];
    7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
    8. 所有叶子结点位于同一层;

    如(M = 3)

    在这里插入图片描述
    B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果

    命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为

    空,或已经是叶子结点;

    B-树的特性:

    1. 关键字集合分布在整颗树中;
    2. 任何一个关键字出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束;
    4. 其搜索性能等价于在关键字全集内做一次二分查找;
    5. 自动层次控制;

    B+树

    B+树是B-树的变体,也是一种多路搜索树:

    1.其定义基本与B-树同,除了:

    2.非叶子结点的子树指针与关键字个数相同;

    3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

    5.为所有叶子结点增加一个链指针;

    6.所有关键字都在叶子结点出现;

    如:(M=3)
    在这里插入图片描述
    B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在

    非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

    B+树的特性:

    1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

    2.不可能在非叶子结点命中;

    3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

    B*树

    B树是B+树一种变形,它是在B+树的基础上,将索引层以指针连接起来,使搜索取值更加快捷。
    如下图(M = 3)
    在这里插入图片描述
    但是B
    树又在B+树的基础上产生了一系列的变化,如下:

    1. B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3代替B+树的1/2);
    2. B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
    3. *树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

    所以B*树相对于B+树,空间利用率上有所提高,查询速率也有所提高。

    总结:

    1. 二叉搜索树:二叉树,每个结点只存储一个关键字且值大于左子树,小于右子树。

    2. B(B-)树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树

    中出现,且只出现一次,非叶子结点可以命中;

    1. B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

    中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

    1. B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

    从1/2提高到2/3;

    更多相关内容
  • B树、B-树、B+树、B*树

    2010-01-25 09:36:57
    B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现...
  • B树、B-树、B+树、B*树简介

    万次阅读 2019-07-17 10:52:36
    B树 (二叉搜索树): 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; 如: B树的搜索,从根结点...

    B树 (二叉搜索树):

         1.所有非叶子结点至多拥有两个儿子(Left和Right);

          2.所有结点存储一个关键字;

          3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

          如:

          B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

          如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

          如:

          但B树在经过多次插入与删除后,有可能导致不同的结构:

                         


          右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;      

          实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;

    B-树

          是一种多路搜索树(并不是二叉的):

          1.定义任意非叶子结点最多只有M个儿子;且M>2;

          2.根结点的儿子数为[2, M];

          3.除根结点以外的非叶子结点的儿子数为[M/2, M];

          4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

          5.非叶子结点的关键字个数=指向儿子的指针个数-1;

          6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] <K[i+1];

          7.非叶子结点的指针:P[1], P[2], …,P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1],K[i])的子树;

          8.所有叶子结点位于同一层;

          如:(M=3)

                         

          B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

    B-树的特性:

          1.关键字集合分布在整颗树中;

          2.任何一个关键字出现且只出现在一个结点中;

          3.搜索有可能在非叶子结点结束;

          4.其搜索性能等价于在关键字全集内做一次二分查找;

          5.自动层次控制;

          由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

        

          其中,M为设定的非叶子结点最多子树个数,N为关键字总数;

          所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

          由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

    B+树

          B+树是B-树的变体,也是一种多路搜索树:

          1.其定义基本与B-树同,除了:

          2.非叶子结点的子树指针与关键字个数相同;

          3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

          5.为所有叶子结点增加一个链指针;

          6.所有关键字都在叶子结点出现;

          如:(M=3)

                                

      B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

          B+的特性:

          1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

          2.不可能在非叶子结点命中;

          3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

          4.更适合文件索引系统;

    B*树

          是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

                             

      B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

          B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

          B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

          所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

    小结

          B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点;

          B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点,所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

          B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

          B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

    展开全文
  • B+B*详解

    千次阅读 2020-07-02 15:15:14
    B+树和B*树详解 文章目录B+树和B*树详解一、B+树1.B+树的定义2.... 2)B+树与B树最大的不同是内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中。 3) m阶B+树表示了内部

    B+树和B*树详解

    一、B+树

    1.B+树的定义

    在这里插入图片描述

    2.性质

    B+树是B树的变体,也是一种多路搜索树,除了:

    • 1)B+树包含2种类型的结点:内部结点(也称索引结点)和叶子结点。根结点本身即可以是内部结点,也可以是叶子结点。根结点的关键字个数最少可以只有1个。
    • 2)B+树与B树最大的不同是内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中
    • 3) m阶B+树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树),阶数m同时限制了叶子结点最多存储m-1个记录
    • 4)内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
    • 5)每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接
      在这里插入图片描述

    3. B+树的插入操作

    • 1)若为空树,创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。

    • 2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入记录。插入后,若当前结点key的个数小于等于m-1,则插入结束

    • 否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第3步。

    • 3)针对索引类型结点:若当前结点key的个数小于等于m-1,则插入结束

    • 否则,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第3步。

    • 下面是一颗5阶B树的插入过程,5阶B数的结点最少2个key,最多4个key。

    • a)空树中插入5
      在这里插入图片描述

    • b)依次插入8,10,15
      在这里插入图片描述

    • c)插入16
      在这里插入图片描述

    • 插入16后超过了关键字的个数限制,所以要进行分裂。在叶子结点分裂时,分裂出来的左结点2个记录,右边3个记录,中间key成为索引结点中的key,分裂后当前结点指向了父结点(根结点)。结果如下图所示。
      在这里插入图片描述
      当然我们还有另一种分裂方式,给左结点3个记录,右结点2个记录,此时索引结点中的key就变为15。

    • d)插入17
      在这里插入图片描述

    • e)插入18,插入后如下图所示
      在这里插入图片描述

    • 当前结点的关键字个数大于5,进行分裂。分裂成两个结点,左结点2个记录,右结点3个记录,关键字16进位到父结点(索引类型)中,将当前结点的指针指向父结点
      在这里插入图片描述
      当前结点的关键字个数满足条件,插入结束。

    • f)插入若干数据后
      在这里插入图片描述

    • g)在上图中插入7,结果如下图所示
      在这里插入图片描述

    • 当前结点的关键字个数超过4,需要分裂。左结点2个记录,右结点3个记录。分裂后关键字7进入到父结点中,将当前结点的指针指向父结点,结果如下图所示。
      在这里插入图片描述

    • 当前结点的关键字个数超过4,需要继续分裂。左结点2个关键字,右结点2个关键字,关键字16进入到父结点中,将当前结点指向父结点,结果如下图所示。
      在这里插入图片描述
      当前结点的关键字个数满足条件,插入结束。

    4.B+树的删除操作

    • 如果叶子结点中没有相应的key,则删除失败。否则执行下面的步骤
    • 1)删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1,删除操作结束,否则执行第2步。
    • 2)兄弟结点key有富余(大于Math.ceil(m-1)/2 – 1),向兄弟结点借一个记录,同时用借到的key替换父结(指当前结点和兄弟结点共同的父结点)点中的key,删除结束。否则执行第3步。
    • 3)若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点,并删除父结点中的key(父结点中的这个key两边的孩子指针就变成了一个指针,正好指向这个新的叶子结点),将当前结点指向父结点(必为索引结点),执行第4步(第4步以后的操作和B树就完全一样了,主要是为了更新索引结点)。
    • 4)索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1,则删除操作结束。否则执行第5步
    • 5)兄弟结点有富余,父结点key下移,兄弟结点key上移,删除结束。否则执行第6步
    • 6)当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点,重复第4步。

    注意,通过B+树的删除操作后,索引结点中存在的key,不一定在叶子结点中存在对应的记录。

    • 下面是一颗5阶B树的删除过程,5阶B数的结点最少2个key,最多4个key。
    • a)初始状态
      在这里插入图片描述
    • b)删除22,删除后结果如下图
      在这里插入图片描述
      删除后叶子结点中key的个数大于等于2,删除结束
    • c)删除15,删除后的结果如下图所示
      在这里插入图片描述
    • 删除后当前结点只有一个key,不满足条件,而兄弟结点有三个key,可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9,删除结束。
      在这里插入图片描述
    • d)删除7,删除后的结果如下图所示
      在这里插入图片描述
    • 当前结点关键字个数小于2,(左)兄弟结点中的也没有富余的关键字(当前结点还有个右兄弟,不过选择任意一个进行分析就可以了,这里我们选择了左边的),所以当前结点和兄弟结点合并,并删除父结点中的key,当前结点指向父结点

    在这里插入图片描述

    • 此时当前结点的关键字个数小于2,兄弟结点的关键字也没有富余,所以父结点中的关键字下移,和两个孩子结点合并,结果如下图所示。
      在这里插入图片描述

    二、B*树

    1.概念

    是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
    在这里插入图片描述

    2.性质

    • B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);
    • B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;
    • B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
    • B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);
    • 如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
    • 所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

    3.总结

    1.B-/B树:

    关键字的数量比孩子的数量少一,M阶的B-/B树最多有M个孩子,M- 1个关键字。分裂的方式把关键字已经满的节点中的数据移动1/2到另一个节点

    2.B+树:

    B+树中关键字的数量和孩子的数量相等,在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引,遍历叶子节点就可以得到所有的数据;B+树总是到叶子结点才命中。M阶的B+树一个节点最少有M/ 2个关键字。分裂的方式把关键字已经满的节点中的数据拷贝1/2到另一个新节点

    3.B*树:

    在B+树基础上,为非叶子结点也增加链表指针,M阶的B树一个节点最少有M 2/3 个关键字,将结点空间的最低利用率从1/2提高到2/3分裂的方式是:如果它的下一个兄弟节点的关键字没满,就把关键字已经满的节点中的数据移动到兄弟节点当中;如果兄弟节点也满了,就在二者之间增加新节点,各复制1/3的数据到新节点当中

    展开全文
  • B树、B-树、B+树、B*树之间的关系

    万次阅读 多人点赞 2018-07-17 21:30:20
    B树  B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另...

    B树

          B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一种树。而事实上是,B-tree就是指的B树。特此说明。

    先介绍下二叉搜索树

           1.所有非叶子结点至多拥有两个儿子(Left和Right);

           2.所有结点存储一个关键字;

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

           如:

           

           二叉搜索树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;

    否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入

    右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

           如果二叉搜索树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树

    的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变二叉搜索树结构

    (插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

           如:

          

       但二叉搜索树在经过多次插入与删除后,有可能导致不同的结构:

     

       右边也是一个二叉搜索树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的

    树结构索引;所以,使用二叉搜索树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就

    是所谓的“平衡”问题;      

           实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树

    结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在二叉搜索树中插入和删除结点的

    策略;

    B树(B-树)

           是一种多路搜索树(并不是二叉的):

           1.定义任意非叶子结点最多只有M个儿子;且M>2;

           2.根结点的儿子数为[2, M];

           3.除根结点以外的非叶子结点的儿子数为[M/2, M];

           4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

           5.非叶子结点的关键字个数=指向儿子的指针个数-1;

           6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

           7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的

    子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

           8.所有叶子结点位于同一层;

           如:(M=3)

           B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果

    命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为

    空,或已经是叶子结点;

    B-树的特性:

           1.关键字集合分布在整颗树中;

           2.任何一个关键字出现且只出现在一个结点中;

           3.搜索有可能在非叶子结点结束;

           4.其搜索性能等价于在关键字全集内做一次二分查找;

           5.自动层次控制;

           由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少

    利用率,其最底搜索性能为:

        

           其中,M为设定的非叶子结点最多子树个数,N为关键字总数;

           所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

           由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占

    M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

     

     

    B+树

           B+树是B-树的变体,也是一种多路搜索树:

           1.其定义基本与B-树同,除了:

           2.非叶子结点的子树指针与关键字个数相同;

           3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树

    (B-树是开区间);

           5.为所有叶子结点增加一个链指针;

           6.所有关键字都在叶子结点出现;

           如:(M=3)

       B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在

    非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

           B+的特性:

           1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好

    是有序的;

           2.不可能在非叶子结点命中;

           3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储

    (关键字)数据的数据层;

           4.更适合文件索引系统;

      

    B*树

           是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

       B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3

    (代替B+树的1/2);

           B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据

    复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父

    结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

           B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分

    数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字

    (因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之

    间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

           所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

      

    小结

           二叉搜索树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于

    走右结点;

           B(B-)树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键

    字范围的子结点;

           所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

           B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

    中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

           B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

    从1/2提高到2/3;

    展开全文
  • B-B+以及B*的原理详解

    万次阅读 2018-10-20 16:47:37
    1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的...
  • 关于B树 B+树 B*树以及红黑树的理解

    万次阅读 多人点赞 2019-02-21 19:34:32
    1、首先要明白为什么有了AVL之后还会出现这么多的变种? 可以参考这个知乎有关几种的应用的回答: 作者:王伟豪 链接:https://www.zhihu.com/question/30527705/answer/52919336 来源:知乎 AVL:平衡...
  • B树B+树B*树原理及应用

    千次阅读 2017-12-03 19:23:23
    查找的时间复杂度O(log2N)与树的深度相关,因此降低树的高度自然对查找效率有所帮助,为了降低树的高度,可令每个节点存储多个元素,并将平衡二叉查找树拓展为平衡多叉查找树,这时神奇的B树就从石头里蹦出来了,B树...
  • B树-B+树-B*树谈到R树

    2012-10-04 23:38:04
    一个B树,B+树,B*树的详细讲解,可以作为初学者的一个学习资料。
  • B树、B-树、B+树、B*树 详细总结

    千次阅读 2018-07-11 12:03:22
    B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; B树的搜索,从根结点开始,如果...
  • 【数据结构】B树、B+树与B*树详解

    千次阅读 2017-07-21 11:05:28
    B树1.B树的定义 B树(B-tree)是对2-3树数据结构的扩展,又称为多路平衡查找树,它的一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同, B树是一种自平衡树数据结构,可以保持数据排序,它能够...
  • B树,B-树和B+树、B*树的区别

    万次阅读 2018-07-26 13:53:03
    B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这种直译不好,容易产生误解。如人们可能会以为B-树是一种树,而B树又是一种树。事实上,B-...
  • B树,B-树,B*树,B+和红黑树的区别

    万次阅读 2018-07-25 14:39:34
    B树  即二叉搜索树:  1.所有非叶子结点至多拥有两个儿子(Left和Right);  2.所有结点存储一个关键字;  3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;  如:    ...
  • 数据结构(三)、B树,B+树,B*树

    千次阅读 2020-08-04 21:32:06
    对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。
  • B-树详细分析及B树B-树B+树B*树概念

    万次阅读 多人点赞 2016-12-03 11:04:57
    B- 树是为了磁盘或其它存储设备而设计的一种多叉(下面你会看到,相对于二叉,B树每个内结点有多个分支,即多叉)平衡查找树。 B- 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下: 树中每个...
  • B-B+B*的优缺点比较

    万次阅读 2017-06-23 13:17:05
    首先注意:B树就是B-树,"-"是个连字符号,不是减号。  B-树是一种平衡的多路查找(又称排序)树,在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)  B+树有一个最大的好处,方便扫库,B树...
  • 特点:平衡二叉树是采用二分法思想把数据按规则组装成一个形结构的数据,用这个形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程遵循以下规则: (1)非叶子节点只能...
  • B树(B-树 B_树)、B+树、B*树

    千次阅读 2019-06-26 15:11:56
    B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一...
  • 因而,红黑树是相对是接近平衡的二叉树 四、B-树是一种多路搜索树(并不一定是二叉的) 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树: 1、根结点至少有两个...
  • 数据结构之B树、B+树、B*树

    千次阅读 多人点赞 2018-12-01 00:09:39
    二叉查找、AVL、红黑等都属于二叉树的范围,查找的时间复杂度是O(log 2N),与的深度相关,那么降低的深度自然会提高查找效率。 但是我们面对这样一个实际问题:大规模数据存储中,节点存储的元素数量...
  • B树、B+树、B*树谈MySQL索引

    万次阅读 2019-11-28 17:58:02
    动态查找主要有:二叉查找(Binary Search Tree),平衡二叉查找(Balanced Binary Search Tree),红黑(Red-Black Tree ),B-tree/B±tree/ B*-tree (B~Tree)。前三者是典型的二叉查找结构,其查找的时间...
  • B树、B-树、B+树、B*树的定义及区分
  • 二叉树与B树、B+树、B*树和2-3树

    千次阅读 2021-10-11 10:22:07
    12.1 二叉树与 B 12.1.1 二叉树的问题分析 二叉树的操作效率较高,但是也存在问题, 请看下面的二叉树 二叉树需要加载到内存的,如果二叉树的节点少,没有什么问题,但是如果二叉树的节点很多(比如 1 亿), 就...
  • B-B+B*详解

    万次阅读 多人点赞 2016-11-07 23:17:04
    1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的...
  • 关于B树的学习总结和B+树,B*树的简介

    千次阅读 多人点赞 2018-01-12 11:33:56
    B树,英文是B-tree,是一种平衡多路树,这个不叫B减树,就是B树B树是一种多路树。因为他的子节点不止2个,可以是多个。 B树是一种平衡树。所谓平衡树,指的是他的左右两个子树的高度差小于等于1,而且左右子树...
  • 平衡二叉树、B树、B+树、B*树

    万次阅读 2019-10-18 09:17:18
    平衡二叉树是采用二分法思维把数据按规则组装成一个形结构的数据,用这个形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程有以下规则: (1)非叶子节点只能允许最多...
  • B*索引——Oracle的默认索引结构

    千次阅读 2014-01-14 10:58:29
    1、B*索引 1.1 概述  B*索引是Oracle默认的索引结构。我们使用CREATE INDEX语句创建索引时,创建的就是B*索引。B*索引的结构一个二 叉,由根节点(root node)、分支部分(branch node)和叶子节点(leaf...
  • B-B+B*的区别

    万次阅读 2012-09-11 22:41:03
    1、二叉搜索  性质:所有非叶子结点至多拥有两个儿子(Left和Right);每个结点存储一个关键字;非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树。  搜索:从根结点开始,如果查询的...
  • 1、二叉查找的缺点 二叉查找,相信大家都接触过,二叉查找的特点就是左子树的节点值比父亲节点小,而右子的节点值比父亲节点大,如图 基于二叉查找的这种特点,我们在查找某个节点的时候,可以采取类似于...
  • 经典查找算法 --- B*

    千次阅读 2017-04-18 11:11:33
    B*-tree是B+-tree的变体,在B+的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B*中非根和非叶子结点再增加指向兄弟的指针;B*定义了非叶子结点关键字个数至少为(2/3)*M...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 906,980
精华内容 362,792
关键字:

b*树

友情链接: Calculator.rar