一、索引的常见模型

索引的出现是为了提高数据查询的效率。实现索引的方式有很多种，比较常见的数据结构有：哈希表、有序数组和搜索树。

索引是在存储引擎层实现的，不同存储引擎索引工作方式不同。

1.1 哈希表

哈希表：键值存储的数据结构，输入待查找的key，找到对应的value。通过一个哈希函数把key换算成一个确定的位置，然后把value放在数组的位置。

优点：适用于等值查询的场景，增加新的记录速度会很快。

缺点：由于不是有序的，区间查询速度很慢。

1.2 有序数组

数组按索引字段的递增顺序保存。适用于静态存储引擎，不会再修改的数据。

优点：等值查询和区间查询可以用二分查找快速查到对应数据。

缺点：插入数据就必须挪动后面所有的数据。

1.3 N叉树

为了在查询中尽量少读磁盘，访问尽量少的数据块，需要使用N叉树，而不是二叉树。这里的N取决于数据块的大小。

广泛应用于数据库引擎中。每一个索引在InnoDB中对应一棵B+树。

二、InnoDB索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表成为索引组织表。

InnoDB使用B+树索引模型，所以数据都是存在B+树中的。每一个索引在InnoDB中对应一棵B+树。

假设我们有一个主键列为ID的表T，表中有个字段k，并且k上有索引。(ID，K)值分别为(100，1)、(200，2)、(300，3)、(500，5)和(600，6)。两个索引对应的B+树如下：

主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引。

非主键索引的叶子节点存的是主键的值。在InnoDB里，非主键索引也被称为二级索引。

如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树。
如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID值，再到ID索引树搜索一次，这个过程称为回表。

三、索引维护、自增主键

B+树为了维护索引的有序性，在插入新值需要做必要的维护。以上图为里，若插入新的行ID为700，则只需要在R5的记录后面插入一个新的记录。若新插入的ID值为400，就要挪动后面的数据空出位置（在底层的数据页）。更糟的情况是，如果R5所在的数据页满了，根据B+树算法，这是会需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂。

InnoDB聚簇索引的节点也是以页为单位的，默认大小为16k，可以通过参数调整。在聚簇索引的叶子节点中，其存放的是数据。如果一个数据页存满了，MySQL 就会去申请一个新的数据页来存储数据。

如果主键为自增 id ，MySQL 在写满一个数据页的时候，直接申请另一个新数据页接着写就可以了。
如果主键是非自增 id，为了确保索引有序，
- 要写入记录的目标页可能已经写入到磁盘而不只是存在于内存中，又或者目标页还没有被加载到内存中，InnoDB 在插入前需要先找到并从磁盘中读取目标页到内存中去，这会产生大量的磁盘随机 IO。
- 因为写入是乱序的，InnoDB 需要频繁地做页分裂操作，一遍为新的行分配空间。页分裂需要移动大量数据。
- 有序频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。

除了考虑性能外，还可以从存储空间的角度来看。若表中有一个唯一字段，比如字符串类型的身份证号，那么该用自增字段做主键，还是身份证号做主键？

由于每个非主键索引的叶子节点都是主键的值，如果用身份证号（20字节）做主键，那么每个非主键索引叶子节点的占用空间远远大于主整型字段做主键。因此，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。

有没有什么场景适用于业务字段直接做主键？
只有一个索引，该索引是唯一索引（没有非聚簇索引）

四、覆盖索引

若对上图的表T执行 select * from T where k between 3 and 5。会先去非聚簇索引K的B+树中找到对应的ID值，再回到主键索引搜索记录，这个回到主键索引树搜索的过程称为回表。

若执行的语句是 select ID from T where k between 3 and 5。这时只需要查ID，而ID的值以及在K的非聚簇索引的叶子节点上，不需要回表了。也就是说，在这个查询里面，索引K已经覆盖了我们的查询请求，我们称为覆盖索引。

需要注意的是，在引擎内部使用覆盖索引在索引K上其实扫描三个记录，分别是叶子节点3，5，6三个记录。由于6不符合条件，所以返回给Server层只有2条记录，因此MySQL认为扫描行是2。

五、最左前缀

定义：

-- 在进行条件匹配时，必须从一个索引的最左边的列开始，并且不能跳过中间的列
-- 具体举例如下：（之前建立的索引中列的顺序，name、status、address）-- 1. 以name 作为条件进行查询，符合该法则，走索引
explain select * from tb_seller where name="小米科技";
-- 2. 以name, status 作为条件进行查询，符合该法则，走索引
explain select * from tb_seller where name="小米科技" and status="1";
-- 3. 以name, address 作为条件进行查询，不符合该法则（跳过了status），但是会走索引，仅以name为索引
explain select * from tb_seller where name="小米科技" and address="北京";
-- 4. 以status, name 作为条件进行查询，符合该法则（没有跳过某列），走索引
explain select * from tb_seller where status="1" and name="小米科技";
-- 5. 以 status，address 作为条件进行查询，不符合该法则（跳过了name），不走索引，最左侧都不存在
explain select * from tb_seller where status="1" and address="北京";-- 走索引，但是只走name, status。不会走address，因为address 在索引中位于范围查询列status的右边
explain select * from tb_seller where name='小米科技' and status > '1' and address='北京';
-- 索引结构为name，status，address。而范围查询位于address，因此应该是使用了三个索引字段。原因是MySQL 优化器会对其进行优化，所以在SQL 语句中范围查询的位置不是很重要，而范围查询的字段才是关键。当然按索引顺序写会减少优化器的开销。
explain select * from tb_seller where name='小米科技' and  address > '北京' and status = '1';

我们以（name，age）这个联合索引来分析。

索引项时按照索引定义里面出现的字段顺序排序的。当逻辑要求查找到所有名字为“张三”的人时，可以快速定位到ID4，然后遍历得到所有需要的结果。

如果要查找的是所有名字第一个字是“张”的人，也能用上这个所以，查找到第一个符合条件的记录时ID3，然后向后遍历知道不满足条件为止。

只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以使联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

建立联合索引时，如何安排索引内的字段顺序？评估标准是索引的复用能力。

第一原则是如果通过调整顺序，可以少维护一个索引，那么往往这个顺序就是优先考虑的。

六、索引下推

最左前缀可以用于在索引中定位记录。那些不符合最左前缀的部分会怎么样？

以联合索引（name，age）为例。如果现在有一个需求：检索出表中名字第一个字是张，而且年龄是10岁的所有男孩：

select * from tuser where name like ‘张%’ and age = 10 and ismale = 1；

首先根据“张%”在索引树找到第一个满足条件的记录ID3，然后判断其他条件是否满足：

在MySQL5.6之前，只能从ID3开始一个个回表，到主键索引找出数据行（这个过程InnoDB不会去看age的值），再对比字段值。

而MySQL5.6引入索引下推优化，在索引遍历过程中，对索引中包含的字段（age）先做判断，直接过滤掉不满足条件的记录，减少回表次数。

七、索引失效

1、全值匹配：对索引中所有列都指定具体值，联合索引(name,status,address)。

explain select * from tb_seller where name='小米科技' and status='1' and address='北京市'\G;

2、最左前缀法则：如果索引了多列，要遵守最左前缀法则。指的是查询从索引的最左前列开始，并且不跳过索引中的列。

3、联合索引中范围查询右边的列，不能使用索引。如下查询在联合索引树走到了status>1的结点之后开始遍历。使用了前两个字段的索引，第三个字段只能遍历查找。

-- 走索引，但是只走name, status。不会走address，因为address 在索引中位于范围查询列status的右边
explain select * from tb_seller where name='小米科技' and status > '1' and address='北京';
-- 索引结构为name，status，address。而范围查询位于address，因此应该是使用了三个索引字段。原因是MySQL 优化器会对其进行优化，所以在SQL 语句中范围查询的位置不是很重要，而范围查询的字段才是关键。当然按索引顺序写会减少优化器的开销。
explain select * from tb_seller where name='小米科技' and  address > '北京' and status = '1';

4、不要在索引列上进行运算操作，否则索引将失效。

5、字符串不加单引号，造成索引失效。在查询时，没有对字符串加单引号，MySQL的查询优化器，会自动的进行类型转换，造成索引失效。

6、尽量使用覆盖索引（只访问索引的查询（索引列完全包含查询列）），减少select * 。

explain的extra字段：