概述

InnoDB存储引擎支持以下几种常见的索引 :

• B+树索引
• 全文索引
• 哈希索引

InnoDB存储引擎支持的哈希索引是自适应的，InnoDB会跟根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。

B+树索引就是传统意义上的索引。类似于二叉树。
B+树索引中的B不是代表的二叉(binary)，而是代表的平衡(balance)，因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树。

数据算法与结构

介绍B+树之前先介绍下相关的数据结构

二分查找

将记录有序化排列，在查找过程中采用跳跃式的方式查找，先以有序数列的重点位置为比较对象，如果要找的元素值小于该重点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次查找将查找区间缩小一半

二叉查找树和平衡二叉树

二叉查找树 ：左子树的键值总是小于节点的键值，右子树的键值总是大于节点的键值
平衡二叉树 ：首先要符合二叉查找树的条件，然后必须满足任何子节点的两个子树的高度最大差为1
平衡二叉树在插入，更新和删除节点时，需要做旋转操作，会有额外的开销

B+树

B+树是为磁盘或其他存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的子节点上，由各子节点指针进行连接。

B+树的插入操作

为了保持B+树的平衡，对于新插入的键值可能需要做大量的拆分页(split)操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘操作，所以应该在尽可能的情况下尽量减少页的拆分操作。因此B+树同样提供了类似于平衡二叉树的旋转功能。

B+树的删除

B+树使用填充因子(fill factor)来控制树的删除变化，50%是填充因子的最小值。B+树的删除操作必须保证删除后叶子节点中的记录依然排序。

B+树索引

前面讨论的都是B+树的数据结构及其一般操作，B+树索引的本质就是B+树在数据库中的实现。在数据库中，B+树的高度一般都是在2~4层，这也就是说查找某一键值的行记录时最多只需要2到4次IO。一般的机械硬盘每秒至少可以做100次IO，2~4次的IO意味着查询时间只需要0.02~0.04秒。

数据库中的B+树可以分为聚集索引(clustered index)和辅助索引(secondary index)，但是不管是聚集索引还是辅助索引，其内部都是B+树的，即高度平衡的，叶子节点存放所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的数据。

聚集索引

聚集索引就是按照每张表的的主键构建一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中的数据也是索引的一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能特别快的访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

数据页上存放的是完整的每行的记录，而在非数据页的索引页中，存放的是键值和指向数据页的偏移量，而不是一个完整的行的记录。

如果聚集索引必须按照特定的顺序存放物理记录，则维护成本会相当高，所以聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点：一是页通过双向链表链接，页按照主键的顺序排序；另一点是每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

聚集索引的另一个好处是，他对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户索要查询的数据

辅助索引

辅助索引(Secondary Index，也称为非聚集索引)，叶子节点并不包含行记录的全部数据。叶子节点除了包含键值外，每个叶子节点中的索引行中还包含了一个书签(bookmark)。该书签用来告诉InnoDB存储引擎哪里可以找到索引相应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引并不影响数据在聚集索引中的组织，因此在每张表上可以有多个辅助索引。当通过辅助索引来寻找数据是，InnoDB存储引擎会遍历索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。举例来说，如果在一颗高度为3的辅助索引树中查找数据，那需要对这棵索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的数据页。

B+树索引的管理

添加删除索引

不赘述了，可以百度

可以通过show index from观察表上的索引，show index展现结果中每列的含义
Table : 索引所在的表名
Non_unique : 非唯一的索引，可以看到primary key是0，因此必须是唯一的
Key_name : 索引的名字，用户可以通过这个名字来执行drop index
Seq_in_index : 索引中该列的位置
Column_name : 索引列的名称
Collation : 列以什么方式存储在索引中，可以是A或NULL。B+树索引总是A，即排序的。如果使用了Heap存储引擎，并建立了Hash索引，这里就会显示NULL了。因为Hash是根据Hash桶存放索引数据，而不是对数据进行排序。
Cardinality : 非常关键的值，标识索引中唯一值的数目的估计值。Cardinality表的行数应尽可能接近1，如果非常小，如果非常小，那么可以考虑删除此索引
Sub_part : 是否是列的部分被索引。字段的类型为字符串时，只会以字符串的前面一部分字符作为索引
Packed : 关键词如何被压缩
Null : 是否索引的列含有NULL值。
Index_type : 索引的类型，InnoDB存储引擎只支持B+树索引，所以这里显示的都是BTREE。
Comment : 注释

Cardinality值非常关键，优化器会根据这个值来判断是否使用该索引。但是这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了。因此这个值是不太准确的，只是一个大概的值。如果需要更新Cardinality的值，可以使用ANALYZE TABLE

Fast Index Creation

MySQL5.5版本之前存在的一个普遍被人诟病的问题是MySQL数据库对于索引的添加或删除的这类DDL操作，MySQL的操作过程为

1. 创建一张临时表，表结果通过alter table新定义结果
2. 把原表中数据导入到临时表中
3. 删除原表
4. 把临时表重命名为原来的表名

如果是一张很大的表，会需要很长的时间，并且在这段时间内，是不能对这张表进行操作的。

InnoDB从1.0.x版本开始支持一种称为Fast Index Creation(快速索引创建)的索引创建方式--检查FIC。

Cardinality值

什么是Cardinality

并不是所有的查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引，一般经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段，地区字段，类型字段，他们可取值的范围很小，称为低选择性，这种时候添加索引其实是没有必要的。高选择性的字段，比如说用户邮箱，比如用户有邮箱。

InnoDB的Cardinality统计

InnoDB内部更新Cardinality的策略为

• 表中1/16的数据已发生变化
• stat_modified_counter > 2000000000

B+树索引的使用

联合索引

从本质上说，联合索引也是一颗B+树，不同的是联合索引的键值数量不是1，而是大于等于2。
和单个键值的B+树一样，键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据。比如一个索引idx(a,b)即(1,1),(1,2),(2,1),(2,4),(3,1),(3,2)。数据按(a,b)的顺序进行了存放

因此对于查询select * from t where a = 1 and b = 2，显示是可以使用这个联合索引的。对于单个的a列的查询select * from t where a = 1，也可以使用这个索引。但是对于单个b列的查询select * from t where b = 2则是不能使用这个索引的。可以看到b的顺序为1,2,1,4,1,2，显然是不排序的，因此对于b列的查询使用不到(a,b)的索引。

联合索引的第二个好处是已经对第二个键值进行了排序处理，这样可以避免一次排序操作。

联合索引(a,b)其实是根据列a,b进行排序，因此下列语句可以直接使用联合索引得到结果

然而对于联合索引(a,b,c)来说，下列语句同样可以直接通过连接索引拿到结果
select ... from t where a = 1 order by b
select ... from t where a = 1 and b = 2 order by c
但是对于下面的语句，联合索引不能直接得到结果，其还需要执行一次filesort操作，因为(a,c)并未排序
select ... from t where a = 1 order by c

覆盖索引

InnoDB支持覆盖索引(covering index，或称覆盖索引)，则从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小远小于聚集索引，因此可以减少大量的IO操作。InnoDB版本小于1.0或MySQL版本为5.0或以下的，不支持此特性。

对于辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为(primary key1,primary key2,...,key1,key2,key3...)。例如，下面的语句都可仅适用一次辅助联合索引完成查询
select key2 from t where key1 = xxx
select primary key2, key2 from t where key1 = xxx
select primary key1, key2 from t where key1 = xxx
select primary key1, primary key2, key2 from t where key1 = xxx

覆盖索引还有一个好处是对某些统计问题而言的。当InnoDB选择适用辅助索引来进行统计时，由于辅助索引远小于聚集索引，选择辅助索引可以减少IO操作。如下面的SQL
select COUNT(*) from t
通常情况下InnoDB引擎不会查询聚集索引来进行统计。但是当表上有辅助索引时，辅助索引远小于聚集索引，选择辅助索引可以减少IO操作，故优化器会选择辅助索引进行统计。

表bug_log有(user_id, buy_date)的联合索引，这里只根据列b进行条件查询，一般情况下是不可以选择b中所谓的查询条件。但是如果是统计操作，并且是覆盖索引，则优化器会进行选择。
select count(*) from buy_log where buy_date >= '2011-01-01'
表buy_log有联合索引，这里只根据列b进行条件查询，一般情况下是不能使用该联合索引的，但是这句SQL查询是统计操作，并且可以利用到覆盖索引的信息，因此优化器会选择改联合索引。

优化器选择不使用索引的情况

当用户要查询的数据是整行信息，而辅助索引不能覆盖到我们要查询的信息，因此在对辅助索引查询到指定的数据后，还需要进行一次书签访问来查找到整行的信息。虽然辅助索引数据是顺序存放的，但是再一次进行书签查找的数据则是无序的，因此变成了磁盘上的离散读操作。如果要求访问的数据量很小，则优化器还是会选择辅助索引，但是当访问量的数据占整个表的蛮大一部分时(一般是20%左右)，优化器会选择通过聚集索引来查找数据。因为之前提到过，顺序读要远远快于离散读。

因此对于不能进行索引覆盖的情况，优化器选择辅助索引的情况是，通过辅助索引查找的数据是少量的。这是由于当前传统机械硬盘的特性决定的，即利用顺序读来替代离散读。若使用的磁盘是固态硬盘，随机操作足够快，同时有足够的自信确认使用辅助索引可以带来更好的性能，那么使用关键词force index来强制使用某个索引

哈希表和全文索引就不记录了。。。