5.1 InnoDB存储引擎索引概述
InnoDB存储引擎支持以下几种常见索引：
- B+树索引
- 全文索引
- 哈希索引
InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引
B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引的构造类似于二叉树，根据快速找到数据。
B+树索引并不能找到一个给定键值的具体行，只能知道查找数据是在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
数据库中的B+树可以分为聚集索引（clustered index）和辅助索引（secondary index），但是不管是聚集索引还是辅助索引，其内部都是B+树的，即高度是平衡的，叶子节点存放着所有的数据。聚集索引和辅助索引不同的是，叶子节点存放的是是否是一整行的信息。
5.4.1 聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同时B+树数据结构一样，每个数据页都是通过一个双向链表来进行链接的。
由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。
聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点：一是前面说过的页通过双向链表链接，页按照主键的顺序排序；另一点是每页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。聚集索引的另一个好处是，它对于主键的排序查找和范围查找非常快。叶子节点的数据就是用户所要查询的数据。
5.4.2 辅助索引
对于辅助索引（也称非聚集索引），叶子节点并不包含行记录的全部数据。叶子节点除了包含键值之外，每个叶子节点的索引行还包含一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。
辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过页级别的指针获取指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录
5.4.4 B+树索引的管理
1. 索引的管理
索引的创建和删除可以通过两种方法：
- alter table
- create/drop index
通过alter table创建索引的语法为
alter table table_name | add {index|key} [index_name] [index_type](index_col_name,...) [index_option]
alter table table_name drop primary key | drop {index|key} index_name
通过create/drop index创建索引的语法为：
create [unique] index index_name [index_type] on tab_name (index_col_name,...)
drop index index_name on table_name
用户可以设置对整个列的数据进行索引，也可以只索引一个列的开头部分数据。
使用 show index from table_name可以查看数据库索引的相关信息，其中 Cardinality是非常关键的值，表示索引中唯一值的数目的估算值。Cardinality除以表的行数应该尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此索引 。优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，即并非每次索引的更新都会更新该值。如果想要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令
2. Fast Index Creation
MySQL5.5版本之前（不包括5.5）存在一个普遍被人诟病的问题是MySQL数据库对于索引的添加或者删除的这类DDL操作，MySQL数据库的操作过程为：
1.首先创建一张新的临时表，表结构为通过命令alter table 新定义的结构
- 然后把原表中数据导入到临时表
- 接着删除临时表
- 最后把临时表重命名为原来的表名
可以发现，若用户对于一张大表进行索引的添加和删除操作，那么这会需要很长的时间。更关键的是，若有大量食物需要访问正在被修改的表，这意味着数据库服务不可用。
从InnoDB 1.0.x版本开始，InnoDB开始支持一种称为Fast Index Creation（快速索引创建）的索引创建方式----简称FIC
对于辅助索引的创建，InnoDB存储引擎会对创建索引的表加上一个S锁，在创建过程中，不需要重建表，因此速度较之前提高很多，并且数据库的可用性也得到了提高。删除辅助索引操作就简单了，InnoDB存储引擎只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图上对该表的索引定义即可。
需要特别注意，临时表的创建路径是通过参数tmpdir进行设置的。用户必须保证tmpdir有足够的空间可以存放临时表，否则会导致创建索引失败。由于FIC在索引创建过程中对表加上了S锁，因此在创建过程中只能对该表进行读操作，若有大量的事务需要读目标表进行写操作，那么数据库的服务同样不可用。此外，FIC方式只限定于辅助索引，对于主键索引的创建和删除同样需要重建一张表
3. Online Schema Change
Online Schema Change（在线架构改变，简称OSC），所谓"在线"是指在事务的创建过程中，可以有读写事务对表进行操作，这提高了原有MySQL数据库在DDL操作时的并发性。由于OSC只有一个PHP脚本，因此其有一定的局限性，例如其要求修改的表一定要有主键，且表本身不能存在外键和触发器。此外，在进行OSC过程中，允许SET sql_bin_log=0，因此所做的操作不会同步slave服务器，可能导致主从不一致的情况。
4. Online DDL
MySQL5.6版本开始支持Online DDL操作，其允许辅助索引创建的同时，还允许其他诸如INSERT，UPDATE，DELETE这类的DDL操作，这大大提高了MySQL数据库在生产环境中的可用性。
Cardinality值
对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分时使用B+树索引才有意义，对于性别字段，地区字段，类型字段，他们可取值的范围很小，称为底选择性，这是添加B+树索引是完全没有必要的。相反，如果某个字段取值范围很广，几乎没有重复，即属于高选择性，则此时使用B+树索引是最适合的。
Cardinality表示索引中不重复记录数量的预估值。
因为MySQL数据库中有各种不同的存储引擎，而每种存储引擎对于B+树索引的实现又各不相同，所以对Cardinality的统计是放在存储引擎层进行的。
InnoDB存储引擎内部对于Cardinality信息的更新策略为：
- 表中1/16的数据已发生变化
- stat_modified_counter>2000000000
第一种策略为自从上次统计Cardinality信息后，表中1/16的数据已经发生了变化，这是需要更新Cardinality的信息。第二种情况是，如果对表中某一行数据频繁地进行更新操作，这时表中的数据实际并没有增加，实际发生变化的还是这一行数据，则第一种更新策略就无法适用这种情况。故在InnoDB存储引擎内部有一个计数器stat_modified_counter，用来表示发生变化的次数，当stat_modified_counter大于2000000000时，同样需要更新Cardinality信息
InnoDB采用采样的方法来进行Cardinality信息的统计和更新操作。默认InnoDB存储引擎对8个叶子节点进行采用。采样的过程如下：
1.取得B+树索引中叶子节点的数量，记为A。
2.随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，...，P8。
3.根据采样信息给出Cardinality的预估值：Cardinality=（P1+P2+...+P3）* A/8
因为每次都是随机获取8个叶子节点得到的，这说明每次得到的Cardinality结果可能是不同的。当然还有一种情况每次获取到的值都是一样的，那就是表足够小，表的叶子节点小于或者等于8个。这是即使随机采样，也总是会采取到这些页，因此每次得到的Cardinality值是相同的。
当执行SQL语句ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX 以及访问INFORMATION_SCHEMA架构下的表TABLES和STATISTICS时会导致InnoDB存储引擎去重新计算索引Cardinality值，若表总数据量非常大，并且表中存在多个辅助索引时，执行上述这些操作可能会非常慢。虽然用户可能并不希望去更新Cardinality值
