索引
对于索引的使用有个误区，并不是越多越好，也不是在有性能问题的时候才想起来要dba加个索引，应该是在最初表设计的时候就考虑到该表的使用场景，设计好索引。
索引的存在就是为了减少磁盘io次数，磁盘io是数据库检索过程中最耗时的部分。
innodb中常见的有三种索引，B+树、倒排索引、哈希索引，其中哈希索引是自适应的，不可人为干预。
B+树
B+树是为磁盘或者其他存储辅助设备设计的一种多路平衡查找树，B是balance的意思，目的是为了减少IO。
B树
B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
- 每个节点最多只有m个子节点
- 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点
- 如果根不是叶节点，则根至少有两个子节点
- 具有k个子节点的非叶节点包含k -1个键
- 所有叶子都出现在同一层
一个B树的结构如下：
B树高度
一棵含有n个总关键字数的m阶(B树中一个节点的子节点数目的最大值称为阶)的B树的最大高度是：
证明过程如下：
B+树
B+树由B树变形而来，是为了满足外存设备的需求。它必须满足以下条件：
- 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引
- 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
- 所有的非叶子结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
一个B+数的结构如下：
用B+树做索引的原因
- B+树索引效率高：B+树非叶子节点不存储实际数据，所以每个节点能存储更多的关键key信息，一次性读入内存的关键key就越多，相当于减少了io次数
- B+树查询效率稳定：所有数据存储在叶子节点，叶子节点的高度都一样，所以查询耗时均衡，不会像B-树一样因为数据所在节点的高度而影响耗时
- B+树范围查询更方便：B+树叶子节点构成双向链表，所以仅需要进行链表遍历就可以进行范围查询，而B-树则需要从root节点重新查询
在真实的数据库中，数据量几十万和几千万的表，B+树索引层高也就3-4层，所以如果通过B+树索引，几十万的数据量和几千万的数据量查询效率不会相差太大，因为都是3次io
聚簇索引
聚簇索引（clustered index）就是按照每张表的主键所建立的一棵B+树，所以每张表只能有一个聚簇索引。
查询优化器会尽量选择采用聚簇索引来检索，因为聚簇索引能够在B+树叶子节点直接找到目标数据，由于叶子节点数据之间是靠双链表连接，所以能很方便的进行范围查询。
辅助索引
也成为非聚簇索引（secondary index）,与聚簇索引最大的不同在于，辅助索引叶子节点保存的是聚簇索引，关系如下：
所以，如果通过辅助索引来检索，过程就是这样的：先通过辅助索引找到聚簇索引，在通过聚簇索引找到实际数据（这个过程称为回表）。如果辅助索引和聚簇索引层高都是3，那么通过辅助索引检索就需要6次io，而通过聚簇索引，只需要3次，这也是为什么在实际应用中应该多多使用聚簇索引。
Cardinality
cardinality的值非常关键，优化器会根据该值来决定是否要走这索引。可以使用show index from table xxx命令来查看。它表示索引中唯一值的估计，它与总行数的比值应该接近于1，如果比值很小，那么应该删除该索引。
它的计算方式：随机对8个叶子节点进行分析然后更新。更新cardinality的策略如下：
- 表1/16分之一的数据已经发生过变化
stat_modified_counter（发生变化的次数）> 20亿
也可以手动更新：analyze table xxx,如果表很大，该操作会比较耗时，生产核心库需要谨慎操作。
所以，这个值的并不是特别准确，因为它的计算方式是随机采样的。
cardinality指示了哪些列适合建来建B+树索引，那些不重复的、没有范围的、散列的列才适合建索引。工作中经常看到有同事会在enum类型的列上建索引（也不能作为联合索引的第一项），这是不对的，因为这些列的取值是重复的、范围恒定的、聚集的，建的B+树分叉太少，层数太高，长的很像链表，大大加大了io次数，走这些索引会增大耗时，也许超过全表扫描。
联合索引
联合索引指的是对表上的多个列进行索引，单个索引只针对于一个列，原理和单个索引一模一样，示例如下：
联合索引有个好处是：第二个key做了排序处理。所以，如果结果集需要根据第二个key做排序，走联合索引可以减少一次内存排序的操作，可以提升查询效率。
索引覆盖
如果能够从辅助索引中就能获取到目标记录，不需要进行回表操作（不需要检索聚簇索引），那么这个行为就称为索引覆盖。
索引覆盖有两个好处：
- 不需要回表：减少了聚簇索引检索的时间
- 优化统计查询count( ):由于辅助索引保存的是聚簇索引，所以它的大小远远小于聚簇索引，也就是辅助索引一个叶子节点的数据页里保存的行数更多，在进行统计查询时通过辅助索引更能够减少磁盘io。
对于统计查询count( )如果不带where条件，myisam的效率远远大于innodb，因为myisam只支持页级锁，所以它有行数计数器，那么它的结果返回速度与表大小无关，查询耗时也可以忽略不计；而innodb支持行锁并且由于MVCC存在，每次count( )都需要对每行进行判断是否对当前事务可见，所以效率很低。
优化器选择不使用索引的情况
明明你在某些列上建了索引，并且你的查询条件中也使用了这些列，但是解释器告诉你他走了全表扫描，也就是使用了聚簇索引。这种情形有可能是由以下两种情况引起的：
- 索引不合理：参考上面分析过的cardinality。
- 范围查询、join连接：如果要查询的数据量占据总表的20%时，优化器会选择全表扫描。虽然可以通过辅助索引能够顺序的查出聚簇索引，效率很高，但是再根据聚簇索引去查询具体数据时，就变成了随机访问磁盘，通过上面的磁盘分析可以知道该操作会大大降低io效率，所以优化器会选择直接顺序的全表扫描。（这里的顺序依然是逻辑上的顺序，不可能做到全部数据是物理磁盘上的连续。innodb是按照区来分配空间的，每个区1M，一次分配连续的1-5个区，这里的连续是指物理上的连续，但是不可能做到所有数据都是物理上连续的，因为那样做的成本太高了）。
索引提示
索引提示的意思就是你显示的告诉优化器使用哪个索引，有两种情况：
- 在有多个可使用索引的情况下，你认为优化器选择的那个不是最优的，你可以提示或者强制优化器使用某个索引
- 在可选择的索引非常多的情况下，优化器选择执行计划的耗时可能都比执行脚本本身。这时，dba或者研发需要显示的告诉优化器使用哪个索引
上面两种情况都告诉我们，建太多索引不但不能提升效率，还有可能降低效率，此外，innodb还会花资源来维护索引，进一步降低性能。
索引提示有两种语法：
- select * from table xx use index(xxx) where xx=xx : 这种方式只是提示优化器可以选择该索引，但是优化器有自己的想法，最终的执行计划如何取决于优化器的选择
- select * from table xx force index(xxx) where xx=xx : 这种方式是告诉优化器把自己的想法收起来，乖乖按照我指定的索引执行，这里的好处是优化器不用在耗费时间去在多个索引中找一个最优的
倒排索引
通过上面的分析可以得知，等值查询、范围查询、like的前缀查询（like xxx%）等都可以利用到B+树的高效优点，但是对于like %xxx% 的模糊查询，B+树无能为力。倒排索引（inverted index）的引入就是为了弥补这个innodb在这个场景的不足。
数据结构
通过一张辅助表（auxiliary table）来存储关键字和关键字在一个或多个文档中所在位置的映射，有两种表现形式：
- Inverted file index:(key,key所在文档的id)
- Full inverted index:(key,(key所在文档的id，在文档中的偏移量))
Full inverted index 不仅存了文档id还存了偏移量，所以它占更多的存储空间，但是能更快的定位实际位置。这两种方式都是将一篇没有结构的文档转换为结构化的数据，相当于为每个词都建立了索引，从而可以做到全文的搜索。
全文检索
为了提高并发性，在innodb存储引擎中共有6张auxiliary table，每张表根据key的latin编码进行分区。为了获取key的latin编码，首先需要进行分词，分词的操作是在插入的事务提交后完成的。英文分词很简单，根据空格就可以，而中文分词有较多的算法，并且比较复杂还会有二义性，所以innodb不支持中文的全文检索，不过innodb5.7之后提供了ngram全文检索插件，用来支持中文分词。使用方式如下：
1、在mysql配置文件中设置分词的大小
ngram_token_size=2分词越小，索引占用空间越大。
2、添加全文索引
alter table xx add fulltext index testfulltext(clumn1,clumn2) with PARSER ngram
因为auxiliary table是持久的表，并且存在磁盘上，所以为了提高性能，innodb引入了全文检索索引缓存（FTS index cache）,其结构是一个红黑树。由于是内存和磁盘的关系，所以此处会涉及缓存有效及宕机恢复等问题，不做过多介绍，只需知道innodb利用缓存提升了检索性能。
innodb的全文检索有以下限制：
- 每张表只能有一个全文检索索引
- 由多个列组成的全文检索索引必须使用相同的字符集和排序规则
- 不支持没有单词界定符（delimiter）的语言，如汉语、日语、韩语等，但可以使用ngram插件来解决
检索模式
innodb 使用全文检索的语法为：
select * from xx where match(clumn1,clumn2) against('key' in xxx mode)
innodb会将在where 条件中使用match( )函数的查询结果根据相关性进行降序排列，相关性是一个非负浮点数，0表示没有任何相关性，其计算依据如下：
- key是否在文档中出现
- key在文档中出现的次数
- key在索引列中的数量
- 包含该key的文档的数量
innodb支持四种检索模式
- nature language : innodb默认的全文检索模式。所以查询时候可以省略mode修饰，直接使用
select * from xx where match(clumn1,clumn2) against('key')
- boolean : 更为复杂查询模式，表示待查询key前后的操作符有特殊含义，支持的操作符如下：
- + : 该key必须存在
- - : 该key必须不存在
- (no operator) : 该key是可选的，但是如果出现，相关性会更高
- @distance : 表示多个查询的key的距离是否在distance范围之内，单位是字节。'"dog cat"@30' IN BOOLEAN MODE表示单词dog和cat之间的距离需要在30个字节之内
- > : 出现该key时增加相关性
- < : 出现该key时降低相关性
- ~ : 出现该key时相关性为负（全文检索允许出现负相关性）
- * : 出现以该key为前缀的词
- " : 表示短语
- query expansion : 全文检索的扩展查询
哈希索引
当服务器内存100多G甚至更大时候，想要找到一个被缓存的页，虽然内存中io速度很快，但也不能每次都要通过遍历的方式来查找，那是憨憨的做法。这时候需要对于字典操作只需要O(1)的哈希算法。
哈希算法
时间复杂度为O(1)的常见的简单的算法，就是将k个关键字映射到m个槽的某一个去，即k mod m，如果产生碰撞就采用链表法拉出一个链表。查询时候如果发现链表就进行遍历，此时遍历的数量会大大降低。
这里的链表法和HashMap的处理碰撞的方式如出一辙，只不过jdk1.8之后，HashMap引入了红黑树，当链表长度大于8后就转换为红黑树，这样再次降低了碰撞后的查询时间复杂度，从O(n)降到O(log n)。不过增加了操作的复杂度，因为增加了红黑数的左旋和右旋，还有链表转红黑树和红黑树转链表。但是总体性能1.8优于1.7。
自适应哈希索引
innodb中的哈希索引由mysql自身创建和管理，dba和研发不能进行干预，所以说它是自适应的。通过命令SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况。