• 【mysql为什么采用b+树作为索引】


    ## 1、Hash:
    它查询任何一行数据都只需一次IO,但是只能查一行,不能查询范围 。

    ## 2、二叉树:

    • 1、 可能会单边增长,退化成链表,查询效率和没建立索引差不多。
    • 2、才二叉而已,树的层数太多,IO次数多(一层就是一次IO)

    ## 3、红黑树:

    虽然解决了退化成链表的问题,但是也才二叉而已,树的层数太多,IO次数多(一层就是一次IO)

    ## 4、B树:
    内部节点存数据,导致每个节点放的数据少,还不能满足范围查找。

    特点:

    • 1、多路排序树
    • 2、内部节点也存data

    在这里插入图片描述

    ## 5、B+树:

    特点:

    • 1、多路排序树
    • 2、内部节点不存data,只有叶子节点才存data
    • 3、叶子节点左右相连,形成一条有序的双向循环链表
      在这里插入图片描述

    ## 为什么MySQL选择B+树做索引

    • 1、 B+树的磁盘IO读写次数低:每次读写一个树节点就是一次IO,B+树的内部节点并没有存data,因此盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。

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

    • 3、B+树更便于遍历:由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。

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

    ## B+树一个节点有多大?

    • 1、B+树一个节点的大小设为一页或页的倍数最为合适。因为如果一个节点的大小 < 1页,那么读取这个节点的时候其实读取的还是一页,这样就造成了资源的浪费。
    • 2、在 MySQL 中 B+ 树的一个节点大小为“1页”,也就是16k。之所以设置为一页,是因为对于大部分业务,一页就足够了:

    ## 一千万条数据,B+树多高?

    首先InnoDB的B+树中,非叶子节点存的是key 和 指针;叶子节点存的是数据行。

    对于叶子节点,如果一行数据大小为1k,那么一页就能存16条数据;对于非叶子节点,如果key使用的是bigint,则为8字节,指针在mysql中为6字节,一共是14字节,则16k能存放 16 * 1024 / 14 = 1170 个索引指针。于是可以算出,对于一颗高度为2的B+树,根节点存储索引指针节点,那么它有1170个叶子节点存储数据,每个叶子节点可以存储16条数据,一共 1170 x 16 = 18720 条数据。

    而对于高度为3的B+树,就可以存放 1170 x 1170 x 16 = 21902400 条数据(两千多万条数据),也就是对于两千多万条的数据,我们只需要高度为3的B+树就可以完成,通过主键查询只需要3次IO操作就能查到对应数据。所以在 InnoDB 中B+树高度一般为3层时,就能满足千万级的数据存储。

    文章知识点与官方知识档案匹配,可进一步学习相关知识

  • 相关阅读:
    Redis 如何实现库存扣减操作和防止被超卖?(荣耀典藏版)
    【Vue3.0移动端项目--旅游网】-- 首页日期和热门推荐处理
    短出行日渐成熟,电动两轮车迎来下半场
    软件项目管理 6.2.功能点估算法
    ①Redis String 字符串类型【命令汇总】
    2022-04-16 对于加班的感悟
    基于SSH开发网络在线考试系统
    vue3-web端文件下载
    智能座舱架构与芯片- (9) 音频篇 上
    python中的类型提示(定义函数时加入箭头->)
  • 原文地址:https://blog.csdn.net/m0_50116974/article/details/139729224