精华内容
下载资源
问答
  • b树和b 树的区别
    千次阅读
    2021-04-15 15:49:30

    一、为什么要有B树?

    学习任何一个东西我们都要知道为什么要有它,B树也一样,既然存储数据,我们为什么不用红黑树呢?

    这个要从几个方面来说了:

    (1)计算机有一个局部性原理,就是说,当一个数据被用到时,其附近的数据也通常会马上被使用。

    (2)所以当你用红黑树的时候,你一次只能得到一个键值的信息,而用B树,可以得到最多M-1个键值的信息。这样来说B树当然更好了。

    (3)另外一方面,同样的数据,红黑树的阶数更大,B树更短,这样查找的时候当然B树更具有优势了,效率也就越高。

    二、B树

    对于B树,我们首先要知道它的应用,B树大量应用在数据库和文件系统当中。

    B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。B树为系统最优化大块数据的读和写操作。B树算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

    假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    B树的结构:

    1. 根节点至少有两个子节点 ;

    2. 每个节点有M-1个key,并且以升序排列 ;

    3. 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间 ;

    4. 其它节点至少有M/2个子节点 ;

    5. 所有叶子节点都在同一层 。

    yH5BAEAAAAALAAAAAABAAEAAAIBRAA7

    三、B+树

    B+树是B-树的变体,也是一种多路搜索树,其定义基本与B树相同,除了:

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

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

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

    4. 所有关键字都在叶子结点出现。

    yH5BAEAAAAALAAAAAABAAEAAAIBRAA7

    四、B树与B+树的对比

    B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

    1、B树的优点

    1. B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

    2、B+树的优点

    1. 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率;

    2. B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

    yH5BAEAAAAALAAAAAABAAEAAAIBRAA7

    3、应用

    B树和B+树经常被用于数据库中,作为MySQL数据库索引。索引(Index)是帮助MySQL高效获取数据的数据结构。为了查询更加高效,所以采用B树作为数据库的索引。

    yH5BAEAAAAALAAAAAABAAEAAAIBRAA7

    更多相关内容
  • B树和B+树的区别

    万次阅读 2022-04-21 00:34:58
    首先来介绍一个工具或者是网站(当然是你能打开的情况下),如果对一个数据结构感觉有点...B+树和B树相比的主要区别: 1,就是B+树所有关键码都在叶子节点 2,B+树的叶子节点是带有指针的,且叶节点本身按关键码从小到

    首先来介绍一个工具或者是网站(当然是你能打开的情况下),如果对一个数据结构感觉有点问题,可以看看这个网站的演示,不管是插入还删除之类的这些可能在代码上看起来有点难懂的,经过动态演示,会有一个不同的理解。

    www.cs.usfca.edu

    在这里插入图片描述
    找你想看的一个数据结构,点进去,比如说我选择了B TreesB树点进去,效果如下:

    在这里插入图片描述

    你自己可以添加元素,删除元素,修改元素去观察数据结构了。

    B+树和B树相比的主要区别:
    1,就是B+树所有关键码都在叶子节点
    2,B+树的叶子节点是带有指针的,且叶节点本身按关键码从小到大顺序连接
    3,在搜索过程中,如果查询和内部节点的关键字一致,那么搜索过程不停止,而是继续向下搜索这个分支

    对照同样5个元素的排序就知道了
    B树
    在这里插入图片描述
    B+树
    在这里插入图片描述

    可以看出来B+树文件系统,数据库系统当中,更有优势,更高效。
    B+树更有利于对数据库的扫描 ,因为所有元素都在叶子节点上。
    B+树的查询效率更加稳定 ,所谓的稳定就是B树最后就是要找到叶子节点,就是不管你找谁都有从头走到尾,不会出现那个特别长,那个特别短。(这个可以在我推荐的这个工具演示一下寻找某个元素的过程)
    B+树没有像B树一样,把一些关键码每层都放一部分,之间存在互相之间的关系,指针。在考虑指针指向内容上,B树没有这些要存,反而数据量大的情况的,占的空间要比B树小。

    最后补一下B树,B+树的概念:
    一棵m阶B树是一棵平衡的m路搜索树,它或者是空树,或者是满足下列性质的树:

    • 树中每个结点至多有m棵子树。(即至多含有m-1个关键字,两颗子树指针夹着一个关键字);
    • 若根结点不是终端结点,则至少有两颗子树。(至少一个关键字);
    • 除根结点外的所有非叶子结点至少有[m/2]棵子树。(即至少含有[m/2]-1个关键字);
    • 所有的叶子结点出现在同一个层次上,不带信息。(就像是折半查找判断树中查找失败的结点)。
    • 每一个结点中的关键字满足从左到右依次增大的规则。

    B+树是B树上的一个修改或者改版:

    • n棵子tree的节点包含n个关键字,不用来保存数据而是保存数据的索引。
    • 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    • 所有的非终端结点可以看成是索引部分,结点中仅含其子树中的大(或小)关键字。
    • B+树中,数据对象的插入和删除仅在叶节点上进行。
    • B+树有2个头指针,一个是树的根节点,一个是小关键码的叶节点。
    展开全文
  • B树和B+树区别

    万次阅读 多人点赞 2020-07-14 11:13:21
    b树(balance tree)b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度比较次数都是最小的,为什么不用二叉树呢? 因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的...

    一,b树

    b树(balance tree)和b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢?
    因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,它的每个节点最多包含m个孩子,m称为b树的阶,m的大小取决于磁盘页的大小。
    ————————————————

    █一个M阶的b树具有如下几个特征:

    1.定义任意非叶子结点最多只有M个儿子,且M>2;
    2.根结点的儿子数为[2, M];
    3.除根结点以外的非叶子结点的儿子数为[M/2, M],向上取整;
    4.非叶子结点的关键字个数=儿子数-1;
    5.所有叶子结点位于同一层;
    6.k个关键字把节点拆成k+1段,分别指向k+1个儿子,同时满足查找树的大小关系。
    █有关b树的一些特性,注意与后面的b+树区分:

    1.关键字集合分布在整颗树中;
    2.任何一个关键字出现且只出现在一个结点中;
    3.搜索有可能在非叶子结点结束;
    4.其搜索性能等价于在关键字全集内做一次二分查找;
    █如图是一个3阶b树,顺便讲一下查询元素5的过程:

    1

    1,第一次磁盘IO,把9所在节点读到内存,把目标数5和9比较,小,找小于9对应的节点;

    2

     

    2,第二次磁盘IO,还是读节点到内存,在内存中把5依次和2、6比较,定位到2、6中间区域对应的节点;
    3,第三次磁盘IO就不上图了,跟第二步一样,然后就找到了目标5。

    可以看到,b树在查询时的比较次数并不比二叉树少,尤其是节点中的数非常多时,但是内存的比较速度非常快,耗时可以忽略,所以只要树的高度低,IO少,就可以提高查询性能,这是b树的优势之一。
    ————————————————

    █b树的插入删除元素操作:
    比如我们要在下图中插入元素4:
    3

    1,首先自顶向下查询找到4应该在的位置,即3、5之间;
    2,但是3阶b树的节点最多只能有2个元素,所以把3、4、5里面的中间元素4上移(中间元素上移是插入操作的关键);
    3,上一层节点加入4之后也超载了,继续中间元素上移的操作,现在根节点变成了4、9;
    4,还要满足查找树的性质,所以对元素进行调整以满足大小关系,始终维持多路平衡也是b树的优势,最后变成这样:
    4

    再比如我们要删除元素11:
    1,自顶向下查询到11,删掉它;
    2,然后不满足b树的条件了,因为元素12所在的节点只有一个孩子了,所以我们要“左旋”,元素12下来,元素13上去:
    5
    这时如果再删除15呢?很简单,当元素个数太少以至于不能再旋转时,12直接上去就行了。

    二,b+树

    b+树,是b树的一种变体,查询性能更好。m阶的b+树的特征:

    1.有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)。
    2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    3.所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。
    4.通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。
    5.同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。6

    █b+树相比于b树的查询优势:

    b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;
    b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);
    对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历,如下两图:

    7

    8

     

    展开全文
  • 文章目录前言B+HashHash索引与B+索引的区别总结 前言 我们都知道在MySQL中索引的数据结构有两种,一种是Hash,另一种是BTree。在数据表中建立什么样的索引需要我们根据实际情况进行选择。 B+ B+结构示意图:...
  • B-树和B+的C语言实现(数据结构)。
  • 数据结构 B树和B键树.pdf数据结构 B树和B键树.pdf数据结构 B树和B键树.pdf数据结构 B树和B键树.pdf数据结构 B树和B键树.pdf
  • B树的每个节点存储3个数据,B+树每个节点存储2个数据。B树除根节点以外,每个磁盘块间不会有链表连接。B+树有链表连接。下面详细说: 上图: 首先是B树图, 在B树中,下面这张小图里的节点有3个数据,17代表...

    先说最主要的区别。B树的每个节点存储3个数据,B+树每个节点存储2个数据。B树除根节点以外,每个磁盘块间不会有链表连接。B+树叶子节点有链表连接。下面详细说:

    上图:

    首先是B树图,

    在B树中,下面这张小图里的节点有3个数据,17代表当前的索引所在的节点位置,P1代表向下搜索的指针(也就是指向下一个节点的指针),红色框代表17对应的数据

    在看B+树:

    在B+树中,下面对应的图只有两个数据,5是当前索引所在的节点位置,P1代表向下搜索的指针(也就是指向下一个节点的指针)

    这个是存储结构的区别,下面说一下链表问题。

    看B+树,看见Q旁边的箭头没有?这个就是链表结构,代表B+树相邻的叶子节点之间是通过链表指针连起来的

    总结:

    1 B+树节点是不保存数据的,只是一个索引作用,它的叶子节点才保存数据(主键索引保存数据,非主键索引保存的是主键值)。B树的节点是保存数据的,

    2 B+树相邻的叶子节点之间是通过链表指针连起来的,B树没有这个功能。

    3 B+树则需要通过索引找到叶子结点中的数据才结束(也就是说,按照三层树高,每次都要遍历完3层才结束),而B树在找到具体的数值以后就结束(运气好遍历第一层就结束了)

    4 B树中每个索引关键字只会出现在一个结点中,不会重复出现。而B+树可以出现多次(可重复出现)。

     文章内容如果有错误,请各位路过的大佬指点,感谢!!

    展开全文
  • MySQL中B+ 树和 B 区别B+索引与Hash索引的区别
  • b树和b+树的区别

    万次阅读 多人点赞 2017-07-17 21:02:37
    一,b树b树(balance tree)b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度比较次数都是最小的,为什么不用二叉树呢? 因为我们要考虑磁盘IO的影响,它相对于内存来说...
  • B树的特点: 1.对节点进行了排序 2.一个节点可以存多个元素(元素也进行了排序) B+树的特点: 1.拥有B树的所有特点 2.叶子节点之间有指针 3.非叶子节点上的元素在叶子节点上都有冗余,也就是说叶子节点中存储了所有...
  • B树的每个节点都存储keydata。 B树由于keydata存在同一个节点,无法进行区间查询。 B树的查询最好时间复杂度为O(1)。 B+树的查询时间复杂度固定为logN。 B+树只在叶子节点中存储数据。 B+树可以进行区间查询,...
  • MySQL中的B树和B+树有什么区别

    千次阅读 2022-01-04 16:35:43
    MySQL中的B树和B+树有什么区别? 解析:B+树继承于B树,都限定了节点中数据数目子节点的数目。B树所有节点都可以映射数据,B+树只有叶子节点可以映射数据。 为了B+树创造了很多冗余的索引(所有非叶子节点都是...
  • Mysql中B树与B+树的区别

    千次阅读 2022-02-16 19:36:08
    B树和B+树都是应用在数据库索引上,可以认为是m叉的多路平衡查找树,但是理论上讲,二叉树的查找速度比较次数都更小,为什么不用二叉树呢? 这是因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的,数据库...
  • B树和B+树详解

    千次阅读 多人点赞 2021-05-24 09:43:53
    Mysql调优之B树和B+ 树详解
  • MySQL中B树与B+树的区别
  • B树,B-树B+树的区别

    万次阅读 热门讨论 2018-06-29 02:50:05
    B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(LeftRight); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; 如: B树的搜索,从根...
  • 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+区别

    千次阅读 2022-04-03 20:52:18
    首先 B+树的应用最多的就是在MySQL中的索引,是InnoDB存储引擎的...结点最大的孩子数目称为B树的阶,因此,2-3树是3阶的B树,而2-3-4是4阶的B树。再者B树的每个结点都会存储数据。 我们在来看B+树: 我们首先先比较
  • 这是某物APP的一道面试真题,B+树和B树区别,为什么mysql的索引使用B+树也不是B数。之前我们记录了一篇数据结构的的在线演示的网站,具体见这篇,接下来我们分析一下,为什么mysql使用B+树做索引。 这里我们首先...
  • B树和B+树区别对比

    千次阅读 2019-01-25 15:57:21
    B树相比二叉树就是每个节点多了更多的子树,节点中存储了一些子树的信息,B树一般用来作为磁盘存取的数据结构,磁盘中有两个机械运动的部分,分别是盘片旋转磁臂旋转。盘片旋转就是我们说的多少转每分钟。,而磁臂...
  • B树和B+树红黑树的区别

    千次阅读 2021-03-02 10:42:23
    如图所示,区别有以下两点: B+树中只有叶子节点会带有指向记录的指针(ROWID...叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点内部节点不停的往返移动。 B树的优点: 对于在
  • 红黑树和B树区别--2019年面试题目

    千次阅读 2019-04-20 09:56:21
    背景:这几天在看《高性能Mysql》,在看到创建高性能的索引,书上说mysql的存储引擎InnoDB采用的索引类型是B+Tree,那么,大家有没有产生这样一个疑问,对于数据索引,为什么要使用B+Tree这种数据结构,其它相比,它能...
  • B树与B+树的区别

    千次阅读 多人点赞 2021-09-14 00:00:30
    文章目录一、使用B-的好处二、B-深入三、B-的查找四、B+ 五、B-树和B+区别B+内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-查询时间复杂度不固定,与 key 在中...
  • B树相对于红黑树的区别在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。为什么会出现这样的情况,我们知道要获取磁盘上数据,必须先通过磁盘移动臂移动...
  • 特点:平衡二叉树是采用二分法思想把数据按规则组装成一个形结构的数据,用这个形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程遵循以下规则: (1)非叶子节点只能...

空空如也

空空如也

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

b树和b 树的区别