为什么添加索引能提高查询速度？

红太狼 2023-02-11 07:24 4阅读 0赞

当使用条件查询语句时，我们可以在条件查询的字段上添加索引来提高查询性能，为了便于理解MySQL的索引，我们先了解一些与索引相关的算法。MySQL中使用最频繁的就是B+树索引，而B+树是借鉴了二分查找法、二叉查找树、平衡二叉树、B树的一些思想构建的，所以我们要依次了解这些算法，最后再学习B+树。

## 1. 二分查找法 ##

二分查找法的查找过程是：将记录按顺序排列，查找时先以有序列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将查找范围缩小为左半边；如果要找的元素值大于该中点元素，则将查询范围缩小为右半边。以此类推，直到找到需要的值。  
比如：从1、2、3、4、5、6、7、8、9这几个数字中找到6，首先找到中点位置是5，发现5小于6，则找5的右半边位置，右半边的中点是7，然后将5与7比较，发现5小于7，则查找7的左半边位置，7的左半边中点是6，于是返回结果。  
发现用了3词就找到了6这个数字，如果用顺序查找法得需要查询6次，显然**二分查找法的效率比顺序查找法更高**。

## 2. 二叉查找树 ##

二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值，并且每个节点最多只有两个子树。如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70]  
如果3后面拖更多的数字，二叉查找树的效率会变得很低。如果想让查找性能变好，需要这个树是平衡的，因此就有了平衡二叉树。

## 3. 平衡二叉树 ##

平衡二叉树满足二叉查找树的定义，另外必须满足任何节点的两个子树的高度差最大为1。  
比如我们要从1、2、3、5、6、7、9几个数字中找到某一个数字，如果使用平衡二叉树进行查找，结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 1]  
如果要找到值为6的记录，则先找到根节点5，而6大于5，所以需要查找的是5的右子树，而又因为6小于7，则因为找7的左子树，找到6这条记录，一共找了3次，如果用顺序查找法，找到6这个记录就需要找5次。  
但是平衡二叉树每个节点最多只有两个分支，如果数据量比较大，要经理多层节点才能查询在叶子节点的数据。如果在平衡二叉树的基础上，每个节点可以有多个分支，那即使在叶子节点的数据，是不是查询效率也比较高呢？这就引出了B树结构。

## 4. B树 ##

B树可以理解为一个节点可以拥有多余2个子节点的多叉查找树。B树中同一键值不会出现多次，要么在叶子节点，要么在内节点上。比如用1、2、3、5、6、7、9这些数字构建一个B树结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 2]  
与平衡二叉树相比，B树利用多个分支节点，减少获取记录时所经历的节点数。B树因为每个节点都包含key值和data值，因此如果data比较大时，**每一页**存储的key会比较少；当数据比较多时，同样会有要经历多层节点才能查询在叶子节点的数据的问题，因此，便有了B+树。  
PS：索引树的节点是放在数据页中的，每个数据页大小是固定的，节点中放key和data，当data比较大的时候，key的数量就少了。

## 5. B+树 ##

B+树是B树的变体，定义基本与B树一致，与B树的不同点：

*  所有叶子节点中包含了全部关键字的信息；
 *  各叶子节点用指针进行连接；
 *  非叶子节点只存储key的信息，这样相对B树，可以增加每一页中存储key的数量；
 *  B树是纵向扩展，B+树是横向扩展的；  
    在B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点上。B+树中并不是一个二叉树。  
    还是以1、2、3、5、6、7、9举例，它的结构如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 3]  
    与B树最大的区别就是：  
    它的键一定会出现在叶子节点上，同时也有可能在非叶子节点中重复出现。而B树中同一键值不会出现多次。

### 5.1 B+树索引 ###

B+树的高度一般都在2~4层，所以查找某一行数据最多只需要2到4次IO。而没索引的情况，需要逐行扫描，明显效率低很多，这也就是为什么添加索引能提高查询速度。  
B+树索引并不能找到一个给定键值的具体行，B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到缓冲池中，在内存中通过二分查找法进行查找，得到需要的数据。  
InnoDB中B+树索引分为聚集索引和辅助索引。

#### 5.1.1 聚集索引 ####

InnoDB的数据是按照主键顺序存放的，而聚集索引就是按照每张表的主键构造成一棵B+树，它的叶子节点存放的是整行数据。InnoDB的主键一定是聚集索引。  
由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能有一个聚集索引。查询优化器倾向于采集聚集索引，因为聚集索引能够在B+树索引的叶子节点上直接找到数据。  
聚集索引对于主键的排序查找和范围查找速度非常快。  
比如：某数据表的数据如下：  
![在这里插入图片描述][20200522151756343.png]  
它的聚集索引的大致结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 4]  
可以看出：

*  该表根据主键值创建了B+树结构；
 *  每个叶子节点包含了整行数据；

#### 5.1.2 辅助索引 ####

聚集索引的叶子节点存放了整行数据，而InnoDB存储引擎辅助索引的叶子节点并不会放整行数据，而存放的是键值和主键ID。当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引树查找到对应记录的主键，然后通过主键索引来找到对应的行数据。  
比如一棵高度为3的辅助索引树中查找数据，那么需要对这颗辅助索引树遍历3次找到指定主键，如果聚集索引树的高度也为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此获取数据一共需要6次IO访问。  
继续拿上述的表数据进行分析，它的辅助索引idx\_a结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 5]  
可以看出：

*  根据a字段的值创建了B+树结构；
 *  每个叶子节点保存的是a字段自己的键值和主键ID

假设有如下这条SQL语句：

SELECT * FROM t WHERE a = 3;

它先通过a字段上的索引树，得到主键ID为3，然后再到ID的聚集索引树上找到对应的行数据。  
而下面这条SQL：

SELECT * FROM t WHERE id = 3;

查询到的结果是一样的，而自行过程只需要搜索ID的聚集索引树。  
所以，可以看出辅助索引查询过程比聚集索引多扫描一棵索引树，所以，**我们应该尽量使用主键作为条件进行查询**。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522132818650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522135338552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200522140812155.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200522143404199.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70
[20200522151756343.png]: https://img-blog.csdnimg.cn/20200522151756343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200522151823833.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200522154702287.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTg2MDE1,size_16,color_FFFFFF,t_70