0x01 B+树
优点：B+树对比二分查找树和平衡二叉树的优点有高扇出性，并且没有频繁平衡带来性能上的问题，3~4层B+树索引即可存储很多数据。B+树对比B树的优点是非叶节点可以存更多记录。而且B+树的优势是可以顺序存储，在范围查找的时候很有优势。
缺点：B+树中元素填满节点的时候，需要节点的分裂，当节点中的元素少于负载因子*元素总数的时候，需要靠旋转或者合并节点。如果是在磁盘上操作，这些都是比较耗时的。
innodb能设置的索引格式只有B+树，但是会有自适应hash索引。一个B+索引分为内节点段、叶子段。
0x02 索引
聚集索引：也是主键索引，每张表只有一个，叶子节点是真正存数据的，而且叶子节点中的数据保证逻辑上的顺序。
辅助索引：一张表可以有多个辅助索引，叶子节点中聚集索引的主键，查询辅助索引的过程一般是先查询辅助索引的B+树，先查到主键，再根据主键去聚集索引中查询真正的数据。
在其他数据库中辅助索引的叶子节点中可能存储指向数据的指针，但是这样有个缺点，在OLTP应用中，DML语句可能会使数据频繁发生移动，导致更新所有的索引，这样带来的影响是很大的（类似java中成员变量对对象的引用）。
0x03 管理
如果想看sql语句是否使用了索引，可以使用执行计划，explain sql。
创建索引
alter table tbl_name add key index_name (col_name(bytes), ...);
create index index_name on table_name (col_name, ...);
删除索引
alter table tbl_name drop key index_name;
drop index index_name on tbl_name;
一般对整行数据进行索取，索引无法覆盖整行，虽然索引是顺序存储的，但是因为查找的数据是无序的，所以会对磁盘离散读，如果数据足够大(一般是20%)优化器认为顺序访问会比离散访问的效率高，所以就回选择使用聚集索引。如果没有使用辅助索引，可以使用force index强制使用索引，或者use index来建议使用索引。
mysql5.5之前创建索引的过程会新建一张表，然后将数据拷贝到新的表并且重新创建索引。
innodb 1.0.x提供了一个方式FIC(Fast Insert Creation)，给表加share锁创建索引，这样就省去了创建新表拷贝数据带来的性能上的损耗，删除索引的时候只需标注该块空间可用即可。
mysql5.6开始提供了新的方式OSC(Online Schema Creation)，创建和原始表一样定义的表，删除索引，然后开始拷贝数据，如果有对原表的DML操作写入delta表中，等数据拷完后在新表上重新播放delta表中的操作，最后重建索引。这个方式的好处是勿需暂停其他事务的执行，仍可以进行索引的创建。
Online DDL
alter table tbl_name add key index_name (col_name, ...)
algorithm = [default | inplace | copy]
lock = [default | none | shared | exclusive]
algorithm：copy是按照mysql5.1之前的算法來，inplace是指创建索引勿需创建新表，default是指根据old_alter_table参数来选择。
lock：none就是不加锁，读写事务不被阻塞，share和FIC一致可以并发读，但是阻塞写，exclusive是指对表加上X锁，读写都无法并行进行，default会根据none->share->exclusive的顺序来进行选择。
Online DDL的delta操作将这些操作放在缓存中，缓存的大小根据innodb_online_alter_log_max_size控制。如果超过缓冲的大小，创建索引的过程中会报error。
0x04 cardinality
索引的适用场景是访问少量数据，而且索引创建对列的选择是尽可能的具有高选择性。
高选择性的判断是cardinality/n_row_in_table这个值尽可能的接近1，也就是列中的数据最好不重复，样本无限大。
cardinality的统计
时机：表中1/16的数据发生过改变或者stat_modified_counter>2000000000。（在执行一些特殊操作的时候也会触发重新统计cardinality值，比如analyze table、show table status、show index等操作）
算法：随机取出8个数据页，然后根据下面的算法进行计算。
(页1中节点不同记录个数 + ... + 页8中节点不同记录个数)/8*行数。
所以cardinality在多次统计的情况下可能发生变化。
cardinality统计的调优参数：innodb_stats_persistent(是否存储统计结果，默认值off)、innodb_stats_on_metadata(是否在访问元数据的时候重新统计，默认值off)、innodb_stats_persistent_sample_pages(存储模式下的采样页数，默认值20)、innodb_stats_transient_sample_pages(默认模式下的采样页数，默认值8)。
案例
今天在解答群里问题的时候发现了个有趣的现象，上述的执行计划走了index_category_id_using索引，而没有走dele_question。按最左前缀原则，应该走dele_question索引，考虑了下，应该是优化器根据cardinality值进行了优化，delete_time=’‘的行有300W行，选择性很低，所以优化器选择了选择性高的category_id_using列来进行查找。
另外，执行计划各列的意义，possible_keys是可选择使用索引，key是选择使用的索引，extra的using where表示内容不能全从index里读取，using index表示查询内容全部可以从索引中获取。
0x05 innodb索引的使用
联合索引
联合索引就是对一张表上的多列建立索引。联合索引是根据索引的第一列进行排序的，在第一列相同的情况下，对第二列也是有序的。所以如果存在idx_a和idx_a_b，对where a=xxx，使用两个索引都OK。对于where a=xxx and b=xxx只能使用idx_a_b，对于where b=xxx则两个索引都无法使用。
覆盖索引
覆盖索引就是能从辅助索引中查询记录，不需要从聚集索引中查询。好处是辅助索引不需要包含整行信息，所以会比聚集索引小很多。
MRR优化
Mysql5.6开始支持MRR(Multi-Range Read)优化，就是将对磁盘的随机访问转换为顺序访问，这对OLAP类型应用性能提升很大。使用MRR后可以先查询辅助索引，然后将主键进行排序，顺序访问磁盘，减少缓冲池中页替换的次数。开启MMR可以设置参数optimizer_switch中的mrr为on，mrr_cost_based表示通过cost based启用mrr。read_rnd_buffer_size表示控制键值的缓冲区大小
ICP优化
Mysql5.6开始支持ICP(Index Condition Pushdown)优化，该优化支持range、ref、eq_ref、ref_or_null类型的查询，该优化可以先根据索引进行where条件的过滤，将条件过滤放在存储引擎层来做，减少上层sql层对记录的fetch，提高性能。
自适应hash
对buffer_pool中的页进行索引，通过hash计算每个页的散列值，来计算缓存中的页在磁盘上的位置。自适应hash无法自己控制，可根据innodb_adaptive_hash_index参数来禁用或者开启此特性。
全文检索
innodb从1.2.x开始支持全文检索，innodb将倒排索引的信息存入到6张auxiliary table中，并且在内存中维持了一个FTS Index Cache(用来减少维护倒排索引信息带来的性能上的损耗，类似Insert Buffer)，如果要开启全文检索，可以使用
create table `table_name` (
id int(10) unsigned not null auto_increment,
title char(254) default null COMMENT '标题',
PRIMARY KEY (`id`),
FULLTEXT KEY `ft_title` (`title`),
) engine=innodb default charset=utf-8;
alter table `zzx_articles` add fulltext ft_title(`title`);
auxiliary table的主键为FTS_DOC_ID 类型为BIGINT UNSIGNED NOT NULL，innodb会自动在该列上加FTS_DOC_ID_INDEX。在事务提交时将分词信息写入到FTS Index Cache中，然后在通过批量刷新写入到磁盘，如果宕机在下次全文检索的时候innodb会读取未完成的文档进行分词然后插入到FTS Index Cache中。
select * from table_name where match(col_name) against ('keyword' (in natural language mode | in natural language mode with query expansion | in boolean mode | with query expansion))\G
0x05 注意点
- 索引是左前缀匹配规则，索引中的列由左向右逐一匹配，如果中间某一列不能使用索引则后面的列不再被使用。
- 如果where子句中使用函数或类型转换或者like左侧使用通配符，则无法使用索引。
- 线上可以使用explain查看执行计划，查看是否走了索引，key_len是否够长，type的取值由好到差const > eq_reg > ref > range > index > all。
- set profiling=0 + show profile 可以查看执行效率。
- 覆盖索引在排行榜这类的业务场景下会比全表检索好。