简要叙述b树和b+树的区别_b+树和b-树的区别

简要叙述b树和b+树的区别_b+树和b-树的区别二三树、B树(多路平衡查找树)、B+树二三树介绍(2-3树的理解对红黑树和B类树的理解大有帮助)1、满足二分搜索树的基本性质2、结点可以存放一个素或两个素,对于存放一个素的节点,和二分搜索树一样,左小右大;对于存放两个素的结点,左小中中右大,即左子树存放比它们都小的素,右子树存

二三树、B树(多路平衡查找树)、B+树   二三树介绍(2-3树的理解对红黑树和B类树的理解大有帮助)   1、满足二分搜索树的基本性质2、结点可以存放一个素或两个素,对于存放一个素的节点,和二分搜索树一样,左小右大;对于存放两个素的结点,左小中中右大,即左子树存放比它们都小的素,右子树存放比它们都大的素,中间结点存放在他们中间的素。3、2-3树是绝对平衡的二分搜索树(从根节点到任意一个叶子结点所经过的结点一定是相同的),这种性质和在构建2-3树时的方法有关。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图1   为了维护2-3树绝对平衡的性质,在构建树,也就是插入结点时就要符合一定的逻辑。如下:   1、添加结点不能添加到空位置,除非此时整个树为空。   2、如果按照二分搜索树的方式插入素,当前插入位置是空,根据上一条,不能插入,此时可以放在最后一个叶子结点上。   上面的规则很空洞,下面看一个具体的例子:   示例:   如图2在插入42结点时,此时为空,直接插入在根节点位置。   如图2所示,在插入37时,按照二分搜索树,应该插在42 的左孩子上,但此时为空,不能插入,此时树中只有42一个结点,则37和42放一起。结果如图3所示。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图2
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图3   如图3所示,如果此时再往树中添加素12,按照二分搜索树的规则和2-3树的规则,应该插入在37的左孩子上,但此时为空,不能插入。所以放在最后一个叶子结点上,即根节点上,和37,42挤一挤。如图4所示:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图4   但2-3树不允许有这样的节点(只能包含一个或两个素),所以对图4继续调整,如图5所示:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图5   如果此时再添加18素,按理说应该放在12的右子树上,但12的右子树为空,不能放,所以先委屈18素和12素挤一挤,如图6所示。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图6   如果此时再往树中添加6素,按理说应该放在12的左子树上,但此时12的左子树为空,不能放。所以也委屈他和12 、18挤一挤,就像图4那样,结果如图7所示,
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图7   但图7不是绝对平衡的,因为从根节点到42经过的结点和到6所经过的结点是不同的。该怎么办呢?   答:12结点和它的父节点结合,就是让他们挤一挤,变成图8。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图8   如果此时要插入11呢?按照上面的规则,应该和6挤一挤,变成图9:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图9   如果此时再添加5素呢?应该和5、6、11挤一挤,如图10
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图10   此时不满足2-3树要求,对其调整,如图11
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图11   此时不满足绝对平衡的条件,把6和12、37挤一挤,变成图12
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图12   此时不满足要求,变成图13
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别图13   —————————分割线————————   上面的多个图展示了往2-3树中添加素的处理过程,整个过程始终保持绝对平衡。注意添加素的先后顺序是42->37->18->12->11->6->5,如果按照二分搜索树的添加规则,是不是会严重偏斜啊,所以二三树可以避免这种严重失衡。   总的原则如下:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   —————————————-分割线—————————————-   B树,又称多路平衡查找树,B数中所有结点的孩子个数的最大值称为B树的阶,用m表示。一颗m阶B树是一颗空树或者是符合一系列条件的m叉树。   性质1:m阶B树,每个节点最多有m叉,那么该节点最多有m-1个关键字(素)   树中每个结点最多有m棵子树,最多有m-1个关键字。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别性质1   性质2:除根节点外,其它非叶子节点至少有(m/2的结果并向上取整)个孩子节点,也就是至少有   (m/2的结果并向上取整减1)个关键字。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别性质2   性质3:若根节点不是叶子节点,则根节点至少有两个孩子节点。即根节点最少有1个关键字。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质4:每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质5:所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   综上,根节点的关键字数量范围:,非根节点的关键字数量范围:m/2的结果并向上取整减一。   比如这里有一个5阶的B树,根节点数量范围:1 <= k <= 4,非根节点数量范围:2 <= k <= 4。因为5/2=2.5,向上取整为3,再减一为2。   2-3树是特殊的B树,3阶B树(3阶意味着最多只能有2个关键字(素))   B数性质总结如下:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   ————————————–B+树———————————————–
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质1:m阶B+树的每个分支节点最多有m棵子树(与B树相同)
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别这里m=3吧   性质2:根节点要么没有子树,要么至少有两个子树(与B树相同)
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质3:除根节点外,其它每个分支节点至少有m/2(向上取整)棵子树(与B树略相同,但B+树n个关键字对应n个子树)
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质4:有n棵子树的节点恰好有n个关键字(B树是有n-1个关键字才有n个节点)
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质5:所有叶子结点包含全部关键字及指向对应记录的指针,而且叶子结点按关键字大小顺序链接。并将所有叶子结点链接起来。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   性质6:所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引的索引块)中最大关键字及指向子结点的指针。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   B+树性质总结
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   B+树案例
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   面试题:B树和B+树的区别?
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   (1)B树每个节点既有key又有数据,B+树的非叶子结点只有key(一行记录的主键id),没有数据(所谓数据,就是该行记录所在的地址)。   (2)B树的叶子结点之间是没有关系的,而B+树的叶子结点是相互连接的,类似链表,而且是双向的链表。   (3)在查找数据时,对于B树来讲,不一定非要找到叶子结点,而对于B+树来讲,是一定要找到叶子结点的。因为B+树的数据都在叶子结点,非叶子结点是没有数据的。   延伸:   B树特点:(1)每一层的节点是排好序的。(2)一个节点可以存储多个素,多个素之间也是按序排列的。   B+树特点:(1)B树的多有特点(2)叶子节点之间有指针(3)非叶子节点上的素在叶子节点上都冗余了,也就是叶子节点存储了所有的素,并且排好序。   面试题:为何mysql用B+树作为索引的存储形式?   用B+树就是因为B+树层级低,一般三层就能容纳千万级别的数据,而千万数据,跳表层级高,检索的话IO次数多。据说是因为每层有很多个分叉。   因为B树的每个节点都有key和数据,而B+树的非叶子节点是没有数据的,所以相同的大小,B+树能存储更多的数据。   因为B+树叶子节点有指针,所以对于范围查找更方便。   先解释为何其它数据结构不合适?   (0) hash:hash值是无序的,hash结构不支持范围查找,还存在hash冲突,多个key对应的哈希值相同,需要逐个对比。   (1)二分查找树:如果数据有序排列,会退化成链表,时间复杂度为O(n)   (2)平衡二叉树(AVL树,本身也是二分搜索树):树越高,查找越慢,而AVL容易变得越来越高。另外,对于范围查找,如下图查找大于等于5的数,需要三次定位到5,然后多次回查,效率较低。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   (4)B树:插入相同量的数据,B树的高度比AVL树低,所以查找效率相对较高,因为AVL树每个节点最多只有两个子节点,而B数则可以有多个子节点,所以每层能存储的节点多,可以降低层数。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   但B树仍然存储回旋查找慢的问题,如上图,查找大于5的素,需要先定位到5,然后往回查。   (5)最终选择了B+树
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   如上图所示,在B树的基础上增加了叶子节点的链接,且它们之间是排好序的,形成了双向链表,这样就可以很容易的某个范围的数据,而不用回查。   当SQL语句中有order by时,如果order by后的字段是索引字段,就可以提升效率,因为本来就排好序了。   索引:Innodb & Myisam   
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   聚簇索引和非聚簇索引
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   下面是两种索引的展示:
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   基于聚簇索引可以引申出很多索引,左边是主键索引(以主键值作为B+树节点),右边是辅助索引(非主键索引),因为聚簇索引中数据和索引值存在一起,可以通过索引直接查找到值,比如查找id为30的记录,可以在左边的主键索引中直接查到;但如果用的辅助索引,只可以查找到该行的主键id,需要再次查找左边的主键索引才能查到全部数据。   主键索引是聚簇索引的默认实现。如果没有主键,就会选择一个唯一且非空的字段构建索引来代替(唯一非空索引),如果没有这样的字段,就会生成一个隐式的聚簇索引。   索引覆盖:如果查的是主键,可以通过辅助索引直接查到   回表:如果查age字段,需要多走一次索引,先查找到id,再查到记录,需要查两次   索引下推:   非聚簇索引:根据主键查找到该行记录的地址
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   索引的扩展:   单列索引 与 复合索引   只包含一个字段的索引叫做单列索引,包含两个或以上字段的索引叫做复合索引(或组合索引)。建立复合索引时,字段的顺序极其重要。   下面这个SQL语句在 列X,列Y,列Z 上建立了一个复合索引。   其实这相当于建立了三个索引,分别是:   1、单列索引(列X) 2、复合索引(列X, 列Y) 3、复合索引(列X,列Y,列Z)。   索引失效   
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   索引失效一般出现在联合索引中,a和b是两个字段,(2,4)是(a,b)字段的值,对于这种联合索引,a字段的值整体是有序的,而b字段的值整体是无序的,但对于相同的a字段来讲,对应的b字段的值也是有序的。   比如要查找a大于1,且b大于1的数据,如下图,可以很快的定位到a大于1的位置,但由于b是无序的,所以还是需要从(2,1)往后逐个遍历。
简要叙述b树和b+树的区别_b+树和b-树的区别
简要叙述b树和b+树的区别_b+树和b-树的区别   但如果是查找a=2,b=1就可以通过索引方便查找,因为可以通过索引快速找到a=1,又因为相同的a对应的b也是有序的,所以方便查找到b=1。   索引失效案例:   创建联合索引,把phone和lan_id字段搞成联合索引explain select * from user where phone=’1212′ and lan_id=1; — 索引正常explain select * from user where lan_id=1; — 索引失效explain select * from user where phone>’1212′ and lan_id=1; — 索引失效explain select * from user where phone like ‘1212%’; — 有效explain select * from user order by phone; — 有效

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/52205.html

(0)
上一篇 2024年 9月 2日
下一篇 2024年 9月 2日

相关推荐

关注微信