MySQL索引

索引介绍

索引是一种用于快速检索数据的数据结构，索引本质是按照某种规律排序好的数据结构

书的目录，字典前面的目录都是一种索引。在书中，当我们需要直接翻到第几章时，只需要查看目录，就能找到这一章的开头；在字典中，如果我们需要找到某个字，首先我们需要知道目录的规律，也就是按字母排序，然后找到该字所在页数，这样就可以快速翻到该字所在页数。

如果没有目录，也就是书的索引，我们想要找到某个某一章，就需要一章一章的找，在字典中，想要找到某个字，需要一个一个字的比对，这是非常费时费力的！

索引的底层数据结构存在很多类型，最常见的索引结构有：B树、B+树、Hash树和红黑树。在MySQL中，无论存储引擎是Innodb还是MyIsam，都使用B+树作为索引结构！

为什么索引快？

1、在没有索引时，想要找到某个数据，需要对每个数据进行比对。索引实际上是由很少的数据来唯一标识这个数据的方法。所以，在有索引时，想要找到某个数据，只需要根据索引查找就行，而索引的数据量远小于全部数据，所以索引查找数据非常快。
2、索引实际上也是将数据按一定规律进行排序之后形成的，这个排序操作是在后台运行的，就可以将代价转移到没有查询操作的时候，相当于提前进行了预查询。

索引的优缺点

优点：

• 使用索引可以大大加快数据的检索速度（减少索引的数据量）：创建索引的主要原因
• 通过创建唯一性索引，就可以保证通过这个索引查到的有且只有一个数据！

缺点：

• 创建和维护索引需要耗费许多时间。在对表中的数据进行增删改的时候，如果有索引，那么索引也需要动态的修改，会降低SQL执行效率。
• 索引也需要使用物理文件存储，会占用一定的空间。

通常情况下，索引查询都是比全表查询快。但是在数据量不大的情况下，使用索引多少有点画蛇添足了。

索引数据结构

Hash表

哈希表是一种key-value结构的数据，通过key可以快速取出对应的value，因此哈希表可以在接近O(1)的时间复杂度下快速找到数据！

哈希表这种特性源自于哈希算法(也叫散列算法)。其本质是将不同的key映射到不同的value上。

但是哈希算法可能会将多个不同的key映射到同一个value，最后得到的index相同。因此哈希算法直接影响了冲突的概率。选择更好的哈希算法可以很大程度上减少冲突的概率，但是要解决哈希冲突，还是得通过：开放地址法（线性探测、平方探测）、再哈希法、链地址法等解决。

哈希表作为索引的缺点：不支持顺序查询和范围查询！
顺序查询和范围查询在数据库中非常常见，所以哈希表并不适合作为经常要进行顺序和范围查询的数据库的索引。

二叉查找树

二叉查找树是一种基于二叉树的数据结构，其主要特点有：

1、左子树所有节点的值均小于根节点的值
2、右子树所有节点的值均大于根节点的值
3、左右子树也分别为二叉查找树

缺点：当一个有序的队列插入二叉查找树时，就会出现只有右子树或者只有左子树的情况，树会退化成线性链表！因此二叉查找树的性能非常依赖于它的平衡程度，所以不适合作为MySQL数据库的底层索引数据结构！

AVL树

自平衡二叉树（AVL）在进行节点的插入时会通过旋转操作自动调整树的平衡，确保左右字数的高度差不超过一。但是在插入和删除操作中会进行旋转操作来保持平衡，因此会有较大的计算开销，从而降低了查询性能。
并且，在使用AVL树时，每个树的节点仅存储一个数据，每次进行磁盘I\O时只能读取一个节点的数据，如果查询的数据分布在多个节点上，就需要进行多次磁盘I\O。
磁盘的I\o相对于处理器来说是一项非常耗时的操作，在设计数据库索引是，需要有限考虑如何最大限度的减少磁盘的I\O操作

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡转台。二叉树的定义如下：

1、节点是红色或黑色
2、根节点是黑色
3、每个叶子结点都是黑色的空节点
4、每个红色节点的两个子节点都是黑色（从每个叶子节点到根节点的所有路径上不能出现两个连续的红色节点）
5、从任一结点到其每个叶子节点的所有路径都包含相同数目的黑色节点

红黑树不追求严格的平衡，而是大致的平衡。虽然牺牲了一点查询效率，但是红黑树的插入和删除操作效率大大提高，只需要进行O(1)次数的旋转和变色操作，即可保持基本平衡状态！

红黑树在TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树，对于在内存中的数据来说，红黑树的表现是非常优异的。
但是如果在磁盘中，还是需要进行大量的磁盘操作，因此也不适合用于构造索引。

B树和B+树

B树	B+树
所有节点既存放键（key） 也存放数据（data）	只有叶子节点存放key和value 其他内节点只存放key
叶子节点都是独立的	叶子结点之间有一条引用链指向与它相邻的叶子节点
检索过程相当于对范围内的每个节点的关键字做二分查找，可能还没到达叶子结点，检索就结束了	任何查找过程都是从根节点到叶子节点的过程，叶子结点的顺序检索很明显
进行范围查询时，首先要找到查找的线下，然后对b树进行中序遍历，直到找到上限	只需要对链表进行遍历即可

综上：B+树与B树相比，具备更少的I\O次数、更稳定的查询效率和更适用于范围查询这些优势。

索引类型总结

按照数据结构维度划分：

• B Tree索引：MySQL里默认和最常用的索引类型，只有叶子结点存储 value，非叶子节点只有指针和 key。存储引擎 MyISAM 和 InnoDB 实现B Tree 索引都是使用 B+ Tree，但二者的视线方式不一样。
• 哈希索引：类似键值对的形式，一次即可定位。
• 空间数据索引（R Tree） 索引：一般不会使用，仅支持 geometry 数据化类型，优势在于范围查找，效率较低，通常使用 ElasticSearch 代替。
• 全文索引：对文本的内容进行分词，进行搜索。目前只有CHAR、VARCHAR、TEXT列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

按照底层存储方式角度划分：

• 聚簇索引（聚集索引）：索引结构和数据一起存放的索引，InnoDB中的主键索引就属于聚簇索引。
• 非聚簇索引（非聚集索引）：索引结构和数据分开存放的索引，二级索引（辅助索引）就是属于非聚簇索引。MuSQL 的 MyISAM 引擎，不管是主键还是非主键，使用的都是非聚簇索引。

按照应用维度划分：

• 主键索引：加速查询，列值唯一（不可以有 NULL），表中只可以有一个
• 普通索引：仅加速查询。
• 唯一索引：加速查询，列值唯一（可以有 NULL）。
• 覆盖索引：一个索引包含（或者说是覆盖）所有需要查询的字段的值。
• 联合索引：多列值组成的索引，专门用于组合搜索，其效率大于索引合并。
• 全文索引：对文本的内容进行分词，进行搜索。目前只有CHAR、VARCHAR、TEXT列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

主键索引

使用数据表主键生成的索引的就是主键索引。

一张数据表只能有一个主键，且主键不能为 NULL，不能重复。

在MySQL的 InnoDB 的表中，当没有显式指定表的主键时，InnoDB 将会自动先检查表中是否有唯一索引且不允许存在 NULL 的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个64Byte的自增主键。

二级索引

二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键，也就是说，通过二级索引，可以定位到主键的位置。

二级索引包含：唯一索引，普通索引、签注索引等。

1. 唯一索引(Unique Key)：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL ，一张表允许创建多个唯一索引，建立唯一索引的目的大部分时候是为了该属性列的数据的唯一性，而不是查询效率。
2. 普通索引(Index):普通索引的唯一作用就是为了加快查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
3. 前缀索引(Prefix):前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小，因为只取前几个字符。
4. 全文索引(Full Text):全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。MySQL5.6之前只有MyISAM引擎支持全文索引，5.6之后InnoDB也支持了全文索引。

二级索引：

聚簇索引与非聚簇索引

聚簇索引（聚集索引）

聚簇索引介绍：聚簇索引（clustered index）即索引结构和数据一起存放的索引，并不是一种单独的索引类型。InnoDB中的主键索引就属于聚簇索引。

在 MySQL 中，InnoDB 引擎的表的 '.ibd' 文件就包含了该表的索引和数据，对于 InnoDB 引擎表来说，该表的索引（B+树）的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

聚簇索引的优缺点：

优点：

• 查询速度非常快：聚簇索引的查询速度非常快，因为整个B+树本身就是一颗多叉平衡树，叶子结点也都是有序的，定位到索引的节点，就相当于定位到了数据。相比于非聚簇索引，聚簇索引少了一次读取数据的I/O操作。
• 对排序查找和范围查找优化：局促索引对于主键的排序查找和范围查找速度非常快。

缺点：

• 依赖于有序的数据：因为B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似字符串或UUID这种又长又难比较的数据，插入和查找的速度肯定比较慢。
• 更新代价大：如果对索引列的数据被修改时，那么对应的索引也将会被修改，而且聚簇索引的叶子节点还存放着数据，修改代价肯定是比较大的，所以对于主键索引来说，主键一般是不可被修改的。

非聚簇索引（非聚集索引）

非聚簇索引介绍：非聚簇索引（NON-Clustered Index）即索引结构和数据分开存放的索引，并不是一种单独的索引类型。二级索引（辅助索引）就属于非聚簇索引。MySQL的MyISAM引擎，不管是主键还是非主键索引，使用的都是非聚簇索引。

非聚簇索引的叶子节点并不一定存放数据的指针，因为二级索引的叶子节点就存放的是主键，根据主键再返回表查询数据。

非聚簇索引的优缺点：
优点：
更新代价比聚簇索引要小。非聚簇索引的更新代价没有聚簇索引大，非聚簇索引的叶子结点是不存放数据的。

缺点：

• 依赖于有序的数据：和聚簇索引一样，非聚簇索引也依赖于有序的数据
• 可能会二次查询（回表）：最大的缺点。当查询到索引对应的指针或主键后，可能还需要根据指针或主键再到文件或表中查询。

非聚簇索引一定会回表查询吗（覆盖索引）？
非聚簇索引不一定回表查询

在用户使用SQL查询用户名时，用户名刚好创建了索引，这个情况下，无需回表查询！！

覆盖索引和联合索引

覆盖索引

如果一个索引包好（或者说覆盖）所有需要查询的字段的值，我们就称之为覆盖索引（Couvering Index）。我们知道在InnoDB存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次，这样就会比较慢。而覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！

覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了，而无需回表查询

测试：一个名为cus_order的表，表中只有id、score、name三个字段。

以score和name两个字段建立联合索引，执行一下sql语句

SELECT `score`,`name` FROM `cus_order` ORDER BY `score` DESC;   #降序排序

查询的数据score、name正好是索引的字段，因此使用EXPLAIN命令分析这条SQL语句，发现这条SQL语句成功使用了覆盖索引。

联合索引

使用表中的多个字段创建索引，也就是联合索引，也叫组合索引或复合索引。

最左匹配原则

最左匹配原则指的是，在使用联合索引时，MySQL会根据联合索引中的字段顺序，从左至右依次到查询条件中去匹配，如果查询条件中存在与联合索引中最左侧字段相匹配的字段，则就会使用该字段过滤一批数据，直至联合索引中全部字段匹配完成，或在执行过程中遇到范围查询（如>、<）才会停止匹配。对于>=、<=、BETWEEN、like前缀匹配的范围查询，并不会停止匹配。所以我们在使用联合索引是，可以将区分度高的字段放在最左边，这也可以过滤更多数据。

索引下推（Index Condition Pushdown）ICP

MySQL5.6之前通过非主键索引查询时，存储引擎通过索引查询数据，然后将结果返回给MySQL server层，在server层判断是否符合条件。
MySQL5.6之后的版本可以使用索引下推，当存在索引列为判断条件时，MySQL server层将这一部分判断条件传递给存储引擎，然后存储引擎会筛选出符合传递条件的索引项，即在存储引擎层根据索引条件过滤掉不符合条件的索引项，然后经过一次回表查询得到结果，奖结果返回给MySQL server。

例子：假如有一张表user，表有四个字段id、name、level、tool

id	name	level	tool
1	大王	1	电话
2	小王	2	手机
3	小李	3	BB机
4	大李	4	马儿

建立联合索引（name，level）

匹配行为第一个字为“大”，并且level为1的用户，sql语句为
注意：

• 组合索引满足最左匹配！
• 第一个条件 name like "大%" 不是等值匹配，所以 level = 1 用不上（name，level） 组合索引了

select * from user where name like "大%" and level = 1;

在5.6之前，该语句的执行流程如下图：

根据前面说的“最左匹配原则”，该语句在搜索索引树时，智能匹配到名字第一个字是“大”的记录，然后对ID=1、ID=4逐个回表，到主键索引上找出相应的记录，在对比level这个字段的值是否符合。
也就是先根据第一个索引进行过滤，之后，对第二个索引进行逐一判断，将每个记录一条一条取出来回表。
因此，需要回表2次！！！

在MySQL 5.6之后，执行流程如下图：

SQL server层直接将两个条件推送到存储引擎层，存储引擎层在索引（name，level）内部直接判断level是否等于1，对于不等于1的记录，直接记录并跳过！
使用索引下推后，由于在查找过程中已经对level=1判断过，因此直接回表一次，根据主键查询id=1的数据即可，因此只需要回表一次！

https://blog.csdn.net/crazymakercircle/article/details/130492417