索引好比书的目录，我们看书的时候，先在目录找到自己感兴趣的主题，映射到对应的页码，然后就可以直接翻到那一页而不需要全书扫描。和目录一样，索引优点是减少找到目标数据需要扫描的行数，进而减少锁定，这样可以降低读操作的响应时间并尽量少的阻塞其他并发事务；反之，不用索引则意味着全表扫描。索引对于中大型的数据表最有效：对于非常小的表，简单的全表扫描更有效，不需要索引；对于特大表，索引成本更高，通常采用分区技术。另外，表的数量特别多时，推荐建立元数据信息表，用于记录哪些数据存储在哪张表。

索引在存储引擎层实现，存储在内存中。数据表中的唯一限制、主键限制、外键限制都通过索引实现。

三星系统用于评价索引设计是否合理：索引将相关记录放在一起则获得一星；索引数据顺序与查找中的排列顺序一致则获得二星；索引列包含查询所有列则为三星。

一、索引的分类

1.1 InnoDB的B+Tree索引

B+Tree是主流的索引数据结构：节点关键字存储索引值，节点指针指向数据行的磁盘地址；对于多列索引，节点关键字顺序包含各个列的值。

1.1.1 用索引优化查询

以people数据表为例，索引为(姓，名，生日)。查询符合下列条件时，可以完全借助索引查询，在B+Tree结构中定位到数据指针，进而拿到磁盘中的数据。

1）全键值查询：查询条件和索引列完全匹配，如查询A用于查找姓名为mary smith，今天生日的人，则可用索引进行查询从而避免全表扫描。

2）键值范围查询：支持左列的范围查询，如姓在allen到smith之间的人；可以扩展为左列精确匹配，第二列范围匹配。由此可见，多列索引的列顺序关系到具体查询的效率。

3）最左前缀：如查找所有姓smith的人，该查询可使用索引；可以扩展为查找所有姓名为Mary Smith的人；但查找所有生日在今天的人，或查找所有名为emily的人则无法使用索引。

4）列前缀：只能是左列的前缀，如所有S开头姓氏的人，也就是说like不能%通配符开头；可以扩展为查找所有姓Smith，名以M开头的人。

5）支持的匹配运算符包括：in、==、 >、<，但不支持<>；

当无法完全根据索引筛选结果时，innoDB首先根据索引检索到数据并返回给服务层，同时用读锁锁定这些数据，服务层根据其他条件筛选数据，innoDB针对被过滤的数据解除读锁；这种需要服务层进行筛选的查询，执行计划的extra显示为using where。例如select id from user where id<5 and id <>1; innoDB锁定id为1-4的数据并返回给服务器层，服务器层继而过滤掉id=1；执行计划的extra显示using where。

1.1.2 用索引优化排序

排序操作成本高，需要足够的内存，尤其对于varchar需要分配标称最大长度的内存。写查询语句时需要避免对大量数据进行排序操作。B+Tree节点形成链表结构并顺序排列，因此满足索引排序的前提下，B+Tree索引可以天然形成有序结果，大大提高排序效率，此时执行计划的type显示为index。无法使用索引排序时，又称为文件排序，数据量小于‘排序缓冲区’则在内存中快速排序，否则对数据分块，每块进行快速内存排序，并将各个块的排序结果放在磁盘并进行合并。

只有order by子句的列与索引列顺序一致，并且所有列的排序方式(升序/降序)也一致时，才能用索引排序。分为全键值排序和左列排序。

1）全键值排序包含3种情况：

1. select id from person where lastName='Smith' order by lastName, firstName, dob; 此时首先基于索引查询，查到的结果天然有序，不需要额外排序；

2. select id from person where nickName='hehe' order by lastName, firstName, dob; 此时无法基于索引查询，会使用全表扫描的方式，查询出来的结果在定位到索引B+Tree从而完成排序么？这个我还不清楚；

3. select id from person where lastName=‘Smith’ and nickName='hehe' order by lastName, firstName, dob;此时首先基于索引查到所有lastName为Smith的数据交给服务层，数据天然有序，服务层再进一步筛选出nickname为hehe的数据。

2）最左列排序，当最左列为常量，如查询条件限定了最左列的值，此时可扩展为按照次左列排序。

业务上通常组合使用order by和limit实现翻页，尤其翻到后面时性能很差，这是因为随着偏移量limit增加，mysql需要扫描大量需要丢弃的数据；通常通过限制用户翻页数量解决该问题，比如用户很少会在意第10000页的内容。或者尽量采用索引覆盖扫描，然后再做一次查询返回其他所需的列，称为延迟关联。例如select from people inner join（select id from people where xxx）as x；通过覆盖索引查询返回需要的主键，再根据主键关联原表获得需要的数据。

1.1.3 B+Tree索引的限制

B+Tree索引的限制即不能使用索引的场景：

1）多列索引中，不支持右列索引，如根据名/生日查询；不支持左列后缀查询，如姓氏以L结尾

2）不支持松散索引，如跳过中间索引查询，如不支持根据姓氏/生日查询，此时只能按照姓氏索引查询。

3）当某个索引列采用范围查询，则后续列不能使用索引优化查询，如姓氏精准/名范围查询/精准生日，此时只有姓名可以用索引查询，生日条件不行。

1.2 InnoDB的自适应哈希索引

当InnoDB注意到某些索引值频繁使用后，会额外创建哈希索引，存储频繁使用索引值的hashcode和行地址。当通过该索引值进行查询时，可以通过哈希值直接定位到行地址，而不需要在B+Tree中查找。

1.3 聚簇索引

聚簇表示在B+Tree索引结构中，数据行与索引列值存储在一起，数据行作为节点的叶子页。不能同时把数据行存放在不同地方，因此每个数据表只有一个聚簇索引。InnoDB默认主键索引作为聚簇索引。非聚簇索引称为二次索引，二次索引中保存主键值，根据二次索引查找时，首先根据索引值定位到主键，在根据主键在聚簇索引查找到数据内容。

推荐使用自增主键，数据顺序写入，当达到页的最大填充因子(默认值是页大小的15/16）时，下一条记录会被写到新的页，从而能够留出部分空间用于后续数据修改。相反，如果采用uuid作为主键，每次写入数据不能在上一条数据后面追加，而是根据值大小写到不同的页，造成频繁IO和频繁的页分裂。自增主键的问题是高并发情况下可能造成明显的争用。

聚簇索引的优点是提高IO密集型应用的性能，例如电子邮箱中，可以根据用户id聚集数据，这样当查找某用户的所有邮件时，只需要从磁盘读取少量数据页；避免每封邮件一次磁盘IO。

1.4 前缀索引

索引blob/text/varchar等长字符列，必须使用前缀索引，索引开始的部分字符，牺牲索引的选择性。如何确定前缀长度，使选择性接近完整列的选择性是一个需要思考的问题。通过add key city(7)创建前缀索引；前缀索引不支持order by/group by。

1.5 哈希索引

哈希索引是指对每行数据，存储引擎对所有索引列计算hashcode，和数据指针一起存放在哈希表，按hashcode顺序存储；查找时，再次计算索引列的hashcode，在哈希表查询对应记录，找到后二次确认找到的数据是否满足检索条件。Mysql中较少使用哈希索引。

通过哈希函数计算hashcode，有两类选择：1）SHA1/MD5的设计目标是最大限度消除冲突的强加密函数，生成的哈希值很长，影响存储/比较效率；2）简单哈希函数如crc32，生成的哈希值不那么长，缺点是容易出现哈希冲突。

哈希索引的限制在于：1）不支持索引排序，因为哈希表的排序按照hashcode而不是索引列本身的值；2）只支持等值查询，包括=，in，不支持范围查询，如>；3）多列索引只支持全列匹配；4）出现哈希碰撞时需要遍历链表中的行指针，找到目标数据。

1.6 覆盖索引

索引包含所有需要查询的字段，此时无需取出完整的数据行。B+Tree索引支持覆盖索引，哈希索引和前缀索引不存储索引列的完整值，因此不适用。使用覆盖索引时执行计划的extra为using index。

1.7 全文索引

对应SQL的match against关键字。使用场景如自然语言的全文索引，计算各个文档对象和查询的相关度，相关度基于匹配的关键词个数及出现频次。

二、索引设计的注意事项

2.1 多列索引的设计

1）多列索引优于多个单列索引：不建议为每个列单独创建索引，例如对姓/名/生日分别建立索引，当根据姓/名查询时，mysql同时使用这两个单列索引进行扫描，并将结果合并，合并算法包括与/或，称为索引合并，索引合并也是索引设计的坏味道：当通过执行计划看到对多个索引做and运算时，说明需要一个多列索引；or运算尤其会大量消耗CPU和内存。

2）合理的索引列顺序：通常将选择性更强的列放在前面，将用于范围查询的列放在后面；写查询语句时尽量避免多个范围查询

2.2 索引的选择性

索引的选择越强则索引查询效率越高。索引的选择性指不重复的索引值和数据表总量的比值，主键索引的选择性最强；如果查询条件中的索引值(如null)搜索出1万多条数据，就是典型的选择性差，此时索引查询对于读操作的效率提升帮助较小；再比如，未登录用户的用户名均为guest，涉及guest用户的查询与正常用户查询性能相距甚远。

2.3 其他注意事项

1）删除未使用索引；通过information_schema.index_statistics查看索引使用频率并删除未使用的索引，统计数据来源于InnoDB记录索引访问并保存索引统计信息。

2）避免重复索引和冗余索引：重复索引是在相同的列上按照相同顺序创建的相同类型索引，如索引(A)和索引(A)。索引(A,B)和索引(A)是冗余索引，因为后者是前者的左键索引。

3）减少索引碎片：B+Tree的叶子节点的物理分布不是连续的，InnoDB提供添加/删除索引功能，可以通过先删除，再创建的方式消除索引的碎片化。

4）查询条件使用独立的列：如果索引列是表达式的一部分，如where actorid+1=123，则无法使用索引；

三、B+Tree基础知识

1）平衡二叉树：每个非叶子节点有两个子节点，左侧子节点的值>节点值>右侧子节点的值，左右深度差不超过1，不存在值相等的节点。适用二分查找以提高检索效率，失衡会造成检索效率降低。

2）B-Tree是一种平衡多叉树，注意不是B减树。节点包含关键字和关键字记录的指针，从左到右按关键字值递增次序排列。相对平衡二叉树，每个节点包含的关键字变多(称为阶数)，树的深度变小；数据库应用中充分利用磁盘块原理：磁盘存储采用块的形式，每块4k，IO读取时，同块数据一次性读取出来。

B-Tree的操作如下：1. 检索过程：查找条件是关键字，对比根节点关键字，相等则查找结束，返回指针；否则去对应子节点查找，直到叶子节点，如果仍然未找到，则返回null。2. 创建：当节点关键字数达到最大值，再新增关键字时，进行节点拆分，把中间关键字提取到父节点。3. 删除关键字：当删除后节点关键字数小于最小值，则先从子节点取，没有则向父节点取，因此造成的父节点关键字不足由其他子节点补上。

3）B+Tree：1）非叶子节点不保存关键字记录的指针，支持更多关键字，层级更少；叶子节点保存父节点所有关键字指针，因此查询速度稳定；2）左边结尾数据保存右边开始数据的指针，因此叶子节点构成一个有序链表，遍历整个树只需遍历所有叶子节点，有利于数据库全表扫描。