目录
0 引言
针对MySQL索引相关知识点的总结，文中图片来自小林coding
1 InnoDB索引底层的数据结构
1.1 什么是索引
首先还是说一下为什么需要索引，索引就是用来帮助我们快速查找数据用的，最典型的例子就是我们书的目录，当我们要查找某一章节的内容的时候可以先到目录中找到对应章节的页码，然后直接翻到对应页就可以了，这里的目录就可以理解为一个索引。这里只是说一下什么是索引，以及索引是干什么用的，我们innodb引擎的索引与目录这种还是有非常大的区别的，在我们的InnoDB引擎中——索引即数据，数据即索引；目录这种更像是我们MyISAM引擎中的索引结构。
1.2 数据页的基本结构
InnoDB引擎是以页为基本存储单位来管理我们数据的，一个页的大小一般为16KB，我们B+树索引的基本单位就是数据页，也成为索引页（Index页），数据页中有许多的数据，和我们索引最相关的数据有三个，分别是File Header，页目录和记录
- 首先说记录，我们的数据是存放在表中，表中的每一行数据就成为一个记录，所以说我们的列表中的数据时以记录为基本单位存放在数据页中，每条记录除了保存有我们列表中的数据外，还有许多其他信息，其中有一个指针，指向该条记录的下一条记录，所以数据页中的所有记录之间构成了一个单向链表，并且这个单向链表是按照索引列从小到大排列。还需要说明的一点是，每一个数据页都有一个最大记录和最小记录，最小记录就是这个记录链表的起点，最大记录就是这个记录链表的重点
- 然后再来看页目录，在一个数据页中，会有许多的记录，我们又将这些记录进行了分组，并且将每组的最大记录的偏移量保存在我们页目录中的一个槽中
- 最后是File Header，这是数据页中的一部分，这个结构中存储当前数据页相关的信息，其中有两个指针和索引结构有关，分别是数据页的前驱和后驱指针，所以我们的数据页在底层实际上构成了一个双向链表的
1.3 B+树索引
前面说到数据页在底层是一个双向链表，这还并不是innodb引擎存储数据的最终形式，innodb引擎中的数据在底层是一棵B+树，具体的结构就是在数据页构成的双向链表中再向上抽取处若干页，在这些页中，每一条记录保存的是该条记录对应数据页的最小的记录索引列信息和对应数据页的信息。同样我们在这一层还可以继续向上抽取处若干索引页直到只有一个索引页，也就是我们B+树的根索引页为止，这时就构成了一个B+树，也就是我们索引真正的数据结构了，一个可能的结构如下图所示
1.4 B+树索引的特点
通过上面的介绍，可以看到B+树有以下特点
- 叶子节点才是真正存放数据的节点
- B+树各层之间构成双向链表，这是为了方便进行范围查询
- 非叶子节点分为了许多层，通过分层可以增加我们查询的速度
2?B+树中数据的查找
说完了索引的结构，我们来看在B+树中如何查找一条记录，就以上图中的B+树为例子，比如我们要查找第4条记录，具体过程如下
- 在根叶子节点中查找第4条记录，找到最小记录是1的索引页30，这里我们采用的是二分查找，注意若一个数据页中的数据较多我们是先在页目录中进行二分查找后再进行链表的顺序遍历
- 到第30页中查找第4条记录，找到最小记录是3的索引页22，查找方式同1
- 在第22页中查找第4条记录，查找方式还是同1，此时找到第4条记录后直接返回
可以看到查找一条记录在可以利用索引的情况下，我们只需要查询3个数据页就可以查找到相应的数据了，并且在页内是通过二分查找的方式进行搜寻，所以B+树查找数据的效率是非常高的
3 索引的分类
我们的索引大致分为三大类，分别是聚簇索引，二级索引和联合索引，具体介绍如下：
- 聚簇索引：使用记录的主键来进行记录和页的排序；叶子节点存储的是完整的用户记录
- 二级索引：我们也称之为非聚簇索引，叶子节点中保存的记录时索引列和主键
- 联合索引：以多个列的大小作为排序规则的索引，叶子节点保存着索引列和主键信息
4 为什么采用B+树来作为索引
索引还有许多其他的数据结构，比如哈希表，有序数组，平衡二叉搜索树，B树等，来看看使用这些数据结构来做索引会有什么问题
-
哈希表
比如我们要存储一个人的身份信息，可以以身份证为key计算一个哈希值后放到我们的哈希table中，当出现哈希冲突时可以采用拉链法来解决，这种索引结构适用于等值查询的场景
-
有序数组
我们可以根据身份证的大小将所有人的信息有序存储在一个数组中，当需要查询一个人的身份数据时，可以通过二分法来进行查找，但是这类存储结构只适用于静态存储引擎，即这些数据以后并不会再被改动
-
平衡二叉搜索树
使用平衡二叉搜索树我们的查询一个数据的时间复杂度是O(logN)但是在查询的过程中会查询到一些不必要的记录，而且对于大量的数据，使用二叉搜索树存储树的高度会非常大，这会增加我们读取磁盘的次数
-
B树
B树是对平衡二叉搜索树的一种优化，我们的节点不再只有两个左右自己子节点，而是有一个节点数组，但是这种方式仍然会存在一些缺点，B树中的每一个节点既保存了索引也保存的数据，这样我们在查询的过程中会将许多无用的记录读取到内存中，这样大大减小了内存的利用率，而且当我们读取大量数据时需要进行反复的磁盘IO操作
正是因为上面的索引结构有这样或者那样的缺点，所以最终我们的InnoDb引擎并没有选择以上的索引结构，而是使用了B+树，B+树在B树的基础上由进行了以下优化：
-
只有叶子结点才真正存放我们的记录
-
树结构的每一层的节点之间构成一个双向链表
有了上面的优化，我们的B+树相对于B树就有了以下优点：
-
B+树由于只有叶子节点存储实际数据，所以非叶子结点能够存储的索引也就更多，这样B+树相对B树也就更加矮胖，故可以减少查询时磁盘的IO次数
-
B+树有更多的冗余节点，在对记录进行删除和插入操作时并不需要和B树一样为了维护自平衡而进行一些复杂的操作
-
B+树由于节点之间构成双向链表，更加有利于进行范围查询
5 索引建立的规则
-
主键和外键上需要建立索引
-
经常出现在where条件中的字段需要建立索引
-
对于经常参与连接的表，应在连接字段上建立索引
-
经常出现在分组，排序，联合语句中的字段应该创建索引
-
避免选择长字段，文本字段做索引，对于这些字段，若非得建立索引，可以选择前缀索引
-
经常参与计算的字段不能建立索引
-
需要建立联合索引时需要慎重考虑，当能够使用索引下推或索引覆盖来降低查询速度是可以建立联合索引
-
避免建立不必要的索引，索引时占存储空间的
6 几类索引失效的情况
加了索引也不一定走索引，我打算用一个例子来说明索引失效的情况，比如我们有一张表如下：
create table user(
`id` INT(10) primary key,
? ?`name` VARCHAR(30),
? ?`age` INT(10)，
? ?`address` VARCHAR(30)，
? ?key `name` (`name`)
)-
使用左或者左右模糊匹配
比如我们执行
select * from user where name = '%巨人'
或者
select * from user where name = '%巨%'
时我们并不会走name的二级索引，而是会走全表扫描，因为我们的索引时从大到小排序的字符串的比较规则是从第一个字符的ascii码进行比较，但是使用了做左模糊匹配后我们的innodb引擎并不知道%代表着什么，所以无法进行比较从而导致索引失效
-
在索引列上使用函数时
比如我们执行
select * from user where length(name) = 8;
这时我们也不会走name索引查询，因为我们底层的索引保存的就是索引字段而不是length(name)，要解决这个问题我们可以该列表中的这个函数值加上一个索引
-
对索引进行表达式计算
比如我们执行
select * from user where id + 1 = 8;
这时我们的innodb引擎会走全表扫描，而不是利用id索引，这里的原因也是我们底层索引保存的是索引字段，而不是索引表达式，将其修改为以下语句即可利用上索引：
select * from user where id = 7;
-
存在隐式类型转换的时候
我们的mysql在进行字符串和数字的比较的时候是将字符串转换为整数后在进行比较，所以类似下面的SQL语句并不会走索引
select * from user where name = 12345;
在做这个查询时，我们的mysql实际上是先将name转换成整数后再与12345进行比较，由于此时name已经转换成了整数，所以我们原来的name索引也就失效了，但是如下索引是有效的
select * from user where id = '10'
由于我们会自动将字符串10转换为整数10再与字段id进行比较，所以我们的id索引仍然是有用的
-
联合索引非最左匹配
比如我们建立了一个联合索引(a, b, c)
在调用where a = 1 and ...时会用到联合索引，但是在调用where b = 1 and c = 1类似的语句时就不会使用到联合索引，因为我们联合索引排序是先对第一个排，第一个相等就对第二个排，以此类推，所以我们首先看到的是有序的a，而b只能在a有序的条件下才有序，所以非最左匹配的联合索引并不会走联合索引
-
OR语句
OR语句中有一个是没有索引的则可能会导致索引失效，比如以下语句
select * from user where id = 1 or address = '北京'
由于or语句是只要其中一个满足条件即可，所以上面sql还是会走全表扫描
7 覆盖索引
覆盖索引是innodb引擎查询的一种优化，若我们的查询语句用到了二级索引并且我们要查询的字段在二级索引中本身就有，那么我们就会使用覆盖索引，也就是说直接在二级索引中拿到我们需要的数据，不必再回表到聚簇索引中再次查询，可以看到覆盖索引可以提高我们查询的效率
8 索引下推
当我们使用联合索引中进行一些复杂查询的时候，可以在联合索引中使用索引下推来提高我们的查询效率
举个例子，有一张表，其中三个字段建立了一个联合索引(a, b, c)，当我们执行下面语句的：
select * from table where a > 10查询过程是这样的，在联合索引中查找a > 10的记录并一一回表查询到所需的数据
当我们执行下面语句：
select * from table where a > 10 and b < 10查询过程是这样的：在联合索引中查到到a > 10的记录，对于每一条记录我们并不急着回表，而是在联合索引中接着查看这条记录的b是否满足 b < 10，满足则回表查找完整记录，不满足则接着查询下一条记录
