前言
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({});