精华内容
下载资源
问答
  • B+树
    千次阅读
    2021-05-24 09:43:53


    在学习数据库调优相关知识的时候,我们发现数据库系统普遍采用B-/+Tree作为索引结构,例如MySQL的InnoDB引擎使用的数据结构是B+Tree,因此我们需要对BTree和B+Tree理解清楚,才能更好的理解数据库的索引机制。

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

    二叉搜索树(BST)
    平衡二叉搜索树(AVL):便于动态保持平衡的二叉搜索树
    有关AVL树的相关内容可以查看数据结构与算法中的二叉树与二叉搜索树的内容。

    1 B树

    二叉树是二分树,多分树是二叉树的推广。多分树主要适用于静态的索引数据文件,在插入和删除的时候需要把插入位置之后的每个记录都要向后移动,从而导致增加新的索引项和索引页块,需要对外存上的页块进行大量的调整。因此对于经常需要插入和删除的动态索引顺序文件,使用多分树并不合适,需要采用动态索引结构,即B树和B+树
    B树是一种自平衡树,是AVL树的一般化,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和删除。与AVL树不同的是,B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统。它通常用于数据库和文件系统。

    1.1 B树的定义

    一颗m阶的B树满足如下条件:

    • 每个节点最多只有m个子节点。
    • 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
    • 非叶子节点的根节点至少有两个子节点。
    • 有k颗子树的非叶节点有k-1个键,键按照递增顺序排列。
    • 叶节点都在同一层中。
      在这里插入图片描述

    (1)什么是B树的阶 ?
    B树中一个节点的子节点数目的最大值,用m表示,假如最大值为4,则为4阶,如图,所有节点中,节点[13,16,19]拥有的子节点数目最多,四个子节点(灰色节点),所以可以定义上面的图片为4阶B树。

    (2)什么是根节点 ?
    节点【10】即为根节点,特征:根节点拥有的子节点数量的上限和内部节点相同,如果根节点不是树中唯一节点的话,至少有俩个子节点(不然就变成单支了)。在m阶B树中(根节点非树中唯一节点),那么有关系式2<= M <=m,M为子节点数量;包含的元素数量 1<= K <=m-1,K为元素数量。

    (3)什么是内部节点 ?
    节点【13,16,19】、节点【3,6】都为内部节点,特征:内部节点是除叶子节点和根节点之外的所有节点,拥有父节点和子节点。假定m阶B树的内部节点的子节点数量为M,则一定要符合(m/2)<= M <=m关系式,包含元素数量M-1;包含的元素数量 (m/2)-1<= K <=m-1,K为元素数量。m/2向上取整。

    (4)什么是叶子节点?
    节点【1,2】、节点【11,12】等最后一层都为叶子节点,叶子节点对元素的数量有相同的限制,但是没有子节点,也没有指向子节点的指针。特征:在m阶B树中叶子节点的元素符合(m/2)-1<= K <=m-1。

    1.2 B树出现的目的

    B树的出现是为了弥补不同的存储级别之间的访问速度上的巨大差异,实现高效的 I/O。平衡二叉树的查找效率是非常高的,并可以通过降低树的深度来提高查找的效率。但是当数据量非常大,树的存储的元素数量是有限的,这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。

    1.3 B树的检索、插入和删除

    1.3.1 检索

    根据要查找的关键码key,在根节点的关键码集合中进行顺序或二分法检索,若key = ki,则检索成功;
    否则,key一定在某 ki 和 ki+1 之间,用一个指针在所指节点继续查找,重复上述检索过程,直到检索成功;或指针为空,则检索失败。
    整个检索过程中访外次数与B树的高度成正比

    1.3.2 插入

    针对m阶高度h的B树,插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素。

    • 若该节点元素个数小于m-1,直接插入;
    • 若该节点元素个数等于m-1,引起节点分裂;以该节点中间元素为分界,取中间元素(偶数个数,中间两个随机选取)插入到父节点中;
    • 重复上面动作,直到所有节点符合B树的规则;最坏的情况一直分裂到根节点,生成新的根节点,高度增加1。

    上面三点为插入动作的核心,接下来以5阶B树为例,详细讲解插入的动作。

    5阶B树关键点:
    2<=根节点子节点个数<=5
    3<=内节点子节点个数<=5
    1<=根节点元素个数<=4
    2<=非根节点元素个数<=4

    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    1.3.3 删除

    首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除;删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中,然后是移动之后的情况;如果没有,直接删除。

    • 某结点中元素数目小于(m/2)-1,(m/2)向上取整,则需要看其某相邻兄弟结点是否丰满;
    • 如果丰满(结点中元素个数大于(m/2)-1),则向父节点借一个元素来满足条件;
    • 如果其相邻兄弟都不丰满,即其结点数目等于(m/2)-1,则该结点与其相邻的某一兄弟结点进行“合并”成一个结点;

    接下来还以5阶B树为例,详细讲解删除的动作:
    关键要领,元素个数小于2(m/2 -1)就合并,大于4(m-1)就分裂
    如图依次删除依次删除【8】,【20】,【18】,【5】

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    2 B+树

    B+树是应文件系统所需而产生的B树的变形树,那么可能一定会想到,既然有了B树,又出一个B+树,那B+树必然是有很多优点的。

    2.1 B+树的定义

    一颗m阶的B+树满足如下条件:

    • 每个节点最多只有m个子节点。
    • 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
    • 非叶子节点的根节点至少有两个子节点。
    • 有k颗子树的非叶节点有k个键,键按照递增顺序排列。
    • 叶节点都在同一层中。
      在这里插入图片描述
      说明
      每个叶节点中至少包含 m/2(向下取整)个关键码,所有主文件记录的索引项都存放在B+树的叶节点中。所有内部节点都看成是索引的索引。节点中仅包含它的各个子节点中最大(或最小)关键码的分界值以及指向子节点的指针。

    2.2 B+树与B树的差异

    B+树B树
    有m颗子树的节点中含有 m 个关键码有m颗子树的节点中含有 m-1 个关键码
    所有的叶子结点中包含了完整的索引信息,包括指向含有这些关键字记录的指针,中间节点每个元素不保存数据,只用来索引B树中非叶子节点的关键码与叶子结点的关键码均不重复,它们共同构成全部的索引信息
    所有的非叶子节点可以看成是高层索引, 结点中仅含有其子树根结点中最大(或最小)关键字B 树的非叶子节点包含需要查找的有效信息

    2.3 B+树的检索、插入和删除

    检索
    在B+树中检索关键码key的方法与B树的检索方式相似,但若在内部节点中找到检索的关键码时,检索并不会结束,要继续找到B+树的叶子结点为止。
    插入
    与B树的插入操作相似,总是插到叶子结点上。当叶节点中原关键码的个数等于m时,该节点分裂成两个节点,分别使关键码的个数为 (m+1)/2 (向上取整)和 (m+1)/2 (向下取整)。
    删除
    仅在叶节点删除关键码。若因为删除操作使得节点中关键码数少于 m/2(向下取整)时,则需要调整或者和兄弟节点合并。合并的过程和B树类似,区别是父节点中作为分界的关键码不放入合并后的节点中。

    3 磁盘IO与B树

    3.1 BTree的高度

    BTree上大部分操作所需的磁盘读取次数与B树的高度成正比

    一棵含有N个总关键字数的m阶的B树的最大高度是多少?

    log(m/2)(N+1)/2 + 1 ,log以(m/2)为底,(N+1)/2的对数再加1.

    3.2 磁盘IO与预读

    计算机存储设备一般分为两种:内存储器(main memory)和外存储器(external memory)

    (1)内存储器为内存,内存存取速度快,但容量小,价格昂贵,而且不能长期保存数据(在不通电情况下数据会消失)。

    (2)外存储器即为磁盘读取,磁盘读取数据靠的是机械运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分,寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一般在5ms以下;旋转延迟就是我们经常听说的磁盘转速,比如一个磁盘7200转,表示每分钟能转7200次,也就是说1秒钟能转120次,旋转延迟就是1/120/2 = 4.17ms;传输时间指的是从磁盘读出或将数据写入磁盘的时间,一般在零点几毫秒,相对于前两个时间可以忽略不计。那么访问一次磁盘的时间,即一次磁盘IO的时间约等于5+4.17 = 9ms左右,听起来还挺不错的,但要知道一台500 -MIPS的机器每秒可以执行5亿条指令,因为指令依靠的是电的性质,换句话说执行一次IO的时间可以执行40万条指令,数据库动辄十万百万乃至千万级数据,每次9毫秒的时间,显然是个灾难。

    考虑到磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO,这个理论对于索引的数据结构设计非常有帮助。

    事实1 : 不同容量的存储器,访问速度差异悬殊。

    磁盘(ms级别) << 内存(ns级别), 100000倍
    若内存访问需要1s,则一次外存访问需要一天
    为了避免1次外存访问,宁愿访问内存100次…所以将最常用的数据存储在最快的存储器中

    事实2 : 从磁盘中读 1 B,与读写 1KB 的时间成本几乎一样

    从以上数据中可以总结出一个道理,索引查询的数据主要受限于硬盘的I/O速度,查询I/O次数越少,速度越快,所以B树的结构才应需求而生;B树的每个节点的元素可以视为一次I/O读取,树的高度表示最多的I/O次数,在相同数量的总元素个数下,每个节点的元素个数越多,高度越低,查询所需的I/O次数越少;假设,一次硬盘一次I/O数据为8K,索引用int(4字节)类型数据建立,理论上一个节点最多可以为2000个元素,200020002000=8000000000,80亿条的数据只需3次I/O(理论值),可想而知,B树做为索引的查询效率有多高;另外也可以看出同样的总元素个数,查询效率和树的高度密切相关。

    4 B+树与B树

    4.1 B+ 树比B树更适合索引?

    1)B+树的磁盘读写代价更低

    B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了;

    2)B+树查询效率更加稳定

    由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当;

    3)B+树便于范围查询(最重要的原因,范围查找是数据库的常态)

    B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。

    补充:B树的范围查找用的是中序遍历,而B+树用的是在链表上遍历。

    4.2 MySQL中InnoDB与MyISAM中采用B+树结构?

    (1)B+树
    在这里插入图片描述(2)InnoDB
    在这里插入图片描述(3)MyISAM
    在这里插入图片描述

    更多相关内容
  • B树和B+树

    2020-12-14 16:19:44
    所有的值都是按照顺序存储,没有重复的元素,并且每个叶子节点到根节点的距离相同,B树的中间节点会存储数据指针信息,B树索引能够加快访问速度,是因为存储引擎不再需要全表扫描来获取数据。 B+树 B+树有重复的...
  • B-B+的C语言实现(数据结构)。
  • B+的代码实现.pdf

    2018-05-03 09:53:44
    B+的相关技术描述以及基于B+的代码实现设计注意事项,代码设计注意事项,开源内容
  • JAVA B+的实现

    2017-10-03 12:24:03
    JAVA B+的实现
  • 前面说过,为了减少磁盘的 I/O 操作才有的B树,那么来看下B树有什么特点: 还是上面那个问题,来看下B树怎么个解决方案: ps:K被称为B树的阶,K的值取决于磁盘页(内存的最小存储单位)的大小 假设搜索节点6,步骤...

    💕前言💕

    楼下菜大爷遛弯的时候经常在菜菜身边装逼,说什么b+树很简单在这里插入图片描述
    你们觉得我信吗?信吗?可是…
    当菜菜把这篇文章认认真真的看完之后!!!

    被他装到了,可恶!!!不信?看完评论区见

    ✨b树家族、一个都别想跑✨

    讲b+树前,先调查一下它的血亲!一个都别想跑!来来来,给我排整齐给大家看看~

    B树、B-树(嫌疑较大,留意)、B+树、B*树

    一个普普通通的树(二叉树),非要搞这么多玩意,区别是啥:

    姓名(术语)简介
    B树多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
    B-树就是B树(没想到吧)
    B+树在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;
    B*树在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

    秘闻;

    • 因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,所以人们可能会以为B-树是一种树,而B树又是另一种树。而事实上是,B-tree就是指的B树

    💙前提条件,温故而知新💙

    💨什么是AVL树

    • 平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1),只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少,但查找多的情况。

    💨什么是红黑树

    • 平衡二叉树,通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,确保没有一条路径会比其他路径长2倍,因而是近似平衡的。所以相对于严格要求平衡的AVL树来说,它的旋转保持平衡次数较少。用于搜索时,插入删除次数多的情况下我们就用红黑树来取代AVL。

    💨什么是二叉搜索树

    举个例子,二叉搜索树来作为索引的案例:
    在这里插入图片描述
    现在来查找节点为5的节点,来看看需要几步:
    在这里插入图片描述
    没错,一共四步,但是要注意,一般索引是在内存中执行的,所以价格很昂贵!!在最坏的情况下磁盘读写次数==二叉搜索树的高度,这在实际应用中肯定是不行的,所以基于此,诞生了B树*(多路平衡树)来减少数的高度,那么🔻

    💨什么是B树(多路平衡树)❓

    B树其实最开始源于的是二叉树,二叉树是只有左右孩子的树,当数据量越大的时候,二叉树的节点越多,那么当从根节点搜索的时候,影响查询效率。所以如果这些节点存储在外存储器中的话,每访问一个节点,相当于进行了一次I/O操作。前面说过,为了减少磁盘的 I/O 操作才有的B树,那么来看下B树有什么特点:

    还是上面那个问题,来看下B树怎么个解决方案:
    在这里插入图片描述
    ps:K被称为B树的阶,K的值取决于磁盘页(内存的最小存储单位)的大小
    在这里插入图片描述
    假设搜索节点6,步骤:

    • ①定位到根节点(9),6比9小,所以在左子树找
    • ②定位到节点(4,7),6在4、7中间,所以在中间子树找
    • ③定位到(5,6),6比5大,所以和该节点的右边比较
    • ④找到,over

    可以看出,在B树里面的比较次数也很多,但是❗减少了I/O操作,因为B树可以减少树的高度,也就减少了磁盘读写次数,在实际应用场景,B树对性能的提升非常明显。

    最后,大家可能之前都知道B树的特点,现在应该会更好理解(m是树的高度,k是树的阶):

    • 1.根结点至少有两个子节点。
    • 2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 。
    • 3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m。
    • 4.所有的叶子结点都位于同一层。
    • 5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

    🧡b+树到底是啥玩意?就这?🧡

    在这里插入图片描述
    前面说了这么多,到这里才步入主题,先来调查一下…
    在这里插入图片描述
    经过菜菜调查发现,B+树的出现带来了这些优点:

    1)B+树的磁盘读写代价更低

    B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B
    树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了;

    2)B+树查询效率更加稳定

    由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当;

    3)B+树便于范围查询(最重要的原因,范围查找是数据库的常态)

    B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低;

    B+树最大的性能问题在于会产生大量的随机IO,主要存在以下两种缺点:

    • 主键不是有序递增的,导致每次插入数据产生大量的数据迁移和空间碎片;
    • 即使主键是有序递增的,大量写请求的分布仍是随机的;

    看下B+树长什么样子
    在这里插入图片描述

    如果要查找0007的话,查找方式如下
    在这里插入图片描述
    并且,为什么MySQL数据库索引选择使用B+树?
    B+树的节点只存储索引key值,具体信息的地址存在于叶子节点的地址中。这就使以页为单位的索引中可以存放更多的节点。减少更多的I/O支出。因此,B+树成为了数据库比较优秀的数据结构,MySQL中MyIsAM和InnoDB都是采用的B+树结构。不同的是前者是非聚集索引,后者主键是聚集索引。

    看下B+树的顺序查找:
    在这里插入图片描述

    B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。B+树支持range-query(区间查询)非常方便,而B树不支持。

    B+ 树通常用于数据库和操作系统的文件系统中

    NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

    💚B树、B+树都知道了,B*树不了解一下?💚

    先看下百度的回答:

    B树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;B树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

    B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针:
    找的网图(大佬莫怪)

    在这里插入图片描述

    B+树和B*树的区别是啥?

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

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

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

    💜数据库索引数据结构了解下?💜

    MySql索引数据结构(BTREE和Hash),也来简单了解下 BTREE和Hash的区别

    • 1、Hash 索引,其检索效率非常高,索引的检索可以一次定位。BTREE 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问
    • 2、Hash 索引仅仅能满足"=",“IN"和”<=>"查询,不能使用范围查询。
    • 3、Hash 索引无法被用来避免数据的排序操作
    • 4、Hash 索引不能利用部分索引键查询。
    • 5、Hash 索引在任何时候都不能避免表扫描。
    • 6、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

    而数据库一般采用B+树索引是因为Hash索引的话,不适合做范围查询,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了(比如原来Hello和World原来是在一起的,但是经过hash算法后就变成了0001 和1522)

    索引 / 存储引擎MyISAMInnoDBMemory
    B-Tree索引支持支持支持
    HASH索引不支持不支持❗支持
    R-Tree索引支持支持不支持
    Full-text索引支持支持不支持

    ps:InnoDB引擎支持hash索引是自适应的,InnoDB存储引擎根据表使用情况自动为表创建hash索引。创建由InnoDB存储引擎引擎自动优化创建,我们干预不了❗ 所以说innodb不算是支持hash索引,因为索引一般用来存储数据的,但是这个hash索引是InnoDB引擎使用来快速找到内存中的页的。

    hash索引的适用情况
    检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。除了memory引擎外,NDB引擎也支持唯一哈希索引

    💛B+树代码实现💛

    有缘相见🧡
    

    🤎数据结构可视化神器推荐!🤎

    旧金山大学做的 BPlusTree Visualization 模型数据结构可视化
    在这里插入图片描述
    在这里插入图片描述
    一个字,绝!!!好用 好用 学起来~

    在这里插入图片描述

    展开全文
  • B树和B+树的区别

    千次阅读 2021-09-14 11:51:56
    文章目录简述写在前面1、B树2、B+树深入浅出B树B树深入B-树的查找B+ 树B+树概述B-树和B+树的区别拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识存储数据最小单元主存存取原理磁盘存取原理总结 简述 写在...

    简述

    写在前面

    大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景:
    请添加图片描述
    B树 和B+树是 MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点!

    1、B树

    • 这里的 B 是 Balance(平衡)的缩写。它是一种多路的平衡搜索树。
    • 它跟普通的平衡二叉树的不同是,B树的每个节点可以存储多个数据,而且每个节点不止有两个子节点,最多可以有上千个子节点。
    • B树中每个节点都存放着索引和数据,数据遍布整个树结构,搜索可能在非叶子节点结束,最好的情况是O(1)。
    • 一般一棵 B 树的高度在 3 层左右,3 层就可满足 百万级别的数据量

    在这里插入图片描述

    B树 每个节点都存储了一定的范围区间,区间更多的情况下,搜索也就更快。

    比如普通的二叉树对于 1~ 100 的索引值,首先分为 1~ 50 和51~ 100 两部分。

    而 B树可以分为四个区间 1~ 25, 26~ 50, 51~ 75, 76~ 100 。甚至可以划分为更多区间,这样一次就能排除四分之三的数据

    2、B+树

    B+树是B树的一种变种,它与 B树 的 区别 是:

    • 叶子节点保存了完整的索引和数据,而非叶子节点只保存索引值,因此它的查询时间固定为 log(n).
    • 叶子节点中有指向下一个叶子节点的指针,叶子节点类似于一个单链表
    • 正因为叶子节点保存了完整的数据以及有指针作为连接,B+树可以增加了区间访问性,提高了范围查询,而B树的范围查询相对较差
    • B+树更适合外部存储。因为它的非叶子节点不存储数据,只保存索引。

    B+树的示意图如下:

    在这里插入图片描述

    到此为止相信你已经对B树和B+树有一定认识,下面结合数据库深入了解


    深入浅出

    B树

    B-树有如下特点:

    1. 所有键值分布在整颗树中(索引值和具体data都在每个节点里);
    2. 任何一个关键字出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);
    4. 在关键字全集内做一次查找,性能逼近二分查找;

    B树深入

    B树由来

    定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。
    B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

    定义只需要知道B-树允许每个节点有更多的子节点即可(多叉树)。子节点数量一般在上千,具体数量依赖外部存储器的特性。

    先来看看为什么会出现B-树这类数据结构。

    传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

    在这里插入图片描述
    上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

    空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    我们从“迎合”磁盘的角度来看看B-树的设计。

    索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘存储单位是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

    在这里插入图片描述
    上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快(比二叉树深层次的搜索肯定快很多)。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

    点评:B树的每个节点,都是存多个值的,不像二叉树那样,一个节点就一个值,B树把每个节点都给了一点的范围区间,区间更多的情况下,搜索也就更快了,比如:有1-100个数,二叉树一次只能分两个范围,0-50和51-100,而B树,分成4个范围 1-25, 25-50,51-75,76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

    B-树的查找

    我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

    Data* BTreeSearch(Root *node, Key key)
    {
        Data* data;
    
        if(root == NULL)
            return NULL;
        data = BinarySearch(node);
        if(data->key == key)
        {
            return data;
        }else{
            node = ReadDisk(data->next);
            BTreeSearch(node, key);
        }
    }
    

    B+ 树

    B+树概述

    B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:

    1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
    2. 为所有叶子结点增加了一个链指针

    简化 B+树 如下图

    在这里插入图片描述
    在这里插入图片描述
    因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

    为了增加 区间访问性,一般会对B+树做一些优化。
    如下图带顺序访问的B+树。

    在这里插入图片描述

    B-树和B+树的区别

    1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

    如下所示B-树/B+树查询节点 key 为 50 的 data。

    B-树:

    在这里插入图片描述
    从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

    B+树:

    在这里插入图片描述
    由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

    点评:B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据

    2. B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

    在这里插入图片描述
    根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。
    当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

    点评:由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快

    3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

    这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

    点评:由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!

    在这里插入图片描述
    从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

    拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识

    上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

    存储数据最小单元

    我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。

    在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k

    而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。

    下面几张图可以帮你理解最小存储单元:

    文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。

    磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

    在这里插入图片描述
    在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:

    在这里插入图片描述
    数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。

    主存存取原理

    目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

    在这里插入图片描述
    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

    主存的存取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

    这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

    磁盘存取原理

    上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

    图6是磁盘的整体结构示意图。

    一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

    图7是磁盘结构的示意图。

    在这里插入图片描述
    盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

    当一个数据被用到时,其附近的数据也通常会马上被使用。

    程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    所以IO一次就是读一页的大小

    总结

    MySQL的B树和B+树原理就说到这里了。

    我是JavaPub,下期见

    参考:https://www.cnblogs.com/gslgb/p/14821363.html

    展开全文
  • B树与B+树的区别

    千次阅读 多人点赞 2021-09-14 00:00:30
    文章目录一、使用B-的好处二、B-深入三、B-的查找四、B+ 五、B-B+的区别①B+内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-查询时间复杂度不固定,与 key 在中...

    • 在B树中,你可以将键和值存放在内部节点和叶子节点;但在B+树中,内部节点都是键,没有值,叶子节点同时存放键和值。

    • B+树的叶子节点有一条链相连,而B树的叶子节点各自独立。
      在这里插入图片描述

    一、使用B-树的好处

    B树可以在内部节点同时存储键和值,因此,把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。这种特性使得B树在特定数据重复多次查询的场景中更加高效。

    B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树(B树是一颗多路平衡查找树)它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.
    在这里插入图片描述
    B-树有如下特点:

    • 所有键值分布在整颗树中(索引值和具体data都在每个节点里);
    • 任何一个关键字出现且只出现在一个结点中;
    • 搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);
    • 在关键字全集内做一次查找,性能逼近二分查找;

    二、B-树深入

    B树由来:

    定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。
    B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

    定义只需要知道B-树允许每个节点有更多的子节点即可(多叉树)。子节点数量一般在上千,具体数量依赖外部存储器的特性。

    先来看看为什么会出现B-树这类数据结构:

    传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
    在这里插入图片描述

    上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若只有部分加载到内存中则无法完成旋转操作。

    其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

    空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    我们从“迎合”磁盘的角度来看看B-树的设计:

    索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。

    为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘存储单位是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。
    在这里插入图片描述

    上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快(比二叉树深层次的搜索肯定快很多)。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

    点评:B树的每个节点,都是存多个值的,不像二叉树那样,一个节点就一个值,B树把每个节点都给了一点的范围区间,区间更多的情况下,搜索也就更快了,比如:有1-100个数,二叉树一次只能分两个范围,0-50和51-100,而B树,分成4个范围 1-25, 25-50,51-75,76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

    三、B-树的查找

    我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO。
    在这里插入图片描述
    比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

    Data* BTreeSearch(Root *node, Key key)
    {
        Data* data;
    
        if(root == NULL)
            return NULL;
        data = BinarySearch(node);
        if(data->key == key)
        {
            return data;
        }else{
            node = ReadDisk(data->next);
            BTreeSearch(node, key);
        }
    }
    
    

    四、B+ 树

    B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:

    • 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)。
    • 为所有叶子结点增加了一个链指针。

    简化 B+树 如下图:
    在这里插入图片描述
    在这里插入图片描述

    因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。
    在这里插入图片描述
    为了增加 区间访问性,一般会对B+树做一些优化。
    如下图带顺序访问的B+树。
    在这里插入图片描述

    五、B-树和B+树的区别

    B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

    如下所示B-树/B+树查询节点 key 为 50 的 data。
    在这里插入图片描述
    从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

    在这里插入图片描述
    由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

    点评:B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据

    B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

    在这里插入图片描述

    根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

    点评:由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快。

    B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

    这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

    点评:由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!

    在这里插入图片描述
    从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

    六、使用B+树的好处

    由于B+树的内部节点只存放键,不存放值,因此,一次读取,可以在内存页中获取更多的键,有利于更快地缩小查找范围。 B+树的叶节点由一条链相连,因此,当需要进行一次全数据遍历的时候,B+树只需要使用O(logN)时间找到最小的一个节点,然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历,这会需要更多的内存置换次数,因此也就需要花费更多的时间

    七、拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识

    上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

    下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • MySQL中的B+索引结构

    万次阅读 2021-08-08 19:11:01
    B树 B树(B-tree、B-树):是一种平衡的多路搜索树,多用于文件系统、数据库的实现。 B树的特点: 1个节点可以存储超过2个元素、可以拥有超过2个子节点; 拥有二叉搜索树的一些性质(有序性); 平衡,每个...
  • MySQL的InnoDB索引结构为啥选用B+?

    千次阅读 2022-04-20 14:47:19
    二叉树(Binary Search Tree)是每个节点最多有2个子(左子树和右子)的结构,而搜索二叉树是一类特殊的二叉树,其具有以下性质: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值; 若它的右子不...
  • B树和B+树,以及数据库中索引为什么用B+树而不是B树的?
  • b+详解

    千次阅读 多人点赞 2021-05-22 20:55:35
    B树 与 B+树 我们今天要介绍的是工作开发中最常接触到的 InnoDB 存储引擎中的 B+ 树索引。要介绍 B+ 树索引,就不得不提二叉查找树,平衡二叉树和 B 树这三种数据结构。B+ 树就是从他们仨演化来的。 二叉查找树 首先...
  • 文章目录树基础知识回顾红黑树b树、b+树为什么不能使用二叉树来存储数据库索引B/B+树的索引数量索引什么是聚簇(集)索引?mysql聚簇和非聚簇索引的区别b+树和哈希索引二级索引二级索引存储主键值而不是存储行指针的...
  • 面试题——红黑树,B树、B+树

    千次阅读 2022-01-06 19:08:30
    面试题——红黑树,B树、B+树
  • mysql中B+索引原理

    千次阅读 2021-12-01 11:33:34
    mysql索引与B+的关系
  • B树、B+树详解

    千次阅读 2020-08-17 12:41:41
    B-树,即为B树。因为B树的原英文名称为B-tree,目前理解B的意思为平衡。 概念 首先,B树不要和二叉树混淆,在计算机科学中,B树是一种自平衡树数据结构,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和...
  • Mysql中B树与B+树的区别

    千次阅读 2022-02-16 19:36:08
    一、B树 B树和B+树都是应用在数据库索引上,可以认为是m叉的多路平衡查找树,但是理论上讲,二叉树的查找速度和比较次数都更小,为什么不用二叉树呢? 这是因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的...
  • MySQL 为什么用 B+ 实现索引索引概述常见的索引模型哈希表有序数组二叉查找二叉查找的查找操作二叉查找的缺陷为什么索引不用二叉树实现InnoDB 的索引模型B 树B 存在的问题B+ 树B B+ 的区别总结 ...
  • MySQL进阶——B+索引结构

    千次阅读 2021-11-14 21:22:57
    索引是提升查询速度的一种数据结构。 索引之所以能提升查询速度,在于它在插入时对数据进行了排序(显而易见,它的...在目前的 MySQL 8.0 版本中,InnoDB 存储引擎支持的索引有 B+ 索引、全文索引、R 索引。...
  • 经典结构——B+的原理及实现

    千次阅读 2021-11-19 15:10:08
    B+跟B树不同B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加 B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能...
  • Mysql索引B树跟B+树

    千次阅读 2021-12-29 10:39:35
    索引底层实现原理 数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个...B树 B-树是一种m阶平衡树,m一般是300-500(经验值),叶子节点都在同一层,由于每一个节点存储的
  • 一文彻底搞懂MySQL基础:B树和B+树的区别

    万次阅读 多人点赞 2020-06-24 11:27:27
    B树和B+树是MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点! 欢迎关注公
  • B树与B+树

    千次阅读 多人点赞 2020-09-07 16:48:34
    一、B树 1.1 B树的定义 B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子结点,一般用字母m表示阶数。当m取2时,就是我们常见的二叉搜索树。 一颗m阶...
  • B树、B+树的C++实现

    2017-07-05 13:56:06
    B树、B+树的C++实现
  • 树(四)详解B+树与B树索引

    千次阅读 2020-03-05 17:25:02
    1 B树 1.1 B树是什么 首先,B树不属于二叉树,它的节点可以拥有大于2的子节点。 B树是一种平衡的多叉树,又叫做多路平衡搜索树,一棵m叉的B树具有如下特性。 (1)树中的每一个节点最多包含m个子节点; (2...
  • 关于B树和B+树以及数据库索引

    千次阅读 2022-03-29 16:38:37
    关于B树和B+树以及数据库索引
  • MySQL索引(B树、B+树)

    千次阅读 多人点赞 2022-02-27 14:47:01
    目录简介索引结构()为什么用,而不用哈希表BTree索引B+Tree索引聚簇索引与非聚簇索引 简介 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。...
  • 什么是B+

    千次阅读 多人点赞 2021-07-06 21:22:49
    B+树是B树的一种变体,也属于平衡多路查找树,大体结构与B树相同,包含根节点、内部节点和叶子节点。多用于数据库和操作系统的文件系统中,由于B+树内部节点不保存数据,所以能在内存中存放更多索引,增加缓存命中率...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 900,786
精华内容 360,314
关键字:

B+树

友情链接: AD2.zip