精华内容
下载资源
问答
  • 2022-04-20 14:47:19

    如果把数据库中的数据当做1个词典,那索引就是字典的目录,其目的是提升查找数据的速度。

    树的数据结构天然适合查找操作,最先被想到就是搜索二叉树。

    搜索二叉树

    二叉树(Binary Search Tree)是每个节点最多有2个子树(左子树和右子树)的树结构,而搜索二叉树是一类特殊的二叉树,其具有以下性质:

    • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值;
    • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值;
    • 它的左右子树也分别为搜索二叉树。

    搜索二叉树中序遍历的结果是有序的。

    搜索二叉树能够提高查询的效率 O(logN),但是当你插入 {1, 2, 3, 4, 5, 6} 这类数据的时候,搜索二叉树会退化成"链表",搜索效率变为 O(N)。
    在这里插入图片描述
    为了让二叉搜索树的左右子树平衡,出现了平衡二叉树。

    平衡二叉树

    平衡二叉树是1种特殊的二叉树,除了满足前面提到的搜索二叉树的特性,其还有1个约束条件:

    • 平衡二叉树左右子树的高度差的绝对值不超过1,并且其左右子树也分别为平衡二叉树。
      在这里插入图片描述
      可以通过左旋和右旋的方式将非平衡的搜索二叉树转化为平衡二叉树。

    • 左旋

    旧的根节点为新根节点的左子树,新根节点的左子树(如果存在)为旧根节点的右子树。

    • 右旋

    旧根节点为新根节点的右子树,新根节点的右子树(如果存在)为旧根节点的左子树。

    1棵平衡二叉树最多容纳多少节点呢?

    假设树的高度为h,则平衡二叉树最多容纳 1+21+22+…+2(h-1)=2h-1。

    如果整个平衡二叉树可以完整的加载到内存中,则其性能完全满足数据库索引的需求。但现实情况却是,当数据量比较大的时候,索引的大小可能有几个G甚至更多,当我们用索引查询的时候,很难将其全部加载到内存进行查找,能做的只有逐一加载每一个树节点,这里的树节点一般对应磁盘页或者磁盘页组合,我们姑且称之为数据块。

    如果每个数据块存储10行数据,每个数据块代表树的1个节点,则1000万行数据需要高度为20的平衡二叉树,即从1000万行数据的平衡二叉树中找1行数据,最坏的情况下需要20次磁盘IO。在机械硬盘时代,从磁盘随机读取1个数据块需要 10ms 左右的寻址时间,也就是说,对于1个1000万行的表,如果采用平衡二叉树来存储,单独访问1行需要20个 10ms 的时间,这个查询可真够慢的。

    为了让1个查询尽量少地读磁盘,就必须让查询过程中访问尽量少的数据块,而磁盘IO次数就是树的高度,所以我们需要想办法降低树的高度,使其变得矮胖,最容易想到的方案就是将二叉树调整为多叉树,让每一层能够容纳更多的节点。

    而 B-Tree(Balance Tree) 就是典型的多叉平衡搜索树。

    其实平衡二叉树的查询性能已经是最高的了,将二叉树改多叉树实属无奈之举(因为内存无法完全加载索引),这也就理解了为啥 HashMap 这类纯内存的集合,使用平二叉的红黑树,而不是多叉树。

    B-Tree

    需要注意的是: 中间的-符号不是减号,读作B树,而不是B减树。

    一棵 m 阶的 B 树具有如下特征:

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

    这条条框框的,听着就头大,别急,我们以3阶 B-Tree 为例:
    在这里插入图片描述
    重点看一下 (2,6) 节点,其包含2和6两个元素,又有3个孩子1、(3,5)、8。其中1小于元素2,(3,5) 在元素2和元素5之间,8大于元素6,正好符合刚才所列的几条特征。

    基于 B-Tree 查找某元素时,元素之间的比较次数和平衡二叉树其实是一致的,但由于查找所经过的节点数量要小的多,也就意味着更少次数的磁盘IO,会极大的提高性能。

    B-Tree 节点上除了索引元素,还包含卫星数据。

    所谓卫星数据,指的是索引元素所指向的数据记录,比如数据库中的某一行。在 B-Tree 树中,无论中间节点还是叶子节点均带有卫星数据。
    在这里插入图片描述
    所以本质上数据库基于 B-Tree 实现索引时,每个节点是 key-data 的形式,key 就是数据的主键,data 就是具体的数据。
    在这里插入图片描述
    接下来我们说一下 B+ 树。

    B+ Tree

    B+ 树和 B 树有一些共同点,但也具备一些新的特性:

    • 每个中间节点都包含 k 个元素和 k 个孩子,其中 m/2<=k<=m;
    • 中间节点仅包含索引元素,不包含数据,所有数据均在叶子节点;
    • 所有叶子节点包含了全部元素的信息及指向这些元素的指针,且叶子节点本身根据关键字的大小有小到大顺序排列;
    • 所有中间节点的元素均存在于子节点,在子节点元素中是最大(或最小)元素。

    直接举例说明:
    在这里插入图片描述
    可以看到,每一个父节点元素均出现在子节点中,是子节点中的最大(或最小)元素。如:根节点元素8是子节点(2,5,8)的最大元素,也是叶子节点(6,8)的最大元素。
    在这里插入图片描述
    需要注意的是,根节点的最大元素(这里是15),也就等同于整个 B+ 树的最大元素。后续无论插入删除多少元素,始终要保持最大元素在根节点之中。

    至于叶子节点,由于父节点的元素均会出现在子节点中,层层向下传导,所有叶子节点包含了全部元素信息。并且每一个叶子节点都带有指向下一个节点的指针,形成1个有序链表。
    在这里插入图片描述
    同样的,由于叶子节点包含了全部元素信息,所以 B+ 树的卫星数据只存在于叶子节点中,中间节点仅包含索引元素。
    在这里插入图片描述
    这时候,有读者就会问了,如果 B+ 树的卫星数据只存在于叶子节点上,岂不是每次都得遍历到最底下一层,才能拿到相应数据,而 B-Tree 中间节点就包含有卫星数据,假设索引元素命中,在中间层就可以返回,岂不是平均IO次数更低,那为啥还要使用 B+ 树呢?

    主要是因为在 B+ 树中,中间节点仅存储索引元素,而 B-Tree 的中间节点即存储索引元素又存储索引元素对应的卫星数据,所以同样存储空间的节点,显然 B+ 树可以容纳更多元素。比如建立100万条数据的索引,使用 B+ 树相比 B 树会使用更少的层数,即 B+ 树更矮胖,随之带来的就是磁盘IO次数的降低。

    同时,由于 B+ 树的叶子节点是根据索引元素大小顺序排列的,所以对于范围查询,只要从上到下找到范围的下界叶子节点,然后顺着叶子节点的横向指针就可以将符合条件的所有元素遍历出来。如果使用 B 树,则需要进行繁琐的中序遍历。

    综上,B+ 树相对于 B 树,具有如下优点:

    • 总元素个数相同的 B+ 树和 B 树相比,B+ 树更为矮胖(层高低),使得查询的 IO 次数更少;
    • B+ 树的所有叶子节点形成有序链表,便于范围查询。

    其实,B+ 树还有1个隐含优势,就是 B+ 树的元素查询性能更为稳定。

    因为 B+ 树的查询必须最终找到叶子节点,而 B 树只要找到匹配元素即可,无论匹配元素处于中间节点还是叶子节点。因此,B 树的查询性能并不稳定(最好情况是只查根节点,最差情况是查到叶子节点),而 B+ 树的每一次查询过程都是稳定的。

    B+ 树的层数计算

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

    MySQL 默认的 InnoDB 存储引擎也有自己的最小存储单元–页(Page),1页的默认大小是 16K。

    假设 B+ 树每个节点均代表1页。

    先假设 B+ 树有2层,第1层为非叶子节点,保存索引字段和指针,第2层为叶子节点,保存索引字段和具体行记录。

    那么,2层高度的 B+ 树能存储的行记录数=根节点的指针数*每个指针对应的第2层的行记录数。

    • 根节点的指针数

    假设主键为 bigint 类型(8字节),InnoDB 的指针占用6个字节,则1个 page 能存放的指针数为 16K/(8+6) 约等于1170;

    • 叶子节点的行记录数

    常规的互联网项目的单行记录大小约为1K,则1个 page 可以存储的行记录数为 16K/1K=16。

    所以1个2层 B+ 树大概能存储的行记录数为 1170*16=18,720。

    以此类推:

    3层 B+ 树: 1170117016=21,902,400(约2190万);
    4层 B+ 树: 117011701170*25,625,808,000(256亿)。

    考虑到根节点的数据块总是在内存中,1个200亿行的表上1个 bigint 类型的索引,查找1行数据最多只需要访问3次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

    哈哈哈,看出来多叉树的威力了吧。

    本文到此结束,感谢阅读!

    参考文献

    • MySQL实战45讲(丁奇)
    • 漫画: 什么是B+树?(程序员小灰)
    更多相关内容
  • B树和B+树

    2020-12-14 16:19:44
    所有的值都是按照顺序存储,没有重复的元素,并且每个叶子节点到根节点的距离相同,B树的中间节点会存储数据指针信息,B树索引能够加快访问速度,是因为存储引擎不再需要全表扫描来获取数据。 B+树 B+树有重复的...
  • B+B+ 中插入数据 要在 B+ 中插入数据,请运行: python bpt.py insert 文件名的默认参数是assgn2_bplus_data.txt 例子: python bpt.py insert assgn2_bplus_data.txt 在运行此查询时保存(插入...
  • B-B+的C语言实现(数据结构)。
  • B+的代码实现.pdf

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

    2017-10-03 12:24:03
    JAVA B+的实现
  • B树、B+树的C++实现

    2017-07-05 13:56:06
    B树、B+树的C++实现
  • 前面说过,为了减少磁盘的 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个子节点; 拥有二叉搜索树的一些性质(有序性); 平衡,每个...
  • B树和B+树,以及数据库中索引为什么用B+树而不是B树的?
  • 文章目录树基础知识回顾红黑树b树、b+树为什么不能使用二叉树来存储数据库索引B/B+树的索引数量索引什么是聚簇(集)索引?mysql聚簇和非聚簇索引的区别b+树和哈希索引二级索引二级索引存储主键值而不是存储行指针的...
  • B+C++代码实现

    热门讨论 2013-01-01 18:26:00
    一个外国人写的B+算法,由于注释比较少,故个人在参照时加上了自己的注释。该代码还用带了LRR和折半查找技术,很值得参考学习!!
  • MySQL进阶——B+索引结构

    千次阅读 2021-11-14 21:22:57
    索引是提升查询速度的一种数据结构。 索引之所以能提升查询速度,在于它在插入时对数据进行了排序(显而易见,它的缺点是...在目前的 MySQL 8.0 版本中,InnoDB 存储引擎支持的索引有 B+ 索引、全文索引、R 索引。
  • 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树是一种自平衡树数据结构,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和...
  • 数据结构(三)、B树,B+树,B*树

    千次阅读 2020-08-04 21:32:06
    对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。
  • MySQL 为什么用 B+ 实现索引索引概述常见的索引模型哈希表有序数组二叉查找二叉查找的查找操作二叉查找的缺陷为什么索引不用二叉树实现InnoDB 的索引模型B 树B 存在的问题B+ 树B B+ 的区别总结 ...
  • 关于B树和B+树以及数据库索引

    千次阅读 2022-03-29 16:38:37
    关于B树和B+树以及数据库索引==MySQL优化详解请点击====了解红黑树请点击==一.B树1.特点2.查找3.插入4.删除4.1 删除非终端关键字4.2 删除终端关键字4.2.1无需改动...对于一个m阶B树来说 任何节点最多m棵子树(子树数量
  • 经典结构——B+的原理及实现

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

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

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

    千次阅读 2019-12-17 11:27:12
    b树和b+树的区别 基本知识 2-3树 2-3-4树 B树存储引擎 (小知识点) (数据结构) B-树 简介 查找 插入 没有破坏结构 结构破坏 删除 终端 非终端 B+树 B树和二叉查找树的性能对比? 为什么数据库...
  • B+数据结构

    千次阅读 2022-01-05 11:41:58
    b树特点:b树中允许一个节点包含多个key,也就是上面所说的2-3-4树类型的树,但是它包含的节点数可以更多,所以我们可以称它为M阶B树。特点: 1)每个节点最多M减一个节点,可以升序排列 2)每个节点最多有M个子...
  • mysql为什么要使用B+作为索引

    千次阅读 2022-02-19 18:50:28
    这个时候了解的都知道是B+,那么为什么会采用B+作为它的索引结构呢? 由图可以知道:索引的存在时为了加快数据访问提高查询效率的,而数据存储在磁盘中,但从磁盘读取数据会产生大量的IO操作,读取效率是非常...
  • 树(四)详解B+树与B树索引

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 887,299
精华内容 354,919
关键字:

B+ 树