Mysql InnoDB 为啥选择B+树索引

柔情只为你懂 2022-10-01 14:59 163阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

前言

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

转载于:https://my.oschina.net/u/3371661/blog/3023759

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/20c57ecb90bf4badaf7f44e1e28f8c38.png