之前找实习、参加秋招时准备面试都没有系统地复习过索引，都是零零碎碎地看一下博客和公众号，总结出了一套面试索引相关问题的组合拳，现在有时间静下心来看看书，那就系统地把索引的知识梳理一下吧。
1 索引的类型
1.1 B-Tree索引
一般说到索引数据结构，大部分同学的第一反应就是B+树，其实不然。MySQL中的专业术语是B-Tree，在create table和其他语句中会见到B-Tree这个关键字。
虽然很多存储引擎都使用B-Tree索引，但底层真正的数据结构又有所不同。例如：
NDB集群存储引擎内部实际使用了T-Tree数据结构
InnoDB存储引擎使用了B+树作为数据结构
不同的存储引擎以不同的方式使用了B-Tree索引，性能也有差别。例如：
MyISAM存储引擎使用了前缀压缩技术使得索引更小，而InnoDB存储引擎按照原数据格式进行存储
MyISAM存储引擎是通过数据的物理位置来引用被索引的行，而InnoDB存储引擎则通过主键来引用被索引的行
由于我们开发过程中使用InnoDB作为存储引擎的情况多，那么我们就具体地来学习下InnoDB的B-Tree索引的数据结构B+树吧。
先来看一棵B+树，它是1～10这10个数据的B-Tree索引：
当我们要查找6这个数据时，首先从树的根节点5出发，发现6比5大，往6的右子树继续查找；比较6和7，6比7小，往7的左子树查找；7的左子树正好是6，于是根据6这个中间节点的指针，就可以找到叶子节点6，6又可以根据叶子节点所指向数据行的指针来查询到真正的数据行。可以发现，使用索引去查询数据只是经过了4次的磁盘IO，比全表扫描需要6次磁盘IO减少了差不多一半，这就有效地提升了查询数据的效率。
结合上述查找的过程，我们来总结一下B+树的一些特点：
由于B+树的中间节点只存放键，不存放值，因此一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
B+树的叶子节点之间有指向下一个叶子节点的指针，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。这也便于范围查询。
B+树的所有查询都要查找到叶子节点，因此查询性能稳定。
B+树索引这么强大，我们当然要好好利用上，但是索引也会失效，那么如何去避免呢？
结合《高性能MySQL（第三版）》中的例子，有这么一个表：
（last_name，first_name，dob）是表的联合索引，那么B+树的存储结构是这样的：
B+树索引对多个值的排序是按照create table时指定的索引顺序来进行排序的，我们可以发现最后两个节点中，当名字均为Basinger Viven时，节点的顺序按照出生日期来进行排序。使索引有效的方式有：
- 全值匹配，和索引中的所有列进行匹配。例如：select ... from People where first_name = 'Allen' and last_name ='Cuba' and dob='1960-01-01'
- 匹配最左前缀，使用了索引的第一列。例如：select ... from People where first_name = 'Allen'
- 匹配列前缀，匹配某一列的值的开头部分。例如：select ... from People where first_name like 'A%'，这里也只是使用了索引的第一列
- 匹配范围值，例如：select ... from People where first_name between 'Allen' and 'Barrymore'，这里也只是使用了索引的第一列
- 精确匹配某一列并范围匹配另外一列，例如：select ... from People where first_name = 'Allen' and last_name like 'K%'，这里使用了索引first_name全匹配，last_name范围匹配
- 只访问索引的查询，例如：select first_name,last_name,dob from People
(注：SQL表达式中的 … 表示某几个索引列)
此外，由于此B+树索引中的节点是有序的，故可以使用order by排序。
对于B+树索引的限制也应该了解，否则会导致一些查询语句无法走索引，导致索引失效使得查询效率低：
- 必须按照索引的最左列开始查找，即最左前缀原则。
- 不得跳过索引中的列，上述的例子中，如果索引是先first_name然后再dob，中间跳过了last_name，这会导致该索引只使用到了first_name
- 查询中的某个列的范围查询，则其右边的所有列都无法使用索引进行查找。例如：select ... from People where first_name = 'Allen' and last_name like 'K%' and dob = '1976-12-23' ，这个查询只能使用first_name和last_name这两个索引，dob索引是失效的。
只有我们遵守了上述的规范，才可以发挥出索引的最大性能，不知不觉，这个高频面试题的答案就这样出来了。
1.2 哈希索引
所谓哈希索引，顾名思义就是基于哈希表实现的索引，只有精确匹配索引所有列的查询才是有效的。对于每一行数据，存储引擎会对所有的索引列计算一个哈希码，哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
哈希索引的特性：
- 哈希索引只有哈希值和行指针，不存储数据值，故不能使用索引中的值来避免读取行，但访问内存中的行速度很快
- 哈希索引不按照索引值顺序排序存储，故无法用于排序
- 哈希索引不正常部分索引匹配查找，只能精确查找
- 哈希索引不支持范围查询，只支持等值比较查询
- 哈希索引查询数据非常快，但会产生哈希冲突，有冲突时采用链表的方式解决冲突，故查询效率会变慢，因为要遍历链表。
- 哈希冲突多的话，哈希索引维护的代价也会变高
支持哈希索引的存储引擎有Memory和NDB集群引擎。此外，InnoDB有自适应哈希索引，当InnoDB发现某些索引值被查询得非常频繁时，它会在内存中基于B-Tree索引上再创建一个哈希索引，可以更快速地查询索引值。这是一个完全自动的行为，用户无法控制或配置。
1.3 空间数据索引R-Tree
MyISAM表支持空间索引，用于地理数据存储。它不必遵守最左前缀原则来查询。R-Tree会从所有纬度来索引数据。查询时，可以有效使用任意纬度来组合查询。
1.4 全文索引
全文索引负责查找文本中的关键词，而不是直接比较索引中的值。在相同的列上可以同时创建全文索引和B-Tree索引，全文索引适用于match against操作，而非普通的where条件查询操作。
2 索引的优点
面试时经常会被问到：如何提高查询的效率？
对于这个面试题，很多同学第一反应就是加索引。的确，索引可以让服务器快速地定位到表中的数据行。其实根据前面的分析，索引的优点可以总结如下：
- 索引减少了服务器需要扫描的数据量，避免了全表扫描
- 索引可以帮助服务器避免在磁盘中创建临时表和进行文件排序
- 索引可以将随机IO变为顺序IO
3 高性能索引策略
3.1 独立的列
如果查询的列不是独立的，MySQL就不会使用索引。例如有个索引列为user_id，以下两种SQL都不会使用user_id索引
select * from user where 表达式/函数(user_id)
select * from user where 表达式/函数(user_id)
只有查询的列和where条件列都是有索引列，才会使用user_id索引。例如：
select user_id from user where user_id = ?
3.2 前缀索引和索引选择性
有时需要索引很长的字符列，采用常规的索引会变得很大且很慢，应该怎么办呢？
针对这个问题，可以索引开始的部分字符，以节省索引空间，从而提高索引查询效率。但这样可能会造成索引选择性降低。
索引选择性：不重复的索引值和数据表总记录数的比值，比值大于0小于等于1。索引选择性越高则查询效率越高，因为选择性高的索引可以让MySQL在查询时过滤掉更多的行。唯一索引的索引选择性是1，因此查询效率最高。
一般情况下，某个列前缀的索引选择性是足够高的，足以满足查询性能。对于blob、text和长varchar的列，必须使用前缀索引，因为MySQL不允许索引这些列的完整长度。
3.3 多列索引
多列索引是开发者们比较常犯的错误，即为每个列创建独立的索引，或者按照错误的顺序创建多列索引。例如：select a,b,c from t where a=1 and b=2 and c=3语句，给t表的where条件里面的列a、b、c列都建立上索引，这种在多个列上建立独立的单列索引大部分情况下并不难提高MySQL的查询性能。
索引合并，MySQL 5.0及以上一定程度上可以使用表上的多个单列索引来定位指定的行。而老版本的MySQL中只能使用某一个单列索引，然而这种情况下没有哪一个独立的单列索引上非常有效的。例如，t表有a、b两个索引，老版MySQL中，对于select a,b from t where a=1 and b=2语句，MySQL会进行全表扫描。除非改成如下的两个查询的union方式：select a,b from t where a=1 union all select a,b from t where b=2;对于MySQL 5.0及以上，查询能够同时使用这两个单列索引进行扫描，并将结果进行合并。
虽然索引合并是MySQL的一种优化策略，以下情况使用多列索引还是很糟糕的：
- 当出现服务器对于多个索引做相交操作时（多个 and 条件），通常需要一个包含所有相关列的多列索引，而不是多个独立的单列索引
- 当出现服务器对于多个索引做联合操作时（多个 or 条件），通常需要耗费大量CPU、内存资源在算法的缓存、排序和合并上。特别是当其中有些索引的选择性不高，需要合并扫描返回的大量数据时
