1、简介
索引是帮助MySQL高效获取数据的排好序的数据结构。MySQL索引的建立对于MySQL的高效运行是很重要的，可以大大提高MySQL的检索速度。
索引是在存储引擎中实现的，因此，每种存储引擎的索引都不一定完全相同，并且每种存储引擎也不一定支持所有索引类型。MySQL中索引的存储类型有两种，即BTREE和HASH，具体和表的存储引擎相关。MyISAM和InnoDB存储引擎只支持BTREE索引；MEMORY和HEAP存储引擎可以支持HASH和BTREE索引。应该创建索引的列：
在经常需要搜索的列上，可以加快搜索的速度
在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构
在经常用在连接（JOIN）的列上，这些列主要是一外键，可以加快连接的速度
在经常需要根据范围（<，<=，=，>，>=，BETWEEN，IN）进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的
在经常需要排序（order by）的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；
在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度
不应该创建索引的列：
对于那些在查询中很少使用或者参考的列不应该创建索引：若列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求
对于那些只有很少数据值或者重复值多的列也不应该增加索引：取值很少的列，如性别。在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度
对于那些定义为text, image和bit数据类型的列不应该增加索引：这些列的数据量要么相当大，要么取值很少
当该列修改性能要求远远高于检索性能时，不应该创建索引。（修改性能和检索性能是互相矛盾的）
2、索引的分类
1）逻辑分类
普通索引和唯一索引
普通索引是MySQL中的基本索引类型，允许在定义索引的列中插入重复值和空值
唯一索引要求索引的列的值必须唯一，但允许有空值。如果是组合索引则列的组合值必须唯一
主键索引是一种特殊的唯一索引，不允许有空值
单列索引和组合索引
单列索引即一个索引只包含单个列，一个表可以有多个单列索引
组合索引是指在表的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用。使用组合索引时遵循最左前缀集合
全文索引
全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建
空间索引
空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING和POLYGON。MySQL使用SPATIAL关键字进行扩展，使得能够用创建正规索引类似的语法创建空间索引。创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MyISAM的表中创建
2）物理分类
聚簇索引
非聚簇索引
聚簇索引不是单独的一种索引类型，而是一种数据的存储方式，指的是将数据和索引放到了一起，找到索引的时候也就找到了数据。
非聚簇索引自然就是表示索引和数据是分开存储的。
聚簇索引的优点：
数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的排序查找和范围查找速度非常快
聚簇索引的缺点：
插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键（主键列不要选没有意义的自增列，选经常查询的条件列才好，不然无法体现其主键索引性能）
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。
3、索引结构
MySQL数据库中的常见索引结构有多种，常用Hash，B-树，B+树等数据结构来进行数据存储。
为什么不选择使用二叉搜索树或红黑树
特点：二叉树，左节点的值小于根节点，右节点的值大于根节点
缺点：二叉搜索树有可能退化成链表，那么查询效率极低，故数据库中不会采用二叉树作为索引结构，而红黑树虽然防止了树的退化，但数据多时树的高度仍然太高
二叉搜索树的缺点主要在于树的高度可能太高，从而查询需要多次进行磁盘IO（树的深度加深一层，意味着多一次查询，对于数据库磁盘而言，就是多一次IO操作，导致查询效率低下），故我们需要选择一种更扁平的数据结构以减少磁盘IO的次数。
不难想到让每个节点保存更多的信息，并且增加每个节点的子节点数量。
1）B-Tree
B树(Balanced-Tree)是一种多路搜索树，树中每个结点至多有m个孩子，且具有如下特点：
关键字集合分布在整棵树中
任何一个关键字出现且只出现在一个结点中
非叶子结点的关键字个数 = 指向子节点的指针个数-1
搜索有可能在非叶子结点结束
所有叶子节点位于同一层
搜索性能等价于在关键字全集内做一次二分查找
自动层次控制
2）B+Tree
B+树是B-树的一个变种，也是一种多路搜索树，但是有如下区别：
- 非叶子结点的子树指针与关键字个数相同
- 为所有叶子结点增加一个链指针，从而方便叶子节点的范围遍历
- 所有关键字都在叶子结点出现，且链表中的关键字恰好是有序的
- 不可能在非叶子节点命中
3）Hash
哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。Memory存储引擎使用Hash。
Hash索引仅仅能满足"=",“IN"和”<=>"查询，不能使用范围查询。
4）索引结构比较
B+树比B树更适合做索引
B+ 树的磁盘读写代价更低：
B+树的数据都集中在叶子节点，分支节点只负责指针（索引）
B 树的分支节点既有指针也有数据
这将导致B+树的层高会小于B树的层高，也就是说B+ 树平均的磁盘IO次数会小于B树
B+ 树的查询效率更加稳定：B+树的数据都存放在叶子节点，故任何关键字的查找必须走一条从根节点到叶子节点的路径。所有关键字的查询路径相同，每个数据查询效率相当
B+树更便于遍历：
B+树的数据都存储在叶子结点中，分支结点均为索引，遍历只需要扫描一遍叶子节点即可
B树因为其分支结点同样存储着数据，需要进行一次中序遍历按序来搜索
B+树更擅长范围查询：B+树叶子节点存放数据，数据是按顺序放置的双向链表。B树范围查询只能中序遍历
B+树占用内存空间小：B+树索引节点没有数据，比较小。在内存有限的情况下，相比于B树索引可以加载更多B+树索引
Hash索引优缺点
如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值
如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索
哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）
哈希索引也不支持多列联合索引的最左匹配规则
在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在哈希碰撞问题
4、存储引擎
MySQL采用插件式的存储引擎，并为我们提供了许多存储引擎，每种存储引擎有不同的特点。我们可以根据不同的业务特点，选择最适合的存储引擎。注意：存储引擎是基于表的。
1）磁盘上的体现
ibd文件中既保存了索引也保存了数据
MyISAM：每个表会创建三个文件，表名.frm文件、表名.myd文件和表名.myi文件
myd文件用于保存数据，myi文件用保存索引
其中frm文件存储的是表的定义，即保存每个数据表的元数据信息，表结构定义等
frm文件和存储引擎无关，任何存储引擎的数据表都有frm文件（MySQL8之后不存在，InnoDB中是直接保存在ibd文件，MyISAM中是保存在sdi文件）
2）存储结构
InnoDB使用B+树存储索引，除了主键索引为聚簇索引，其他索引均为非聚簇索引（一个表中只能有一个聚簇索引，但可以有多个非聚簇索引）
叶子节点包含了完整的数据记录，这就是聚簇索引（如上图）。因为InnoDB的数据文件（.idb）按主键聚集，所以InnoDB必须有主键（MyISAM可以没有），如果没有显示指定主键，则选取首个为唯一且非空的列作为主键索引，如果还没具备，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
此处的节点也称为页，是InnoDB最小的存储单元，默认为16KB（最小可设置为4KB，最大可设置为64KB）。页作为磁盘与内存之间交互的基本单位（与操作系统的页不同），也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把16KB的内容刷新到磁盘中。而在数据库中不管是读取一行还是多行，都是将这些行所在的页进行加载，即数据库IO操作的最小单位是页。
File Header：文件头，描述页的信息
Page Header：页头，页的状态信息
Infimum + Supremum：最大和最小记录，这是两个虚拟的行记录
User Records：用户记录，存储行记录内容
Free Space：空闲记录，页中还没有被使用的空间
Page Directory：页目录，存储用户记录的相对位置
File Tailer：文件尾，校验页是否完整
B+树的查询是从上往下一层层查询的，一般情况下我们认为B+树的高度保持在3层以内是比较好的，也就是上两层是索引，最后一层存数据，这样查表的时候只需要进行3次磁盘IO就可以了(实际上会少一次，因为根节点会常驻内存)，且能够存放的数据量也比较可观。
如果数据量过大，导致B+树变成4层了，则每次查询就需要进行4次磁盘IO了，从而使性能下降。所以我们才会去计算InnoDB的3层B+树最多可以存多少条数据。
每一条索引记录当中都包含了当前索引的值 、 一个 6字节 的指针信息 、一个 5 字节的行标头，用来指向下一层数据页的指针。假设我们的主键id为 bigint 型，也就是8个字节，那索引页中每行数据占用的空间就等于19 字节。每页可以存大约801条索引数据。那么前两层总共便可以存放800*800=640000个索引。
又因为最大行长度略小于页的一半（因为每个页还留了空间给其他内容，如果超过了这个值则会分一些数据到溢出页中），所以可以认为每个页最少可以存放两条数据；而对于一张字段很少的表（如1个长整型和2个整型字段），可能一行只需要x+x+5+8+2*4≈30个字节。
即最多可以存放640000*(16KB/30B)≈3亿个数据，最少可以存放2倍的640000即大概120万条数据。
以下是MyISAM的主键索引存储图，存储的只是索引的地址值：
3）联合索引
从本质上来说，联合索引还是一棵B+树，不同的是联合索引的键值数量不是1而是大于2。对于联合索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用。即使用联合索引时遵循最左前缀原则
举例，假设在id、name、age字段上已经成功建立了一个名为MultiIdx的组合索引。索引行中按id、name、age的顺序存放，索引可以搜索id、（id,name）、（id, name, age）字段组合。如果列不构成索引最左面的前缀，那么MySQL不能使用局部索引，如（age）或者（name,age）组合则不能使用该索引查询。
4）查询
索引生效的查询
先到数据页的页目录根据主键进行二分查找，根据目录定位到具体的哪个槽位，然后到那个槽位里，遍历槽位里每一行数据，就能够快速找到主键所对应的数据。走了聚簇索引的查询（主键查询）只需要查询一次即可拿到信息，而走了非聚簇索引的查询会现在非聚簇索引出的树中找到主键之后，再根据主键索引去查数据内容，即一般需要查两次（除非要查的信息只是主键和索引列），这个过程也称为回表。
不走索引的查询：
直接从第一个数据页开始遍历所有数据页，从第一个数据页开始，把第一个数据页从磁盘上读取到内存buffer pool的缓存页里，然后根据数据页内部的单向链表来遍历查找，如果第一个数据页没有查找到想要的数据，那么就根据链表去找下一个数据页，读取到buffer pool里，然后一行行在缓存内部查找数据，这样依次的查找每个数据页，依次类推，循环往复。如图所示：
对于这样的查找是全表扫描，在没有任何索引数据的时候，就是对数据表进行全表扫描，根据双向链表依次把磁盘上的数据页加载到缓存页里去，然后在缓存页内部来查找数据。采用这样将数据一页一页的加载到BufferPool中，判断是否满足条件的数据，直到找到需要的数据采用停止扫描。如果数据量大的话，采用全表扫描会严重影响数据库的性能，所以在写SQL的时候，都会考虑索引的问题，让自己的SQL都可以走到索引。
5、索引相关问题
1）为什么推荐使用整型自增主键而不是选择UUID：
UUID是字符串，比整型消耗更多的存储空间，这就会导致每一页存储的索引索引记录以及叶子结点存储的数据记录变少，会导致相同高度存储的数据量变少
在B+树中进行查找时需要跟经过的节点值比较大小，整型数据的比较运算比字符串更快速
自增的整型索引在磁盘中会连续存储，在读取一页数据时也是连续；UUID是随机产生的，读取的上下两行数据存储是分散的，不适合执行where id > 5 && id < 20的条件查询语句。
在插入或删除数据时，整型自增主键会在叶子结点的末尾建立新的叶子节点，不会破坏左侧子树的结构；UUID主键很容易出现这样的情况，B+树为了维持自身的特性，有可能会进行结构的重构，更容易出现页的分裂，消耗更多的时间。
2）为什么非主键索引结构叶子节点存储的是主键值：
保证数据一致性和节省存储空间
3）索引数量也多越好吗？
索引并非越多越好，一个表中如有大量的索引，不仅占用磁盘空间，还会影响INSERT、DELETE、UPDATE等语句的性能，因为在表中的数据更改时，索引也会进行调整和更新。
4）建立索引应该遵循的原则：
避免对经常更新的表进行过多的索引，并且索引中的列要尽可能少。应该经常用于查询的字段创建索引，但要避免添加不必要的字段。
数据量小的表最好不要使用索引，由于数据较少，查询花费的时间可能比遍历索引的时间还要短，索引可能不会产生优化效果。
在条件表达式中经常用到的不同值较多的列上建立索引，在不同值很少的列上不要建立索引。比如在学生表的“性别”字段上只有“男”与“女”两个不同值，因此就无须建立索引，如果建立索引不但不会提高查询效率，反而会严重降低数据更新速度。
当唯一性是某种数据本身的特征时，指定唯一索引。使用唯一索引需能确保定义的列的数据完整性，以提高查询速度。
在频繁进行排序或分组（即进行group by或order by操作）的列上建立索引，如果待排序的列有多个，可以在这些列上建立组合索引。
5）索引失效的可能情况：
使用组合索引时没有遵循“最左前缀”原则；
在索引列上做任何操作，例如计算、函数、类型转换，会导致索引失效而转向全表扫描；
尽量使用覆盖索引（只访问索引列的查询），减少 select * 覆盖索引能减少回表次数；
MySQL在使用不等于（!=或者<>）的时候无法使用索引会导致全表扫描；
LIKE以通配符开头（%abc）MySQL索引会失效变成全表扫描的操作；
字符串不加单引号会导致索引失效（可能发生了索引列的隐式转换）；
少用or，用它来连接时会索引失效。
参考文章：
🔥我说MySQL每张表最好不超过2000万数据，面试官让我回去等通知？ - 掘金 (juejin.cn)
MySQL没有索引是如何进行数据查询
MySQL体系构架、存储引擎和索引结构
