1. 索引分类

索引是一种快速查询表中内容的机制，类似于新华字典的目录。

1.1 存储

B+ tree 索引（下文重点讲）

哈希索引：不需要做排序、范围查询的需求。
Full-index 全文索引

1.2 应用

普通索引：即一个索引只包含单个列，一个表可以有多个单列索引。
唯一索引：索引列的值必须唯一，但允许有空值。
复合索引：一个索引包含多个列。

唯一索引和主键索引区别：主键就是唯一索引，但是唯一索引不一定是主键。唯一索引可以为空，但是空值只能有一个，主键不能为空。

1.3 聚集

聚集索引
表记录的排列顺序和索引的排列顺序一致。(类似拼音查字)
1. 一个表中只能拥有一个聚集索引。
2. 默认是在主键上建立聚集索引的，没有主键是唯一索引，再或者是_rowid。
3. 聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，因为只要找到第一个索引值记录，其余的连续性的记录在物理表中也会连续存放，一起就可以查询到。
4. 缺点是新增比较慢，因为为了保证表中记录的物理顺序和索引顺序一致，在记录插入的时候，会对数据页重新排序。

非聚集索引
表记录的排列顺序和索引的排列顺序不一致。(类似偏旁部首查字)
1. 一个表中可以拥有多个非聚集索引。
2. 索引的逻辑顺序与磁盘上行的物理存储顺序不同，非聚集索引在叶子节点存储的是主键和索引列，当我们使用非聚集索引查询数据时，需要拿到叶子上的主键再去表中查到想要查找的数据。这个过程就是我们所说的回表。

2. B树和B+树

2.1 B 树（也写作 B- 树）

关键字分布在整棵树的所有节点。
任何一个关键字出现且只出现在一个节点中。
搜索有可能在非叶子节点结束。
其搜索性能等价于在关键字全集内做一次二分查找。如下图所示：

2.2 B+ 树

非叶子节点的子树指针与关键字个数相同。
非叶子节点的子树指针 P[i]，指向关键字属于 [k[i],K[i+1]) 的子树（注意：区间是前闭后开)。
为所有叶子节点增加一个链指针。
所有关键字都在叶子节点出现。

2.3 对比二叉树

B不是代表二叉（binary），而是代表平衡（balance）。

实际实现B+Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B+Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d(节点数)是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B+Tree差很多。

2.4 对比B树

B+树的高度比较稳定，因为它的非叶子节点不会保存数据，只保存键值和指针的情况下，一个页能承载大量的数据。

B树它的非叶子节点也会保存数据的，同样的一行数据大小是1kb，那么它一页最多也只能保存16个指针，在大量数据的情况下，树高就会速度膨胀，导致IO次数就会很多，查询就会变得很慢。

B+ 树的磁盘读写代价更低。
B+ 树的内部没有指向关键字具体信息的指针，所以其内部节点相对 B 树更小，如果把所有关键字存放在同一块盘中，那么盘中所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO 读写次数就降低了。
树的查询效率更加稳定。
B+ 树所有数据都存在于叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率相当。而 B 树可能在非叶子节点就停止查找了，所以查询效率不够稳定。
B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。

2.5 B+ 树存储多少数据

InnoDB存储引擎它也是有最小存储单位的，叫做页（Page），默认大小是16kb。页可以放一行一行的数据（叶子节点），也可以放主键+指针（非叶子节点）。

为了减少磁盘I/O。磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k）。 InnoDB 引擎一个页的大小是 16K。(mysql5.7后，提供了一个设定page大小的参数innodb_page_size，默认值是16K。)

假如一行数据大小是1k，那么理论上一页就可以放16条数据。那一页可以放多少主键+指针呢？

假如我们的主键id为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16384 / 14 = 1170，就是说一个页上可以存放1170个指针。

一个指针指向一个存放记录的页，一个页里可以放16条数据，那么一颗高度为2的B+树就可以存放 1170 * 16=18720 条数据。同理，高度为3的B+树，就可以存放 1170 * 1170 * 16 = 21902400 条1k数据的记录。

理论上就是这样，在InnoDB存储引擎中，B+树的高度一般为2-4层，就可以满足千万级数据的存储。但是每个页不可能只放数据本身。首先每个页都有一些固定的格式，比如文件头部、页面头部、文件尾部这些，所以实际会比较少一些。

实际测试中发现: 数据大概在1300万左右，B+树就会增加树高到4层。

查找数据的时候，一次页的查找代表一次IO，那我们通过主键索引查询的时候，其实最多只需要2-4次IO就可以了。

3. 聚集索引和非聚集索引

3.1 InnoDB 和 MyISAM 区别

InnoDB 是由一个聚集索引和非聚集索引构成。MyISAM 全是非聚集索引。

但是无论是什么，底层的数据结构都是用 B+树实现的。

1. MyISAM 非聚集索引

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
非聚簇索引的主键索引和辅助索引两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已。
主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。
由于索引树是独立的，通过辅助键检索无需访问主键的索引树。
索引文件（.MYI）和数据文件（.MYD）文件是分离的, 索引文件仅保存数据记录的地址(指针去查找)。

2. InnoDB 聚集索引

聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。
聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。
由于实际的数据页只能按照一棵 B+ 树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在 B+ 树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。
聚集索引的存储并不是物理上连续的，而是逻辑上连续的。
如果一个主键被定义了，那么这个主键就是作为聚集索引。如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引。如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增。
聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。

3.2 InnoDB的聚集索引和非聚集索引

在数据库中，B+ 树的高度一般都在 2～4 层，这也就是说查找某一键值的行记录时最多只需要 2 到 4 次 IO，这倒不错。因为当前一般的机械磁盘每秒至少可以做 100 次 IO，2～4 次的 IO 意味着查询时间只需 0.02～0.04 秒。

1. InnoDB 是由一个聚集索引和非聚集索引构成

数据库中的B+树索引可以分为聚集索引（clustered inex）和辅助索引（secondary index）。辅助索引有时也称非聚集索引（non-clustered index）。

但是不管是聚集还是辅助的索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。

2. InnoDB 非聚集索引

叶子节点并不包含行记录的全部数据（只有索引字段本身的数据，废话）。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。

如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的一个数据页。

3.3 总结

例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。

再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段int作为主键则是一个很好的选择。

4. 索引机制

4.1 查看索引

1	SHOW INDEX FROM table_name;

Cardinality：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality表的行数应尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此索引。

Null：是否索引的列含有NULL值。可以看到idx_b这里为Yes，因为定义的列b允许NULL值。

4.2 Cardinality

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。

但是这个值并不是实时更新的，如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。

对两条基本一样的语句执行EXPLAIN，但是最终出来的结果不一样：一个使用索引，另外一个使用全表扫描。这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间，对应用程序下的几张核心表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。

在InnoDB存储引擎中，Cardinality统计信息的更新发生在两个操作中：INSERT和UPDATE。但是表中1/16的数据已发生过变化，或者stat_modified_counter＞2 000 000 000

4.3 覆盖索引

InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。

对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1，primary key2，…，key1，key2，…）。例如，下列语句都可仅使用一次辅助联合索引来完成查询：

SELECT key2 FROM table WHERE key1=xxx；
SELECT primary key2,key2 FROM table WHERE key1=xxx；
SELECT primary key1,key2 FROM table WHERE key1=xxx；
SELECT primary key1,primary key2，key2 FROM table WHERE key1=xxx；

覆盖索引的另一个好处是对某些统计问题而言的。

1	SELECT COUNT(*)FROM buy_log;

InnoDB存储引擎并不会选择通过查询聚集索引来进行统计。由于buy_log表上还有辅助索引，而辅助索引远小于聚集索引，选择辅助索引可以减少IO操作。

1 2	SELECT COUNT(*)FROM buy_log WHERE buy_date＞='2011-01-01'AND buy_date＜'2011-02-01'

表buy_log有（userid，buy_date）的联合索引，这里只根据列b进行条件查询，一般情况下是不能进行该联合索引的，但是这句SQL查询是统计操作，并且可以利用到覆盖索引的信息，因此优化器会选择该联合索引。

4.4 使用某个索引

如果用户确定指定某个索引来完成查询，那么最可靠的是使用FORCE INDEX，而不是USE INDEX。

5. 索引技术优化

5.1 Multi-Range Read 优化（多范围读）

将查询范围分成多个不重叠的部分，并使用范围扫描技术来查找每个部分中的匹配行。

MySQL5.6 版本开始支持 Multi-Range Read（MRR）优化。Multi-Range Read 优化的目的就是为了减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，这对于 IO-bound 类型的 SQL 查询语句可带来性能极大的提升。

通常情况下，在执行查询时，MySQL会遍历整个索引树，以找到所有匹配的行。但是，对于大型数据集，这种方式可能会导致性能下降，因为它需要大量的磁盘I/O和CPU资源。

MRR通过将索引分成多个范围并在内存中缓存结果来避免这种情况。在使用MRR时，MySQL会尝试将查询范围分成多个不重叠的部分，并使用范围扫描技术来查找每个部分中的匹配行。这种方式可以有效地减少磁盘I/O和CPU消耗，从而提高查询性能。

1
2
3

SELECT*FROM t
WHERE key_part1＞=1000 AND key_part1＜2000
AND key_part2=10000;

若没有Multi-Read Range，此时查询类型为Range，SQL优化器会先将key_part1大于1000且小于2000的数据都取出，即使key_part2不等于1000。待取出行数据后再根据key_part2的条件进行过滤。这会导致无用数据被取出。

倘若启用了Multi-Range Read优化，优化器会先将查询条件进行拆分，然后再进行数据查询。就上述查询语句而言，优化器会将查询条件拆分为（1000，1000），（1001，1000），（1002，1000），…，（1999，1000），最后再根据这些拆分出的条件进行数据的查询。

5.2 Index Condition Pushdown 优化（索引下推）

减少回表，索引级别的判断

在不使用ICP的情况下，在使用非主键索引（又叫普通索引或者二级索引）进行查询时，存储引擎通过索引检索到数据，然后返回给MySQL服务器，服务器然后判断数据是否符合条件。
在使用ICP的情况下，如果存在某些被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器。
索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少MySQL服务器从存储引擎接收数据的次数。

当优化器选择 Index Condition Pushdown 优化时，可在执行计划的列 Extra 看到 Using index condition 提示。

假设某张表有联合索引(zip_code，last_name，first_name)，并且查询语句如下：

SELECT*FROM people
WHERE zipcode='95054'
AND lastname LIKE'%etrunia%'
AND address LIKE'%Main Street%';

若不支持 Index Condition Pushdown 优化，则数据库需要先通过索引取出所有 zipcode 等于 95054 的记录，然后再过滤 WHERE 之后的两个条件。

若支持 Index Condition Pushdown 优化，则在索引取出时，就会进行 WHERE 条件的过滤，然后再去获取记录。这将极大地提高查询的效率。当然，WHERE 可以过滤的条件是要该索引可以覆盖到的范围。

Index Condition Pushdown 优化可以将查询效率在原有 MySQL 5.5 版本的技术上提高 23%，而再同时启用 Mulit-Range Read 优化后，性能还能有 400% 的提升！

6. 建索引原则

6.1 最左前缀匹配原则

非常重要的原则. mysql会一直向右匹配直到遇到范围查询(>、<、between、like) 就停止匹配, 复合索引的第一个, 必须先查, 才能继续。

如果建立(a,b)顺序的索引

查询 b = 2 ，是匹配不到(a,b)索引的
查询 a = 1 and b = 2 或者 a = 1 又或者 b = 2 and a = 1 都可以，因为优化器会自动调整a,b的顺序。

如果建立(a,b,c,d)顺序的索引

a = 1 and b = 2 and c > 3 and d = 4 ，d是用不到索引的，因为c字段是一个范围查询，它之后的字段会停止匹配。

如果建立(a,b,d,c)顺序的索引

a = 1 and b = 2 and c > 3 and d = 4 , 索引则都可以用到，a,b,d的顺序可以任意调整。

6.2 最左前缀匹配原则！！！

左边的必须在才走索引!!!
(col1, col2, col3)这个复合索引的所有前缀就是(col1), (col1, col2), (col1, col2, col3), 包含这些列的查询都会启用索引查询.
其他所有不在最左前缀里的列都不会启用索引, 即使包含了联合索引里的部分列也不行. 即上述中的(col2), (col3), (col2, col3) 都不会启用索引去查询.
注意, (col1, col3)会启用(col1)的索引查询.

6.3 尽量选择区分度高的列作为索引

区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1。（越大越好）。

而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录。

索引列的基数越大，索引的效果越好。例如，存放出生日期的列具有不同的值，很容易区分行，而用来记录性别的列，只有”M”和”F”,则对此进行索引没有多大用处，因此不管搜索哪个值，都会得出大约一半的行。

6.4 离散度更高的索引应该放在复合索引的前面

因为离散度高索引的可选择性高

1	SELECT count(DISTINCT user_id), count(DISTINCT lottery_id), count(DISTINCT award_id) FROM lottery_user_log

看下面的结果, 越大的适合在前面

count(DISTINCT user_id),count(DISTINCT lottery_id),count(DISTINCT award_id) 
56135										 1													12

适合创建 (user_id, award_id, lottery_id)

6.5 使用短索引

如果对字符串列进行索引，应该指定一个前缀长度，可节省大量索引空间，提升查询速度；

例如，有一个CHAR(200)列，如果在前10个或20个字符内，多数值是唯一的，那么就不要对整个列进行索引。对前10个或者20个字符进行索引能够节省大量索引空间，也可能会使查询更快。

6.6 尽量的扩展索引，不要新建索引

比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。

6.7 = 和 in 可以乱序

比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式。

6.8 索引列不能参与函数计算

比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’)。

6.9 强制类型转换会用不到索引

phone varchar(20), index(phone)。注意phone是字符串类型。

1 2	select phone where phone = '1000000' # 用到索引 select phone where phone = 1000000 # 用不到索引

6.10 索引的列不要为 null

也能建立索引, 但是会造成不符合预期的行为。

6.11 索引数量控制

单表索引控制在5个以内
复合索引字段最好不超过5个

6.12 在合适的列上创建索引

频繁作为 WHERE 查询条件的字段
经常 GROUP BY 和 ORDER BY 的列
DISTINCT 后面的字段

6.13 什么时候要创建索引

表经常进行 SELECT 操作。
表很大(记录超多)，记录内容分布范围很广。
列名经常在 WHERE 子句或连接条件中出现。

6.14 什么时候不要创建索引

表经常进行 INSERT/UPDATE/DELETE 操作
表很小(记录超少)
列名不经常作为连接条件或出现在 WHERE 子句中
字段内容重复很多

7. 头脑风暴

B+树走索引是从上往下，全表扫描是从左往右。
InnoDB只能有一个聚集索引，索引和数据在一起。
InnoDB其他的索引就做辅助索引，走索引后，找到的数据时在用聚集索引，再次回表查询。
多范围读MRR，是辅助索引排序后，直接一起回表，减少磁盘的随机访问。
索引下推，是一个复合索引，查询的时候，直接在存储器过滤。
建立索引：最左匹配，区分度高，不要为 null，扩展索引，数量控制。
查询索引：复合索引，不参与函数，不强转类型。

8. 参考资料

锁和事务 https://www.liuvv.com/p/9762ea3e.html
MVCC https://www.liuvv.com/p/a0f7945d.html