一、索引的常见模型
1. 哈希表
是键值对（key-value）存储结构，只要根据 key 就可以找到 value。
可以理解为一个数组，对 key 进行哈希计算，换算成一个确定的位置，把 value 放入此位置。
因为存储hash冲突的情况，多个value可能在同一个位置上，使用链表，后来的就追加到链表中。
例如存储身份证号和名字的信息：
这种结构只适用于等值查询场景，如果要找某个区间的用户就需要全部扫描一遍了。
2. 有序数组
按照身份证号递增的顺序保存。
有序数组非常适合等值查询和范围查询。
例如查找 [ID_X, ID_Y] 内的，先用二分法找到 ID_X，然后向右遍历，直到找到大于 ID_Y 的就结束了。
有序数组的优势是查询效率高，缺点是更新麻烦，插入一个记录就需要挪动后面所有的记录，效率低。
有序数组索引只适用于静态存储引擎，不会修改的数据情况。
3. 搜索树
先看最经典的二叉树：
二叉树中，左儿子 < 父节点，父节点 < 右儿子。
例如查找 ID_2，路径就是：
UserA -> UserC -> UserF -> User2
二叉树搜索效率最高，但实际数据库却不适用二叉树，因为索引是需要写到磁盘上的，例如一棵100万节点的二叉树，高度是20，一次查询需要访问20个数据块，从磁盘随机读一个数据块需要10ms左右的寻址时间，那么这个查询就需要200ms，很慢了。
所以需要使用N叉树，每个节点可以有多个儿子，儿子间从左到右递增，这样可以让查询过程访问尽量少的数据块儿。
二、InnoDB 索引
1. 为什么使用 B+ tree 索引模型？
例如插入数据：1,a,b,c,d,e。
二叉树的结构：
红黑树的结构：
B+ tree 的结构：
二叉树上面说过，效率太低，高度完全不可控，红黑树优化了不少，但高度仍然不可控，B+ tree 的高度恒定，而且只在叶子节点中存储数据，叶子节点间也是顺序链接的，做范围查找时非常高效。
2. 为什么建议使用自增主键？
涉及到1个概念：页分裂。
插入时，如果新值比现有值都大，那么只需要在后面插入即可，否则需要挪动现有数据。
如果插入目标位置的数据页满了，就要申请新的数据页，并挪动数据。
所以自增ID能够连续申请页空间，提升空间的操作效率和利用率。
三、MySQL 索引的3个重要概念
例如有一个表：
有2个索引，ID 和 k。
InnoDB 主键索引的叶子节点存储的是行数据，非主键索引的叶子节点存储的是主键。
查询 k 在 [3,5] 区间内的所有行数据：
select * from T where k betweet 3 and 5 在 k 索引树上找到符合条件的，得到 ID 值，回到 ID 索引树取得行数据。
回到主键索引搜索的过程称为回表。
1. 覆盖索引
上面的查询如果改为：
select ID from T where k betweet 3 and 5 只查询ID这个字段，那么只搜索 k 树索引即可，不需要回表了。
索引 k 已经覆盖了我们的查询需求，这种情况称为覆盖索引。
覆盖索引可以显著提升查询性能，所以做优化时可以考虑是否适合使用此方式。
例如用户表，有身份证号、姓名字段，身份证号是唯一的，建了一个索引。
如果业务中有根据身份证号搜索姓名的高频需求，就可以创建一个（身份证号+姓名）的联合索引，实现覆盖索引，即使增加了索引的维护成本也是值得的。
2. 最左前缀原则
索引项是按照字段顺序排序的。
查询“张三”时，会快速定位到 ID_4，然后向后遍历需要的结果。
查询“张%”也可以用这个索引，定位到 ID_3，向后找，直到不满足条件为止。
所以，只要满足最左前缀就可以用到索引。
涉及到一个问题：如何安排索引内的字段顺序？
需要考虑索引的复用能力，如果通过调整顺序，可以少维护一个索引，那么这个顺序就是优先考虑的。
3. 索引下推
例如用户表有字段：ID,name,age,ismale …，建有一个索引（name,age）。
现在查询：
select * from tuser where name like '张 %' and age=10 and ismale=1; MySQL5.6 之前，查询过程是：
根据索引找到以“张”开头的名字的ID，然后回表，进一步判断 age 和 ismale。
在 5.6 引入了索引下推，在索引中找到“张”开头的以后，先在索引中判断其 age 是否符合条件，因为 age 已经在索引中，不需要回表判断了，把 age 不符合要求的先过滤掉，然后再回表判断 ismale，这就减少了回表次数，提升了查询效率。