1、索引的建立 / 数据的存储

一条条数据存储到页中后，各个数据页组成了一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。此时，如果我想根据主键值查询一条记录，只能从第一个数据页开始一个页一个页地去查询，这种全表搜索方式的效率想想也不会很高，因此 MySQL 选择为每一个存储了用户数据的数据页建立目录，通过目录确定目标数据在哪个页，然后再在目标页中根据 Page Directory (页目录) + 二分法查询目标数据。这种方式的前提条件就是下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值，即保证数据的有序性，保证二分法的可用。我们称数据页中存储的该种数据为目录项记录，称存储的用户自定义内容为用户项记录，以此来区分。

存储目录项记录、用户项记录用的都是数据页(页面类型一致)，都会为主键值生成 Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。只不过前者存储的列只有主键值(页中最小主键值)和页号，而后者不仅存有用户自定义内容，还有 InnoDB 隐藏列；前者记录头信息的 record_type = 1(代表目录项记录)，后者 record_type = 0(代表普通记录)。因为在这些目录页中只存储了主键值和页号，所以能够记录很多数据，但随着数据的增多，加上页面大小默认为 16KB，迟早会出现一张表不足以记录所有的目录项记录，那就只能再新增一页，这些页也存有上一个和下一个页的页号，以此也构成一个双向链表。

由此可见，随着数据的增多，目录项记录数据页也将变成一个双向链表，那我们再根据主键查询时，又回到了原始问题，即需要一页一页遍历这个双向链表来找到目录项记录页。为了解决这个问题，只能再为创建一个更高的目录，这样的话，就形成了一个多级目录，层层嵌套，最终的小目录(叶子节点)存储的才是真实数据。

在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

以上过程是从叶子节点到根节点构建B+树的角度来描述聚簇索引的构建过程，但是实际上B+树的构建过程是这样的：

每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页。
当页b存储空间用完时，则重复第三步进行页分裂，创建页c用于存储新记录，并将根节点指向页c。

一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引，也就是常说的聚簇索引的顶层常驻内存。

2、重点概念：

2.1 页分裂：

假设此时聚簇索引只有一个叶子节点，且存储空间（16KB）已满，此时想向表中插入一条记录，这条记录的主键id在已有主键的范围内，也就是说这条记录的主键并不是最大的，所以需要新增一个数据页，将旧数据页中的最大记录移到新页中，将新增记录按主键大小顺序插入到旧页中，这个过程就被称为页分裂。

2.2 聚簇索引

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照主键的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+树的叶子节点存储的是完整的用户记录。
- 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
目录项记录中是主键+页号

2.3 非聚簇索引

使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照c2列的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

2.4 回表：

聚簇索引中叶子节点的value部分存储的是行数据，而非聚簇索引中叶子节点的value部分存储的是主键值。当查询中使用到了索引 k，就需要先搜索k索引树找到对应的主键值，再根据主键值搜索主键索引树，这样才能获取到所要查询的值，这个过程就被称为回表。

2.5 覆盖索引：

如果执行的语句是select ID from T where k between 3 and 5，这时只需要查ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引k已经“覆盖了”我们的查询需求，我们称为覆盖索引。

由于覆盖索引可以减少树的搜索次数（减少回表的次数），显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

2.6 索引下推

3、使用

3.1 使用场景

1、用于条件匹配

如果想要借助联合索引优化查询时，必须遵循“最左匹配原则”。

全值匹配
匹配左边的列
匹配列前缀
匹配范围值
精确匹配某一列并范围匹配另外一列

2、用于排序

3、用于分组

3.2 创建索引注意事项

1、只为用于搜索、排序或分组的列创建索引：

对于经常出现在查询列表，但不参与 or 很少参与条件筛选的字段无需创建索引。

2、为列的基数大的列创建索引：

为字段构建索引树的时，需要对字段进行排序，以基数为 1 的字段举例，此时字段值都相同，给它排序没有任何意义（排不排序结果一样），不能提升查询效率，反而在增删改的时候还要对索引树进行维护，因此最好为基数大的列创建索引，为基数太小列的建立索引效果可能不好。

3、索引列的类型尽量小：

数据类型越小，在查询时进行的比较操作越快（CPU层次）
数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。

4、可以只对字符串值的前缀建立索引：

当对长度很长的字符串建立索引时，其索引结构的存储将会花费较大的空间，其次在进行字符串比较时也会花费较多的时间，此时我们可以做一个居中的选择，只为字符串的前几位字符建立索引。

5、只有索引列在比较表达式中单独出现才可以适用索引：

索引列加入运算 or 使用函数会造成索引失效。

6、为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性：

一般我们新增记录时不会指定主键是多少，而是采用自增的形式。因为如果指定主键进行插入的话，很有可能没按主键从小到大的顺序插入，但是为了保证快速查询，MySQL会对不按大小顺序插入的数据进行移位、页分裂，造成不必要的性能损耗。

7、定位并删除表中的重复和冗余索引：

避免出现重复、冗余的索引，以避免对其进行的维护成本。

8、尽量使用覆盖索引进行查询，避免回表带来的性能损耗

4、面试常问

4.1 MySQL索引的底层实现（简单描述）：

它实际上是一个B+树，首先当我们存入数据时，它会基于数据进行一个排序，排序之后，会使用指针以链表的形式连接起来，同时mysql在底层为了进一步优化，基于页的形式进行管理索引，也就是对我们的数据进行了一页一页的存储，默认页的大小为16KB。站在整个B+树这个数据结构来讲，一个三层的B+树可存储进8亿-10亿左右的数据，所以一般的项目用两层足矣。站在一个两层的B+结构来讲，如果基于主键查询，最多动用一次磁盘IO，因为它的顶层是常驻内存的。

4.2 索引为什么是 B+树,而不是 B树呢?

参考资料: B树、B+树详解 - Assassinの - 博客园

原因：

B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

实际情况：

B+Tree中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。
mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

总结：B+Tree只有叶子节点可以存储数据，而B-Tree非叶子节点也必须存储数据，当存储的数据量很大时，会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

4.3 使用聚簇索引的优势：

问题：每次使用辅助索引检索都要经过两次B+树查找，看上去聚簇索引的效率明显要低于非聚簇索引，这不是多此一举吗？聚簇索引的优势在哪？
1.由于行数据和聚簇索引的叶子节点存储在一起，同一页中会有多条行数据，访问同一数据页不同行记录时，已经把页加载到了Buffer中（缓存器），再次访问时，会在内存中完成访问，不必访问磁盘。这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。
2.辅助索引的叶子节点，存储主键值，而不是数据的存放地址。好处是当行数据放生变化时，索引树的节点也需要分裂变化；或者是我们需要查找的数据，在上一次IO读写的缓存中没有，需要发生一次新的IO操作时，可以避免对辅助索引的维护工作，只需要维护聚簇索引树就好了。另一个好处是，因为辅助索引存放的是主键值，减少了辅助索引占用的存储空间大小。

4.4 聚簇索引需要注意什么?

当使用主键为聚簇索引时，主键最好不要使用uuid，因为uuid的值太过离散，不适合排序且可能出线新增加记录的uuid，会插入在索引树中间的位置，导致索引树调整复杂度变大，消耗更多的时间和资源。
建议使用int类型的自增，方便排序并且默认会在索引树的末尾增加主键值，对索引树的结构影响最小。而且，主键值占用的存储空间越大，辅助索引中保存的主键值也会跟着变大，占用存储空间，也会影响到IO操作读取到的数据量。

4.5 为什么要设置主键自增？

保证每一行数据都有一个唯一标识符，使数据具有唯一性
设置主键自增可以使索引建立时避免数据的重排(数据无序时需要排序，使数据按从小到大的顺序排列)，从而提高插入性能

注：数据的重排可能会出现页分裂。比如，将一条记录插入到一个数据页中的两条记录之间时，此时数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。

4.6 索引失效情况：

查询语句中使用LIKE关键字：在查询语句中使用 LIKE 关键字进行查询时，如果匹配字符串的第一个字符为“%”，索引不会被使用。如果“%”不是在第一个位置，索引就会被使用。
查询语句中使用多列索引：多列索引是在表的多个字段上创建一个索引，只有查询条件中使用了这些字段中的第一个字段，索引才会被使用。
查询语句中使用OR关键字：查询语句只有OR关键字时，如果OR前后的两个条件的列都是索引，那么查询中将使用索引。如果OR前后有一个条件的列不是索引，那么查询中将不使用索引。