什么是索引

索引就好比是书的目录，可以显著提高数据库查询的效率。例如像一本很厚的书，在没有目录的情况下要查到你想要看的知识点，都不知要找到什么时候，但通过目录我们可以很快的查询到对应的内容。

索引的数据结构

哈希表

哈希表是一种以K-V值存储的数据结构，这样，我们只需要输入K值，就会很快得到需要的V值。K值经过哈希计算得出，这样避免不了哈希碰撞问题，解决的方法是当K值哈希后一样时，可以采用列表的形式存储相应的数据，在查询时再经过列表逐一比对得到V值。哈希表在等值查询的时候非常快，但会存在下面问题：
1、无法进行范围查询
2、无法利用索引进行排序
3、存在哈希碰撞问题，当哈希碰撞过于严重时很影响效率
4、不支持最左前缀

有序数组

有序数组可以很好的解决范围查询的问题，查询数据也可以用二分法很快的找到对应的值。但在中间插入一条数据时，需要把后面的数据都往后移，代价太大。

二叉搜索树

二叉搜索树每个节点最多只有两个子节点，并且左节点小于等于父节点，右节点大于父节点。这样很好解决了等值查询、范围查询、数据插入的问题。但因为只有两个节点，这样数据量很大的时候，会产生很高的层级，并且数据库中这些层级不全是存放在内存中的（内存只会存放一级，有时还会存放进二级）而是存放磁盘中。这样就造成了多次IO操作，严重影响性能。

B+树

在二叉搜索树的基础上进行优化，每个节点至多可以达到拥有1200个子节点，子节点按照顺序存放。显著减少IO操作。

主键索引和普通索引

InnoDB中每张表都有主键索引，且是根据主键顺序存放数据的，如果建表时未定义主键，则数据库会自己生成rowid当主键。主键索引又被称为 聚簇索引。主键索引的B+树中的页子节点存储的是整行数据。
普通索引又称二级索引或非主键索引，在B+树中的页子节点存储的是主键值。在这样一个SQL（select b from t where a = 10）执行时，数据库会在a的索引表中查询a='xx'对应到的主键值，再用这个主键到主键索引中查询需要的数据，这个过程叫做回表操作。

覆盖索引与索引下推

上面提到一个sqlselect b from t where a = 10在执行时会进行回表操作，回表操作多查询一次主键索引树，影响了效率。那有没有什么办法可以避免呢？答案是建立个联合索引INDEX index_a_b (a, b)，这样数据在查询时就直接拿到了需要的b字段的值，不需要再进行回表操作。例如查询主键sql也是不需要回表操作select id from t where a = 10。这个就是覆盖索引的概念了。

索引下推是MySQL 5.6引入的功能，指的是可以在遍历的过程中就对包含的字段先做判断，直接过滤掉不符合条件的数据，减少回表操作。

例如select * from t where a > 10 and a <20 and b = 'xx'。
如果没有索引下推功能，这条语句的执行过程是这样的：
1、判断a是否大于10且小于20
2、如果步骤1不满足条件，则进行下一条记录。如果步骤1满足条件，则从a的索引树中取得对应的主键进行回表操作。
3、回表操作取得整行数据，取b的值判断是否等于'xx'，如果是，取出数据。重复步骤1和步骤2，直至a大于等于20终止。
上面的执行过程中如果满足步骤1的数据有100条，但同时满足t.b = 'xx'的数据只有10条，数据库却需要进行回表100次。

在引入了索引下推后的执行过程变成：
1、判断a是否大于10且小于20
2、如果步骤1不满足条件，则进行下一条记录。如果步骤1满足条件，则继续判断b是否等于'xx'。如果不满足，而进行下一条记录，如果满足，则从a的索引树中取得对应的主键进行回表操作，取出数据。
3、重复步骤1和步骤2，直至a大于等于20终止。
在引入索引下推后，整个过程就只需要回表10次，大大减少了回表操作。

最左前缀原则

最左前缀原则指的是只要sql满足最左前缀，就可以利用索引进行高效的查询。最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

例如在上面我们建立的联合索引INDEX index_a_b (a, b)，这时候其实相当于对a建立了单独索引，可以使用select id from t where a = 10快速得查询到主键值，这个a是联合索引的最左第一个字段。但此时select id from t where b = '张'这条sql是不会走索引的。如果建立的联合索引是这样的INDEX index_b_a (b, a)，那么后面一条sql会走索引，而a=10的查询那条反而不会走索引。
建立了INDEX index_b_a (b, a)的联合索引，这时进行select id from t where b lik '张%'查询时，也会利用了索引。但像b lik '%张%'和b lik '%张'是不会走索引的，这就是最左前缀中的字符串索引的最左M个字符。