MySQL的索引结构简析

Bertha 。 2023-01-07 10:27 93阅读 0赞

先来讲讲没有索引的情况下是如何来查询数据的吧

首先我们应该知道数据都是存储在了一个个的数据页中，在我的上一篇博客《[图解MySQL页分裂][MySQL]》中具体讲了数据页的格式，简单来说，数据页中包含了一行行的数据行，且数据行之间是单向链表连接，每个数据页中的数据行的主键都是递增的（如果不是的话则会进行页分裂保证递增），每个数据页之间是双向链表连接的

这里假设两种情况，一种是数据量较少，一个数据页就能存储所有的数据的情况，此时如果是根据主键查询，此时会利用到一个页目录的概念，拿正常的目录做类比的话，标题就是**主键**，页码对应的是**槽位**，每个槽位都存在着一组数据行，此时不利用索引，使用主键进行查询的话，就会在页目录中使用二分法定位到我们要找的主键（主键是递增），然后找到具体的槽位，再去槽位中遍历数据行找到我们需要的数据；如果不是使用主键查询的话，此时就只能在数据页中遍历数据了，效率很差

再来说说第二种情况，也就是数据量较大，数据分布在多个数据页中的情况，此时都只能对数据页进行遍历，将数据页加载到buffer pool缓存页中，如果是主键查询，就二分法遍历查询，如果是非主键，就只能一个个遍历过去，这就是所谓的全表扫描  
![无索引查询数据][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xPX1lVTg_size_16_color_FFFFFF_t_70_pic_center]  
我们知道了全表扫描查询效率很低之后，就需要解决这个问题，解决方案就是索引，索引存储的格式就类似于上面的页目录，里面存储的是数据页号和最小主键值，当数据页很多的时候，也就需要很多的数据页和最小主键值，此时就会生成索引页，就是将索引数据记录在数据页中

那么有了索引页之后是如何查询的呢？这里面也用到了二分法，举个例子，如下图所示  
![索引图][20210125230837723.png_pic_center]  
假设我们要查询的数据主键值为6，此时二分法会先将所有数据页一分为二，此时我们可以判断数据在数据页3和数据4之间，再次进行二分法查询，就可以发现数据是在数据页3中，因为主键值6大于数据页3的最小主键值，并且小于数据页4的最小主键值，这种查询就是最简单的基于主键索引的查询

当索引页太多的时候，此时就会以一个树形结构来存储，MySQL中默认的索引结构是B+树，看起来就像下图（网上图很多，请容我盗个图）  
![B+树索引][B]  
使用B+树的话，亿级数据一般也只需要三阶即可，B+树跟B树比起来，只有最下面的叶子节点才会存储数据，因为每层的数据页大小有限，那么只存储键值的话，就能存储更多的键值了，看起来也就是更矮更胖

在B+树索引的结构下，查询数据也是根据二分法来做，每次都可以定位到一半的索引数据，最后缩小到叶子节点的数据就能查询到我们想要的值了

关于索引的数据结构其实就是这么简单，也有很多文章具体分析过了，我这里就不赘述了，至于其他的索引知识，我们下次再讲

[MySQL]: https://blog.csdn.net/LO_YUN/article/details/112061699
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xPX1lVTg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/b2e0bc14b0714e76984070b7a5e7fcde.png
[20210125230837723.png_pic_center]: /images/20221119/15e8bef2032946c4809a03f5eaca5447.png
[B]: https://img-blog.csdnimg.cn/20210125231924602.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xPX1lVTg==,size_16,color_FFFFFF,t_70#pic_center