目录
面试中，经常被问到的MySQL索引是什么数据结构？索引有那些分类？ 开发中，经常遇到的明明加了索引，为啥会失效？索引应该怎么调优？
索引数据结构
MySQL索引的作用加快数据访问。
对于索引的设计，我们不妨思考下目前已知的数据结构： hash表、平衡二叉树 (AVL)、B树、B+树。
hash表
如下：数据结构为数据链表
显而易见，如使用hash表有如下弊端：
1、插入数据的时候存在hash碰撞或者hash冲突，需要设计比较好的hash算法，否则会造成存储空降的浪费；
2、当进行范围查找的时候，必须挨个进行匹配，效率极低，不适合做范围查询；
平衡二叉树
如下：数据结构为平衡二叉树
一棵平衡二叉树能容纳多少的结点呢？
这跟树的高度是有关系的，假设树的高度为 h，那每一层最多容纳的结点数量为 2^(n-1)，整棵树最多容纳节点数为 2^0+2^1+2^2+...+2^(h-1)。
这样计算，100w 数据树的高度大概在 20 左右，也就是说从有着 100w 条数据的平衡二叉树中找一个数据，最坏的情况下需要 20 次查找。
根据平衡二叉树的特性，想要存储更多的数据，需要将树变深，变深之后会导致更多的I/O次数，影响效率；
如使用平横二叉树有如下弊端：
1、存储数据有限；
2、如存储过多数据，访问数据需要更多的I/O，影响效率；
B树
如下为数据结构
从数据结构上来看，对于平衡二叉树，B树每个节点能存储更多的数据。但B树的节点不仅存储键值，还存储数据。而innodb中页的默认大小是16K，存同样的数据，也会导致树的阶数（高度）增加。
如使用B树有弊端如下：
1、数据存储有限，查找数据磁盘I/O增多，数据查询效率变低；
2、对于范围查找、排序不适合；
B+树
对比B树以及其他数据结构，使用B+树有如下优势： 1、非叶子节点只存储索引，可以存储更多，且对比B树更矮胖，I/O次数更少； 2、叶子节点链式前后管理，方便范围查询；
索引分类
聚簇索引和非聚簇索引
按照主键值区分有两大分类：主键索引（聚簇索引）、非主键主键（非聚簇索引）；
聚簇索引跟非聚簇索引的区别在于：聚簇索引的叶子节点存放主键值跟数据，非聚簇索引的叶子节点存放非主键索引以跟主键索引值。
所以通过非聚簇索引查找的过程是先找到该索引Key对应的聚簇索引的Key，然后再拿聚簇索引Key到主键索引树上查找对应的数据，这个过程称为回表！
因此，DBA建议表在创建的时候需要指定主键值，没有主键的表是没有灵魂的。而如果不指定主键，MySQL也会默认生成一个主键值。
类型区分
按照索引类型区分有如下分类：
- 唯一索引：Unique，唯一键
- 普通索引：Normal
- 全文索引：Full Text
- 组合索引：联合索引，包含2个及以上列组成的索引
前面章节讲过，索引的结构是B+树，如有多个索引，就有多颗B+树；有多个索引的话，实际的数据只在主键索引那棵树存一份；
索引失效原因
对于使用了索引，但是没有生效的场景有如下原因：
- 使用模糊查询：比如左模糊或者全模糊都会导致索引失效，比如'%肖'和'%肖%'，但右模糊索引是有效的，比如'肖%'；
- 索引字段使用函数表达式：比如select name from user where substring(name,1,3)='abc';
- 查询的时候索引包含表达式运算：比如select id from user where id/2=100;
- 不满足联合索引最左前缀匹配：比如（A,B,C）的联合索引，where条件使用C或B或B,C都会失效；
- 查询类型不匹配：比如age为varchar类型，查询语句为select name from user where age = 16,值没加引号；
索引调优
1、避免建立过多索引，多使用组合索引（单表索引不超过5个）；
2、经常用于查询条件的字段建议加索引，通过索引查询，速度更快；
3、频繁group by、order by的字段建议生成索引，可以大幅提高分组和排序效率；
4、数据具有唯一性，建议生成唯一性索引，在数据库的层面，保证数据正确性；
5、区分度较低的字段不建议加索引，比如性别字段（区分度超过30%，建议不加索引）；
6、频繁更新的字段不建议加索引，重建索引时，会增加数据库的开销；
7、尽量使用覆盖索引；
索引知识点
回表
先通过数据库非主键索引扫描出数据所在的行，再通过行主键id取出索引中的数据，即基于非主键索引的查询需要多扫描一棵索引树；
索引覆盖
如果一个索引包含（或者说覆盖）所有需要查询的字段的值，不需要回表查询，我们就称之为索引覆盖；
最左匹配原则
对多个字段同时建立的组合索引（有顺序，abc、acb 是完全不同的两种联合索引）以联合索引（a,b,c）为例，建立这样的索引相当于建立了索引 a、ab、abc 三个索引。另外组合索引实际还是一个索引，并非真的创建了多个索引，只是产生的效果等价于产生多个索引；
索引下推
MySQL 5.6 引入了索引下推优化。可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表次数；
?