索引是数据库系统里面最重要的概念之一，它的出现就是为了提高数据查询的效率。

索引的常见模型

       索引的出现是为了提高查询效率，实现索引的方式却有很多种，常见的有如下三种模型：哈希表、有序数组和搜索树。

哈希表

       哈希表是一种以键-值（key-value）存储数据的结构，只要输入待查找的值即key，就可以找到其对应的值即value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。不过，多个key值经过哈希函数的换算，可能会出现同一个值的情况，即哈希冲突，处理该种情况，就是拉出一个链表，即拉链法。在查询数据的时候，根据哈希函数定位到的位置若是链表，则顺序遍历链表，找到想要的数据。
       在哈希表中，key的值不是递增的，这样有个好处就是增加新的元素时速度会很快，只需要往后追加，但是缺点就是，因为不是有序的，所以哈希表在做区间查询的速度是很慢的。故哈希表这种结构适用于只有等值查询的场景。

有序数组

       有序数据，即大小有序的数组，其在等值查询和范围查询场景中的性能就都非常优秀。想要查找一条记录，使用二分查找法就可以快速得到，该算法的时间复杂度是O(log(N))。同时这种索引结构支持范围查找，可以先用二分查找法找到区间最小值，若区间最小值不存在，则找到大于区间最小值的第一个值，然后向右遍历，直到查到第一个大于区间最大值的值，退出循环。如果仅仅从查询效率来看，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，往数组中间插入一个记录就必须得挪动后面所有的记录，成本很高。故有序数组只适用于静态存储引擎。

搜索树

       二叉搜索树，是经典的数据结构，其特点是每个结点的左儿子小于父节点，父节点小于右儿子。其查询的时间复杂度是O(log(N))。树可以有二叉，也可以有多叉。多叉树就是每个结点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是索引不止在内存中，还要写到磁盘上。
       可以想象一下，一棵100万节点的平衡二叉树，树高20（log(1000000)）。一次查询可能需要访问20个数据块。也就是说，对于一个1000000行的表，如果使用二叉树来存储，单独访问一行，就需要访问20个数据块，效率相当的低下。为了让一个查询尽量少的读磁盘，就必须让查询过程访问尽量少的数据块。那么，就不应该使用二叉树，而是要使用“N叉”树，而N的大小取决于数据块的大小。
       以InnoDB的一个整数字段索引为例，假设N约等于1200。当这棵树高是4的时候，就可以存1200的3次方个值，已经17多亿。考虑到树根的数据块总是在内存中的，一个10亿行的表上的一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。从中可以看出，N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
       在MySQL中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。

InnoDB的索引模型

       在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB使用了B+树索引模型，所以数据都是存储在B+树中。每一个索引在InnoDB里面对应一棵B+树。
       在InnoDB中，索引分为主键索引和非主键索引。主键索引的叶子节点是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引被称为二级索引（secondary index）。而基于主键索引和普通索引的查询区别是基于非主键索引的查询需要多扫描一棵索引树。

索引维护

       B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。在插入新的数据页时，若数据页未满，直接插入；反之，需要申请一个新的数据页，然后挪动部分数据过去，该过程称为页分裂。这种情况下，性能会受到影响，除此之外，页分裂操作还影响数据页的利用率，原来放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。当然有分裂就有合并，当相邻两个页由于删除数据，利用率很低之后，会将数据页做合并。
       有这样的一个要求，要求建表语句里一定要有自增主键，原因是自增主键的插入数据模式，符合递增插入的场景。每次插入一条新纪录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而用业务逻辑的字段做主键，往往不容易保证有序插入，这样写入数据成本相对较高。
       除了考虑性能外，还要从存储空间的角度来看。假设表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增主键字段做主键呢？由于每个非主键索引的叶子节点上都是主键的值。主键越长需要的空间越大，故主键的长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。即从性能和存储空间方面考量，自增主键往往是更合理的选择。

索引覆盖

       在使用非主键索引查询时，难免要回到主键索引树来搜索，因为查询结果所需要的数据只有在主键索引上有，这个回到主键索引树搜索的过程，称为回表。
       如果使用非主键索引进行查询的结果包含在其索引树上，就不需要回表了。也就是说，该查询使用的索引涵盖了查询需求，称之为覆盖索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

最左前缀原则

       在使用联合索引进行查询的时候，并且该索引使用的底层数据模型是B+树，只要查询的条件是联合索引的最左N个字段，或者是字符串索引的最左M个字符，便可利用该索引来加速检索。
       基于“最左前缀索引”，在建立联合索引的时候，要考虑如何安排索引内的字段排序。评估标准是索引的复用能力，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

索引下推

       在MySQL 5.6之后，引入了索引下推的优化，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。