一、索引数据结构
索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。
MySQL索引的数据结构是B+树，MongoDB索引的数据结构是B-树。
1.1 B-树
特点：多路，非二叉树；每个节点既保存索引，又保存数据；搜索时相当于二分查找。
1.2 B+树
特点：多路，非二叉树；只有叶子节点保存数据；搜索时相当于二分查找；增加了相邻接点的指向指针。
1.3 B-树和B+树的区别
B+树查询时间复杂度固定是O(log(n))，B-树查询复杂度最好是 O(1)。
B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
B+树更适合外部存储，也就是磁盘存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。
注意这个区别相当重要，是基于前面三点的，B-树每个节点即保存数据又保存索引，所以磁盘IO的次数很少，B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。
1.4 MySQL使用B+树作为索引原因解释
MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于MySQL。
MySQL作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。
二、聚簇索引
2.1 聚簇索引
在叶子节点下挂载了索引和行数据的索引。
如果表设置了主键，则主键就是聚簇索引。如果表没有主键，则会默认第一个NOT NULL，且唯一（UNIQUE）的列作为聚簇索引。以上都没有，则会默认创建一个隐藏的row_id作为聚簇索引。
InnoDB的聚簇索引的叶子节点存储的是行记录（其实是页结构，一个页包含多行数据），InnoDB必须要有至少一个聚簇索引。
2.2 非聚簇索引
普通索引也叫二级索引，除聚簇索引外的索引，即非聚簇索引。
InnoDB的普通索引叶子节点存储的是主键（聚簇索引）的值，而MyISAM的普通索引存储的是记录指针。
例：
建表：
mysql> create table user(
-> id int(10) auto_increment,
-> name varchar(30),
-> age tinyint(4),
-> primary key (id),
-> index idx_age (age)
-> )engine=innodb charset=utf8mb4;
id 字段是聚簇索引，age 字段是普通索引（二级索引）
insert into user(name,age) values('张三',30);
insert into user(name,age) values('李四',20);
insert into user(name,age) values('王五',40);
insert into user(name,age) values('刘八',10);
mysql> select * from user;
+----+--------+------+
| id | name | age |
+----+--------+------+
| 1 | 张三 | 30 |
| 2 | 李四 | 20 |
| 3 | 王五 | 40 |
| 4 | 刘八 | 10 |
+----+--------+------+
如果查询条件为主键（聚簇索引），则只需扫描一次B+树即可通过聚簇索引定位到要查找的行记录数据。
如：select * from user where id = 1;
如果查询条件为普通索引（非聚簇索引），需要扫描两次B+树，第一次扫描通过普通索引定位到聚簇索引的值，然后第二次扫描通过聚簇索引的值定位到要查找的行记录数据。
如：select * from user where age = 30;
- 先通过普通索引 age=30 定位到主键值 id=1
-
再通过聚集索引 id=1 定位到行记录数据
普通索引查找过程第一步
普通索引查找过程第二步
回表查询
先通过普通索引的值定位聚簇索引值，再通过聚簇索引的值定位行记录数据，需要扫描两次索引B+树，它的性能较扫一遍索引树更低。
三、联合索引
3.1 联合索引B+树结构
这是一张表格，col1 是主建，col2和col3 是普通字段。那么主索引 对应的 B+树 结构是这样子的：
对col3 建立一个第二索引（辅助索引）：
如果对 col3 和 col2 建立 联合索引（顺序是先col3后 col2）：
原文例子中的数据没有重复数据，所以改了下表数据：
还是对 col3 ，col2建立联合索引，那么 B+树 如下：
3.2 联合索引最左前缀原理
对于复合索引（多列b+tree，使用多列值组合而成的b+tree索引）。遵循最左侧原则，从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持a a,b a,b,c 3种组合进行查找，但不支持 b,c进行查找。当使用最左侧字段时，索引就十分有效。
3.3 联合索引使用
3.3.1联合索引在and查询中应用
1、select a,b,c from test where a=? and b=? and c=?；查询效率最高，索引全覆盖。
2、select a,b,c from test where a=? and b=?；索引覆盖a和b。
3、select a,b,c from test where b=? and a=?；经过mysql的查询分析器的优化，索引覆盖a和b。
4、select a,b,c from test where a=?；索引覆盖a。
5、select a,b,c from test where b=? and c=?；没有a列，不走索引，索引失效。
6、select a,b,c from test where c=?；没有a列，不走索引，索引失效。
3.3.2联合索引在范围查询中应用
select * from test where a=? and b between ? and ? and c=?；索引覆盖a和b，因b列是范围查询，因此c列不能走索引。
select * from test where a between ? and ? and b=?；a列走索引，因a列是范围查询，因此b列是无法使用索引。
select * from test where a between ? and ? and b between ? and ? and c=?；a列走索引，因a列是范围查询，b列是范围查询也不能使用索引。
3.3.3联合索引在排序中应用
select * from test where a=? and b=? order by c；a、b、c三列全覆盖索引，查询效率最高。
select * from test where a=? and b between ? and ? order by c；a、b列使用索引查找，因b列是范围查询，因此c列不能使用索引，会出现file sort。
3.4总结
联合索引的使用在写where条件的顺序无关，mysql查询分析会进行优化而使用索引。但是减轻查询分析器的压力，最好和索引的从左到右的顺序一致。
使用等值查询，多列同时查询，索引会一直传递并生效。因此等值查询效率最好。
索引查找遵循最左侧原则。但是遇到范围查询列之后的列索引失效。
排序也能使用索引，合理使用索引排序，避免出现file sort。
四、覆盖索引
InnoDB存储引擎支持覆盖索引(covering index，或称索引覆盖)，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是付出索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。
只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。例如：select id,age from user where age = 10;
回表：即在辅助索引上根据辅助索引找到了主键，再根据主键回到主键索引的B+树上再次索引查询数据。
4.1 如何实现覆盖索引
常见的方法是：将被查询的字段，建立到联合索引里去。
1、如实现：select id,age from user where age = 10;
explain分析：因为age是普通索引，使用到了age索引，通过一次扫描B+树即可查询到相应的结果，这样就实现了覆盖索引。
2、实现：select id,age,name from user where age = 10;
explain分析：age是普通索引，但name列不在索引树上，所以通过age索引在查询到id和age的值后，需要进行回表再查询name的值。此时的Extra列的NULL表示进行了回表查询。
为了实现索引覆盖，需要建组合索引idx_age_name(age,name)
drop index idx_age on user;
create index idx_age_name on user(`age`,`name`);
explain分析：此时字段age和name是组合索引idx_age_name，查询的字段id、age、name的值刚刚都在索引树上，只需扫描一次组合索引B+树即可，这就是实现了索引覆盖，此时的Extra字段为Using index表示使用了索引覆盖。
4.2 特殊举例（摘自《MySQL技术内幕InnoDB存储引擎第2版》5.6.3节）
联合索引userid_2（userid,buy_date）,一般情况，我们按照buy_date是无法使用该索引的，但特殊情况下：查询语句是统计操作，且是覆盖索引，则按照buy_date当做查询条件时，也可以使用该联合索引
mysql> explain select count(*) from buy_log where buy_date >= '2011-01-01' and buy_date < '2011-02-01';
+--+-----------+-------+-----+-------------+--------+-------+----+----+------------------------+
|id|select_type| table |type |possible_keys| key |key_len|ref |rows|Extra |
+--+-----------+-------+-----+-------------+--------+-------+----+----+------------------------+
| 1| SIMPLE |buy_log|index| NULL |userid_2| 8 |NULL| 7 |Using where; Using index|
+--+-----------+-------+-----+-------------+--------+-------+----+----+------------------------+
1 row in set (0.00 sec)
五、索引失效
5.1 创建索引
普通的索引的创建：
CREATE INDEX indexName ON TableName(field);
复合索引的创建：
CREATE INDEX indexName ON TableName(field1, field2 ...);
删除索引：
DROP INDEX indexName;
5.2 explain
id: SELECT 查询的标识符. 每个 SELECT 都会自动分配一个唯一的标识符
select_type: SELECT 查询的类型
table: 查询的是哪个表
partitions: 匹配的分区
type: join 类型
possible_keys: 此次查询中可能选用的索引
key: 此次查询中确切使用到的索引
ref: 哪个字段或常数与 key 一起被使用
rows: 显示此查询一共扫描了多少行. 这个是一个估计值
filtered: 表示此查询条件所过滤的数据的百分比
extra: 额外的信息
5.3 索引查询失效的几个情况
5.3.1、like 以%开头，索引无效；当like前缀没有%，后缀有%时，索引有效
5.3.2、or语句前后没有同时使用索引。当or左右查询字段只有一个是索引，该索引失效，只有当or左右查询字段均为索引时，才会生效
5.3.3、组合索引，不是使用第一列索引，索引失效。
5.3.4、数据类型出现隐式转化。如varchar不加单引号的话可能会自动转换为int型，使索引无效，产生全表扫描。
5.3.5、在索引列上使用 IS NULL 或 IS NOT NULL操作。索引是不索引空值的，所以这样的操作不能使用索引，可以用其他的办法处理，例如：数字类型，判断大于0，字符串类型设置一个默认值，判断是否等于默认值即可。
5.3.6、在索引字段上使用not，<>，!=。不等于操作符是永远不会用到索引的，因此对它的处理只会产生全表扫描。 优化方法： key<>0 改为 key>0 or key<0。
5.3.7、对索引字段进行计算操作、字段上使用函数。（索引为 emp(ename,empno,sal)）
5.3.8、当全表扫描速度比索引速度快时，mysql会使用全表扫描，此时索引失效。
索引失效分析工具：
可以使用explain命令加在要分析的sql语句前面，在执行结果中查看key这一列的值，如果为NULL，说明没有使用索引。
explain命令的详细用法，可以查看这篇文章：https://segmentfault.com/a/1190000008131735
参考文章
Mysql索引查询失效的情况
MySQL 的覆盖索引与回表的使用方法
mysql索引数据结构
最简单方式理解为什么MongoDB索引选择B-树，而 Mysql 选择B+树
复合(联合)索引失效解析
联合索引（复合索引）在B+树上的结构
MySQL索引背后的数据结构及算法原理
