索引就是数据库的表的目录，用来加速对表的数据的检索。
索引的常见模式
索引的实现有很多种，这里介绍常见几种常见、也比较简单的数据结构。分别是哈希表、有序数组和搜索树。
哈希表
哈希表就是用哈希函数根据一个key算出一个位置，然后将value存放在这个位置。使用哈希表不可避免会出现哈希冲突，而常用的解决方法就是拉链法。
使用哈希表可以快速根据key找到其对应的value，但是因为哈希表中存放的数据是无序的，所以做区间查找是非常慢的，需要扫描整个表。
哈希表这种索引适用于只有等值查询的场景，如Memchached及一些Nosql引擎。
有序数组
有序数据在等值和范围查找的场景中表现都很优秀。利用二分法既可以快速找到一个确定的值，也可以找到想要的范围。
但是有序数组只适合静态存储引擎，就是数据创建之后再也不会改变的场景。因为有序数组的更新耗费很大，比如往数组中间插入一条记录，那么后面的所有元素都需要进行移动。
搜索树
最经典的就是二叉搜索树，为了让保证时间复杂度为O(logn)，需要保证这是一个平衡树，但是二叉树在数据量多的时候树会非常高，每个节点都代表一个数据块，需要从磁盘中读取，这样耗时仍然不小。
解决的方法就是由二叉变为N叉。让查询尽量少读磁盘。以Innodb的一个整数索引为例，N差不多是1200，这个树高为4的时候，就可以存1200的3次方个值，就已经17亿了。 一个10亿行的表上的整数索引，查找一个值最多需要访问三次磁盘，并且实际上树的根节点通常就在内存中，第二层的节点也有很大的概率也在内存中，这样磁盘访问的速率就更快了。
因此N叉树广泛应用于数据库引擎中，其在读写上的性能都非常优秀。
InnoDB索引模型
InnoDB使用B+树作为索引的数据结构。每一个索引都对应一棵树。
虽然索引都是B+树，但是根据叶子节点存储的内容，还可以分为主键索引（也称聚簇索引）和非主键索引（二级索引）。
主键索引的叶子节点存放的就是就是数据库中的一行完整的记录，也就是说数据库中的数据就是按照主键索引组织的。所以也可以知道一个表中只能有一个主键索引，毕竟数据不可能同时按照两种方式组织。
如果查询的字段正好是主键，那么直接使用主键索引即可。如果查询的字段使用的不是主键索引，那么它需要现在索引中找到要查询的记录对应的主键，再根据主键到主键索引中查找，这个过程叫做回表，这也是我们为什么将非主键索引叫做二级索引的原因。
索引的维护
索引要发挥作用，就要保证索引的有序，所以在插入和删除的时候需要做必要的维护。
当插入数据的时候，如果插入的数据在节点的中间，那么就需要将节点后面的数据进行移动，并且因为每个节点对应一个数据页，所以如果插入的时候数据页是满的，那么就会发生页分裂，即影响了性能了，也降低了空间利用率。 当然删除数据的时候，会讲相邻的利用率低的页进行合并，就是页分裂的逆过程。
基于这个原因，可以思考下面的问题
为什么一些建表规范中要求必须要有自增主键？
答案就是避免页分裂
使用自增主键保证了，在向数据库中插入数据的时候，是直接在数据页后追加的，数据页写满之后，直接创建一个新的数据页，继续往里追加数据即可。不会移动数据，也不会造成页分裂。
并且由于非主键索引的每个叶子节点上都要保存对应的主键的值，所以主键的值空间越小越好，这样普通索引的空间也会很小。
至于使用业务字段作为索引的情况，那就是这个表只有一个唯一索引，使用业务字段作为索引可以避免查询的时候需要搜索两棵树。这种场景其实就是典型的KV场景。
覆盖索引
对于非主键字段的查询使用覆盖索引可以不用回表，就是说查询的字段在非主键索引的叶子节点上都有，这样通过非主键索引就能够获得结果的话就没有必要再去回表查询了。
使用覆盖索引也是一个常用的性能优化手段。
覆盖索引是否建立需要考虑实际请求中的字段的情况，例如一个人的身份信息就足够用来建立索引，但是如果经常需要根据身份证查询姓名，那么就有必要建立身份证、姓名的联合索引来进行覆盖，提交检索效率。
最左前缀原则
只要查询的字段与索引的前缀匹配，那么就能够使用这个索引，这就是最左前缀匹配原则。如果能够在查询的时候调整字段的顺序，利用这个原则，可以减少不必要的索引创建。 例如一个(name,age)的联合索引，查询name,age或者name都可以走这个索引。
索引下推
当查询不满足最左前缀的时候，例如有一个(name,age)的联合索引，而查询语句是
select * from user where name like '张%' and age = 10在mysql5.6之前没有索引下推，虽然可以利用索引找到name以张开始的记录，但是接下来就需要去主键索引中查找了。
而5.6之后的索引下推，可以先对索引中包含的字段进行判断，筛选掉不满足的记录，减少回表的次数。例如，可以先将age不等于10的记录过滤掉再去回表，而不是直接回表去查。