1. 聚集索引

聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的为整张表的行记录数据。也将聚集索引的叶子节点称为数据页。同B+树数据结构一样，每个数据页都通过一个双向链表进行链接。

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

聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点原因：一是数据页通过双向链表链接，数据页按照主键的顺序排序；另一点是每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

2. 辅助索引

辅助索引（secondary index，也称非聚集索引）的叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，还包含了一个bookmark，该bookmark用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表可以由多个辅助索引。当通过辅助索引寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的记录。

举例来说，如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引数查找3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页。因为一共需要6次逻辑IO访问以得到最终的一个数据页。

3. 联合索引

从本质上讲，联合索引也是一棵B+树，不同的是联合索引的键值不是1，而是大于等于2。

create table t (a int,b int,primary key (a),key idx_a_b (a,b))engine=innodb

联合索引（a,b）是根据a,b进行排序的，下列语句可以直接使用联合索引得到结果：

select * from t where a=xxx and b=yyy;

select * from t where a=xxx order by b;

对于联合索引（a,b,c），下列语句同样可以直接使用联合索引得到结果：

select * from t where a=xxx and b=yyy;

select * from t where a=xxx order by b;

select * from t where a=xxx and b=yyy order by c;

4. 覆盖索引

InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询记录，而不需要去查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

5. B+树索引管理

5.1 索引管理

索引创建：

alter table t add key idx_a_c(a,c);

create index idx_a_c on t(a,c);

删除索引：

drop index idx_a_c on t;

查看索引：

show index from t\G;

5.2 fast index creation

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

a. 首先创建一张新的临时表，表结构为通过命令alter table新定义的结构；

b. 把原表的数据导入临时表中；

c. 删除原表；

d. 把临时表重命名为原来的表。

临时表的创建路劲是通过参数tmpdir进行设置的，用户必须保证tmpdir有足够的空间可以存放临时表，否则会导致创建索引失败。

若用户要对一张大表进行索引的添加和删除操作，那么会需要很长的时间。更关键的是，若有大量事务需要访问正在被修改的表，这意味着数据库服务不可用。

InnoDB 1.0.x版本开始支持一种称为fast index creation的索引创建方式——简称FIC。

对于辅助索引的创建，InnoDB存储引擎会对创建索引的表加一个S锁。在创建的过程中，不需要重建表，因此速度较之前提高很多。由于加了S锁，创建过程中，可以对表进行读操作，不能进行写操作。删除索引的操作就更简单了。InnoDB存储引擎内部只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图上对该表的索引即可。

FIC方式只限定于辅助索引，对于主键的创建和删除同样需要重建一张表。

5.3 online DDL

MySQL 5.6版本开始支持online DDL操作。以下几类操作都可以通过在线方式进行操作：

a. 辅助索引的创建与删除

b. 改变自增长值

c. 添加或删除外键约束

d. 列的重命名

InnoDB存储引擎实现online DDL的原理是在执行创建或删除操作的同时，将insert、update、delete这类DML操作日志写入到一个缓存中，待完成索引的创建后再将重做应用到表上，以此达到数据的一致性。这个缓存大小由参数innodb_online_alter_log_max_size控制，默认大小为128M。若用户更新的表比较大，并且在创建的过程中有大量的写事务，如遇到innodb_online_alter_log_max_size的空间不能存放日志，就会报错。

需要注意，由于online DDL在创建索引完成后再通过重做日志达到数据库的最终一致性，这意味着在索引创建过程中，SQL优化器不会选择正在创建中的索引。

6. cardinality值

show index 结果中的cardinality值很关键，优化器会根据这个值来判断是否使用这个索引。

cardinality表示索引中唯一值得数目的估计值。

索引的高选择性：cardinality/表中的总行数 要尽可能的等于1。

cardinality是一个预估值，不是一个准确值。如果需要更新索引cardinality的信息，可以先使用analyze table命令。

MySQL数据库中有各种不同的存储引擎，而每种存储引擎对于B+树的实现又各不相同，所以对cardinality的统计信息是放在存储引擎层进行的。

数据库对于cardinality的统计都是通过采样的方式完成的。InnoDB存储引擎内部对跟新cardinality的策略为：

（1）表中有1/16的数据已经发生过变化

（2）stat_modified_counter>2 000 000 000.(stat_modified_counter,用来表示单行数据发生变化的次数)。

在InnoDB存储引擎中，cardinality的值是通过对8个叶子节点预估而得的，不是一个实际精确值。再者，每次对cardinality值的统计，都是通过随机取8个叶子节点得到，这意味着每次得到的cardinality值可能是不同的。