文章目录
前言常见的索引类型聚簇索引/非聚簇索引覆盖索引前缀索引索引下推前言
索引的出现是为了提高数据查询效率，像书的目录一样。对于数据库的表而言，索引其实就是“目录”。
关于MySQL的系列文章，请跳转至 MySQL专栏
常见的索引类型
哈希表有序数组搜索树哈希表
哈希表是以 KV 形式存储数据的结构，只要输入key，就可以找到对应的 value，思路很简单，就是放到数组中，根据 hash 算法计算出key在数组中确定的索引位置，把 value 存储在这个索引位置。当两个不同的 key 经过 hash 算法计算出的 索引位置相同时，就出现了哈希碰撞，这时用一个链表解决。查询的时候，根据 hash 算法计算出 value 所在数组的索引位置，然后按链表顺序遍历，直到找到 key 对应的 value
哈希表中存储数据不是按照 key 的顺序递增排序的，如果需要做范围查询的话，使用哈希结构就不得不全部扫描一遍了。
所以，哈希结构适用于等值查询的场景，比如 NoSQL
有序数组
有序数组不管是等值查询还是范围查询场景中性能都很好。等值查询时，可以根据二分查找法定位元素，时间复杂度是 O(logn)；如果是范围查询时，可以先用二分法查找到范围的下限，再向右遍历，知道查到第一个不符合范围的值，退出循环。
如果只看查询效率，有序数组是最好的数据结构了。但是，如果要新增数据，往其中数组中插入一个元素，要挪动后面所有记录，成本太高。所以，有序数组只适用于静态存储引擎，比如不会再修改，只需要查询的数据。
搜索树
二叉搜索树的节点是有序的，左节点都小于根节点，右节点都大于根节点。二叉搜索树如果出现极端的情况，性能极差，所以，平衡二叉树的查询性能更好。但是平衡二叉树的结构，每次读数据块都需要从磁盘加载到内存，为了减少 I/O 操作，要尽可能的少读磁盘，平衡多叉树可以解决这个问题，每个节点有多个子节点，这样树的高度相较于二叉树来说，低的多，查询过程中就会访问较少的数据块，从而提高查找效率。
聚簇索引/非聚簇索引
众所周知，InnoDB采用的是B+Tree这种数据结构，B+Tree 也是一种平衡多叉树。InnoDB 表中的数据都是根据主键顺序以索引的形式存放的，每一个索引在 InnoDB 中对应一棵 B+Tree ，索引类型又分为：主键索引和非主键索引。
主键索引的叶子节点存的是整行数据，在 InnoDB 中，主键索引也被称为聚簇索引。
非主键索引的叶子节点存的是主键的值，在 InnoDB 中，非主键索引也被称为二级索引。
基于主键索引和普通索引的查询有什么区别？
如果 SQL 中的 where 条件是主键，则只需要搜索主键索引的B+Tree即可查询该数据；
如果 SQL 中的 where 条件是普通索引，则先搜索普通索引的 B+Tree，得到主键的值，再根据主键的值搜索主键索引的B+Tree查询到需要的数据，这个过程称为回表。
所以，基于非主键索引的查询需要多扫描一棵树，因此，在应用中应该尽量使用主键查询。
为什么说主键的长度要尽量小并且是自增的？
B+Tree 在插入新节点时，如果插入的节点值比当前树中的值都大时，则直接插入即可。而如果插入的节点值在当前树中的值处于中间位置，就需要挪动部分数据，空出位置再插入新数据。而如果要插入数据页满了，根据B+Tree 的算法，需要申请一个新的数据页，再挪动部分数据，这个过程叫做页分裂。有分裂的情况就有合并的情况，当从树中删除一个节点时，剩余的数据在数据页中的利用率很低的时候，会将数据页做合并操作，就是分裂的逆过程。
而之所以要求主键自增是因为，如果每次要插入的节点都比当前树中最大值还大，都是追加操作，则不会触发叶子节点的分裂。
要求主键的长度要尽量短，上面我们说过，每个非聚集索引的B+Tree中存的是元素对应的主键，如果主键越长，占用的内存空间越大；而主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。
覆盖索引
这条 SQL中select * from T where k between 3 and 5，id 为主键，k 为普通索引。这条SQL的执行流程是什么样的？
k是普通索引，遍历k索引树，找到范围的下限3，取得对应的主键，再到主键索引树中查询主键对应的数据行。再回到k索引树取下一个值，判断是不是在要查询数据的范围内，如果在，再取到对应的主键，再去主键索引树查询到对应的数据行。直到找到超出查找的数据范围时，查找结束
上述过程中不可避免的出现了回表操作，因为数据行只有主键索引上存在，只能去遍历主键索引树。
如果执行的 SQL 是：select id from T where k between 3 and 5
只需要查到遍历 k 索引树从叶子节点查到 id 的值，直到找到超出查找的数据范围时，查找结束，不需要回表操作
在这个查询中，索引 k 已经覆盖了查询需求，称为覆盖索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
前缀索引
有一种索引是联合索引，指的是由多个字段组成的索引，也称复合索引。
如果有一个联合索引（name,age），下面通过实例说明最左前缀原则。
根据上面的联合索引，现在有如下需求：
要求查出所有名字是“张三”的人要求查出所有姓“李”的人要求查出所有名字中最后一个字是 “山”的人要求查出所有年龄为 18 的人
1 的SQL条件写成：where name = "张三"，可以使用(name,age)联合索引查询，也就是从索引的最左侧开始，这个最左前缀可以是联合索引的最左N个字段。
2 的SQL条件：where name = "李%"，这时，也可以使用联合索引。
3 的SQL条件：where name = "%山"，这时，不可以使用联合索引，会导致索引失效
4 的SQL条件：where age = 18，这时，不可以使用联合索引，因为查询条件不是联合索引的最左N个字段。
综上所述，在建立联合索引时，要安排好索引的字段顺序。否则，很有可能导致索引失效。对于(name,age)联合索引，符合条件的查询条件是：
where name = …where name = … and age = …where name = … and age in (… , …)order by name,agewhere name = … order by age
还有很多情况会导致索引失效，看看都有哪些情况：
or 前后查询条件不都是索引子段（or 前后查询字段都是索引时会生效）未遵循最左N个字段模糊查询 like 以 % 开头需要类型转换where 中索引列有计算where 中索引列用到了函数索引字段上使用 not , <> , != （不等于操作符会触发全表扫描）当全表扫描速度比索引速度快时
索引下推
上面讲解了最左前缀原则，如果联合索引中不符合最左前缀原则的部分，会怎么样呢？
我们还是以联合索引（name, age）为例，要求检索出表中 “名字第一个字是张，而且年龄是10岁的所有男孩”。那么，SQL语句是这么写的：
select * from tuser where name like '张%' and age=10 and ismale=1;
这个语句在搜索索引树的时候可以使用联合索引，先覆盖了 name 索引，找到第一个name字段满足"张%"的记录后，开始回表查询数据行，再从联合索引树上找下一个字段值做对比。
在MySQL 5.6之前，只能从第一个满足name条件的值开始一个个回表。到主键索引上找出数据行，再对比字段值。
而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
如下图，分别是 MySQL 5.6 前 和 5.6 后的执行流程图。
第一个图中，也就是无索引下推的流程图中，这个过程InnoDB并不会去看age的值，只是按顺序把“name第一个字是’张’”的记录一条条取出来回表。因此，需要回表4次。
使用了索引下推的流程图中，InnoDB在(name,age)索引内部就判断了age是否等于10，对于不等于10的记录，直接判断并跳过。在我们的这个例子中，只需要对ID4、ID5这两条记录回表取数据判断，就只需要回表2次。
