MySQL索引

索引常见模型

哈希表、有序数组、搜索树

哈希表

哈希表是一种键-值 （key - value）存储的数据结构

优点：无序、新增很快
缺点：因为不是有序的，区间查询速度很慢
适用范围： 只适用于只有等值查询的场景

有序数组

有序数组在等值查询和范围查询场景中性能都很优秀。但是在更新数据时候就很麻烦了，因为是排序的，往中间插入一个记录，就要挪动后边所有的记录。
适用范围：适用于存储静态存储引擎。比如历史旧数据，不会再有新增的数据，或者不会往中间插入的数据。

二叉搜索树

二叉树特点：每个节点左儿子小于父节点，父节点又小于右儿子。二叉树搜索效率并不高，需要使用到N叉树。

InnoDB的索引模型

在InnoDB中索引都是根据主键顺序以索引的形式存放的，这种存储方式称为索引组织表。 InnoDB都是使用了B+树索引模型，所以索引都是存储在B+树中的。

每一个索引在InnoDB中对应一颗B+树。
主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

覆盖索引

基于主键索引和二级索引查询的区别：
基于二级索引查询，先搜索二级索引树，得到id值，再通过主键索引搜索一次，返回结果。这个结果成为回表。

所以基于非主键索引的查询需要多扫描一颗索引树。因此应尽量使用主键索引。

回表会造成多搜索一次索引树。比如我们想查询一个表的 id 和 key ，对于 id=1，key=5 的记录，根据 key=5 查询到 id = 1 , 然后会再根据 id=1 的主键索引再查一次，查询得到 key=5 , 返回结果。
这个例子中由于key在主键索引中有所以不得不回表，但是如果是 select id from table where key=5 ，这样的情况就不需要因为 id 的值已经包含在 k 索引树上了。不需要回表就能得到结果，这种称之为覆盖索引。

覆盖索引可以减少树的搜索次数，显著的提升性能，所以使用覆盖索引是一个常用性能优化手段。

最左前缀原则

B+树索引结构可以利用最左前缀原则，来定位记录。
联合索引的创建规则，因为联合索引的最左前缀原则，如果通过调整顺序可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

例如有个 (a,b) 的联合索引，那么一般就不需要在 a 上单独创建索引了。如果既有 (a,b) 的联合索引，又有基于a,b 的各自索引的查询， 查询条件里只有 b , 那么就需要同时维护(a,b) , (b) 这两个索引。

索引下推

如果一个查询需要利用的最左前缀原则，同时又要条件筛选，比如 select a,b from table where a like 'xx%' and b='xx'
在MySQL 5.6 之前 ，只能一个个开始回表。先找到数据，然后再对比字段值条件。
MySQL5.6之后的索引下推，可以在遍历索引的过程，对索引的字段进行判断，直接过滤掉不满足条件的记录，减少回表数。