MySQL性能优化做得好的人，都懂的索引绝技其底层的存储引擎和数据检索

一步一步推导出MySQL索引的底层数据结构。
MySQL作为互联网中非常热门的数据库，其底层的存储引擎和数据检索引擎的设计非常重要，尤其是MySQL数据的存储形式以及索引的设计，决定了MySQL整体的数据检索性能。
我们知道，索引的作用是做数据的快速检索，而快速检索实现的本质是数据结构。通过不同数据结构的选择，实现各种数据快速检索。在数据库中，高效的查找算法是非常重要的，因为数据库中存储了大量数据，一个高效的索引能节省巨大的时间。
比如下面这个数据表，如果MySQL没有实现索引算法，那么查找id=7这个数据，那么只能采取暴力顺序遍历查找，找到id=7这个数据需要比较7次，如果这个表存储的是1000W个数据，查找id=1000W这个数据那就要比较1000W次，这种速度是不能接受的。

文章图片
一、MySQL索引底层数据结构选型
1、哈希表（Hash）
哈希表是做数据快速检索的有效利器。
哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的key地址，通过这个地址进行具体数据的数据结构。

文章图片
考虑这个数据库表user ，表中一共有7个数据，我们需要检索id=7的数据， SQL语法是：
select*fromuserwhereid=7
哈希算法首先计算存储id=7的数据的物理地址addr=hash(7)=4231 ，而4231映射的物理地址是0x77 ， 0x77就是id=7存储的额数据的物理地址，通过该独立地址可以找到对应user_name="g"这个数据。这就是哈希算法快速检索数据的计算过程。
但是哈希算法有个数据碰撞的问题，也就是哈希函数可能对不同的key会计算出同一个结果，比如hash(7)可能跟hash(199)计算出来的结果一样，也就是不同的key映射到同一个结果了，这就是碰撞问题。解决碰撞问题的一个常见处理方式就是链地址法，即用链表把碰撞的数据接连起来。计算哈希值之后，还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾，直达找到真正的key对应的数据为止。

文章图片

文章图片
从算法时间复杂度分析来看，哈希算法时间复杂度为O（1），检索速度非常快。比如查找id=7的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是MySQL并没有采取哈希作为其底层算法，这是为什么呢？
因为考虑到数据检索有一个常用手段就是范围查找，比如以下这个SQL语句：
select*fromuserwhereid&gt3
针对以上这个语句，我们希望做的是找出id&gt3的数据，这是很典型的范围查找。如果使用哈希算法实现的索引，范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了，没有一点效率而言。
所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为Mysql的底层索引的数据结构。
2、二叉查找树(BST)
二叉查找树是一种支持数据快速查找的数据结构，如下图所示:

文章图片
二叉查找树的时间复杂度是O(lgn) ，比如针对上面这个二叉树结构，我们需要计算比较3次就可以检索到id=7的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？
答案是可以的。观察上面的图，二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找id&gt5的数据，那我们取出节点为6的节点以及其右子树就可以了，范围查找也算是比较容易实现。
但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为O（N），检索性能急剧下降。比如以下这个情况，二叉树已经极度不平衡了，已经退化为链表了，检索速度大大降低。此时检索id=7的数据的所需要计算的次数已经变为7了。

文章图片
在数据库中，数据的自增是一个很常见的形式，比如一个表的主键是id ，而主键一般默认都是自增的，如果采取二叉树这种数据结构作为索引，那上面介绍到的不平衡状态导致的线性查找的问题必然出现。因此，简单的二叉查找树存在不平衡导致的检索性能降低的问题，是不能直接用于实现MySQL底层索引的。
3、AVL树和红黑树
二叉查找树存在不平衡问题，因此学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有AVL树和红黑树。
首先简单介绍红黑树，这是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为O（logn）），也就保证了查找效率不会明显减低。比如从1到7升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找id=7的所要比较的节点数为4 ，依然保持二叉树不错的查找效率。
红黑树拥有不错的平均查找效率，也不存在极端的O(n)情况，那红黑树作为Mysql底层索引实现是否可以呢？其实红黑树也存在一些问题，观察下面这个例子。
红黑树顺序插入1~7个节点，查找id=7时需要计算的节点数为4 。

文章图片
红黑树顺序插入1~16个节点，查找id=16需要比较的节点数为6次。观察一下这个树的形态，是不是当数据是顺序插入时，树的形态一直处于“右倾”的趋势呢？从根本上上看，红黑树并没有完全解决二叉查找树虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待的。

文章图片
现在考虑另一种更为严格的自平衡二叉树AVL树。因为AVL树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。
AVL树顺序插入1~7个节点，查找id=7所要比较节点的次数为3 。

文章图片
AVL树顺序插入1~16个节点，查找id=16需要比较的节点数为4 。从查找效率而言， AVL树查找的速度要高于红黑树的查找效率（AVL树是4次比较，红黑树是6次比较）。从树的形态看来， AVL树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。

文章图片
总结一下AVL树的优点：
不错的查找性能（O（logn）），不存在极端的低效查找的情况。
可以实现范围查找、数据排序。
看起来AVL树作为数据查找的数据结构确实很不错，但是AVL树并不适合做MySQL数据库的索引数据结构，因为考虑一下这个问题：
【MySQL性能优化做得好的人，都懂的索引绝技】数据库查询数据的瓶颈在于磁盘IO ，如果使用的是AVL树，我们每一个树节点只存储了一个数据，我们一次磁盘IO只能取出来一个节点上的数据加载到内存里，那比如查询id=7这个数据我们就要进行磁盘IO三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘IO的次数。

MySQL性能优化做得好的人，都懂的索引绝技

推荐阅读

现金|1.36万亿！上市公司分红金额再创新高！

血糖高怎么办，四个方法帮助改善

跑步|高血压患者能否跑步？中低强度跑步可辅助降压

协助|《中国寺庙建筑》菜园子-协助拍摄

投影幕布材质如何选择，自制幕布的最佳材料

山西不得不说的7个忻州土特产！忻州特产

新生活化妆品官方账号按摩真的能够让鼻子变挺吗？

认定买家少付20万元房款，六旬老伯用热胶棒堵门锁获刑

170cm 115kg 打羽毛球一年多了，但是消退渐渐变粗咋办

孙权为什么要夺取荆州?为什么孙权得到荆州后毫无作为

梦到拖地打扫卫生梦到拖地板

疑存在新冠病毒感染隐患 “加勒比公主”号邮轮被临时“禁止航行”

宋雨琦@娱记曝宋雨琦缺席跑男内幕：很忌惮被Baby压制，连资源都被阻拦

『App小胖子』站桩忍者未必弱，有两个典型案例！，火影手游：无敌位移不一定强

新中国印象——我的故乡

大乌龙！女子“牙痛”难忍，拔了3颗大牙后发现罪魁祸首是这“天下第一痛”……

怎么快速练手臂肌肉呢

父母婚姻不和睦，每天争吵不断，我作为儿女在中间调节无果，劝离也无果，很无力，不知该咋办。?

客户|广发银行广州分行为产业链供应链实体经济“舒筋活血”

韭菜|暑假小男孩发型怎么剪？看看这5种，解暑清凉还帅气