专栏首页热爱ITMysql InnoDB 为啥选择B+树索引 转

Mysql InnoDB 为啥选择B+树索引 转

前言

Mysql数据库中的常见索引有多种方式,例如Hash索引,B-树索引,B+树索引,但是为啥mysql中默认是采用B+树索引索引呢?下面对这三种索引学习总结一下。B+树到底有啥优势? B-树

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树(不是二叉树)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图。

B-树有如下特点:

    所有键值分布在整颗树中;

    任何一个关键字出现且只出现在一个结点中;

    搜索有可能在非叶子结点结束;

    在关键字全集内做一次查找,性能逼近二分查找;

 B+ 树

B+树是为磁盘及其他存储辅助设备而设计一种平衡查找树(不是二叉树)。B+树中,所有记录的节点按大小顺序存放在同一层的叶节点中,各叶节点用指针进行连接。B+树从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动。

简化 B+树 如下图

B+树有如下特点

    B+树每个节点可以包含更多的节点,这样做有两个原因,一个是降低树的高度。另外一个是将数据范围变为多个区间,区间越多,数据检索越快。占用空间非常小,因此每一层的节点能索引到的数据范围更加的广。换句话说,每次IO操作可以搜索更多的数据。     每个节点不再只是存储一个key了,可以存储多个key。

    非叶子节点存储key,叶子节点存储key和数据。

    叶子节点两两指针相互链接,顺序查询性能更高。叶子节点两两相连,符合磁盘的预读特性。比如叶子节点存储50和55,它有个指针指向了60和62这个叶子节点,那么当我们从磁盘读取50和55对应的数据的时候,由于磁盘的预读特性,会顺便把60和62对应的数据读取出来。这个时候属于顺序读取,而不是磁盘寻道了,加快了速度。

哈希索引

哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。

从上面的图来看,B+树索引和哈希索引的明显区别是:

    如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据;

    如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;

    哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询);

    哈希索引也不支持多列联合索引的最左匹配规则;

    B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。

总结

上面大致介绍了B-树,B+树,哈希索引。那么B+树的优势大致总结如下

    不同于B-树只适合随机检索,B+树同时支持随机检索和顺序检索;     B+树的磁盘读写代价更低。B+树内部结点比B-树小,盘块能容纳的结点中关键字数量更多,一次性读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。     B+树的查询效率更加稳定。B-树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。     B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B-树不支持这样的操作(或者说效率太低)。

参考文献

1.https://blog.csdn.net/m0_37947204/article/details/81046943

2.https://segmentfault.com/a/1190000004690721

3.https://blog.csdn.net/mine_song/article/details/63251546

4.http://www.cnblogs.com/zengkefu/p/5647279.html

(adsbygoogle = window.adsbygoogle || []).push({});

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MySQL数据表存储引擎类型及特性 转

    数据库引擎用于存储、处理和保护数据的核心服务,利用数据库引擎可控制访问权限并快速处理事务,利用数据库引擎创建用于联机事务处理或联机分析处理数据的关系数据库,包括...

    双面人
  • mysql5.7 索引

    问题1:mysql索引类型normal,unique,full text的区别是什么?

    双面人
  • python tornado 热加载/自动重启

    热加载这个概念我是在node中体验的,python这么强大的语言怎么会没有热加载呢?抱着这个心态google了一番,发现有的人用supervisor做的热加载,...

    双面人
  • MySQL常用性能分析方法-profile,explain,索引

    1.查版本号无论做什么都要确认版本号,不同的版本号下会有各种差异。>Select versio...

    Java架构师必看
  • MySQL索引那些事

    大家有没有遇到过慢查询的情况,执行一条SQL需要几秒,甚至十几、几十秒的时间,这时候DBA就会建议你去把查询的 SQL 优化一下,怎么优化?你能想到的就是加索引...

    编程大道
  • SQL Server之索引解析(二)

    聚集索引表由根节点(Root Node)、中间节点(Branch Nodes)、叶子节点组成。

    Edison.Ma
  • 一次 MySQL 索引面试,被面试官怼的体无完肤!

    之前有过一次面试,关于MySQL索引的原理及使用被面试官怼的体无完肤,立志要总结一番,然后一直没有时间(其实是懒……),准备好了吗?

    Java技术栈
  • MySQL与InnoDB(下)-B+树与索引

    本节主要讲对记录的查找。关于数据库查询,首先要从查询算法的角度优化,从顺序查找、二分查找再到二叉树查找。但每一种算法只能用于特定的数据结构上,比如二分查找必须有...

    企鹅号小编
  • Class文件访问标志&类索引

    在常量池以后,紧接着是2个字节的访问标志,用来表示一个Class文件的基本访问信息,包括Class是类还是接口,是否被定义为public类型,是否被定义为abs...

    shysh95
  • 数据库创建索引的条件和注意事项

    索引可以分为聚簇索引和非聚簇索引。聚簇索引通过树形结构重排表中的数据来提高数据的访问速度,非聚簇索引则通过维护表中的数据指针来提高数据的索引。

    Steve Wang

扫码关注云+社区

领取腾讯云代金券