1. MySQL索引为什么使用B+树数据结构，而不是B树，红黑树等？
1.1 二叉查找树/二叉搜索树
下图b为二叉查找树的典型结构，其特点为：
- 任意节点左子树不为空,则左子树的值均小于根节点的值
- 任意节点右子树不为空,则右子树的值均大于于根节点的值
- 任意节点的左右子树也分别是二叉查找树
- 没有键值相等的节点
局限性： 如果数据排序好插入二叉查找树时，会退化为链表，此时时间复杂度为O（n），最好的情况是O（log n）。
1.2 AVL 树（Adelson-Velsky and Landis Tree，平衡二叉树）
由于二叉查找树的局限性，引入了AVL树，在插入数据时，调整这棵树，让它的节点尽可能均匀分布。该树节点左右子树深度之差只能是0，1，-1. 如果插入数据后，不满足平衡性，会通过旋转来实现平衡，具体的通过旋转保证平衡的四种操作参见专栏https://www.bilibili.com/read/cv8748171。
局限性：旋转是非常耗时的，故而AVL树适合用于插入删除次数比较少，但查找多的情况。
1.3 红黑树
红黑树是平衡二叉树的一种变体。红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是弱平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索、插入、删除操作较多的情况下，就用红黑树。Java8中，hashmap底层数据结构是基于数组和链表（红黑树 ）来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。通过key值计算hash码值，将其传递进数组，若hash码值冲突则采用链表连接，若该hashmap容量大于64且该链表长度大于8则将该链表转化为红黑树，若链表长度减少到6时候，则将红黑树转化回链表。
红黑树的特征：
- 每个节点非红即黑
- 根节点是黑的
- 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的
- 如果一个节点是红的,那么它的两儿子都是黑的
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
- 高度始终保持在h = logn红黑树的查找、插入、删除的时间复杂度最坏为O(log n)
同样的通过旋转保证平衡的操作参见专栏 https://www.bilibili.com/read/cv8748171。
为什么文件系统和数据库常使用B树及其变体B+树存储数据索引呢？
红黑树每个节点最多只有两个子节点，而B树，B+树是多路查找树，分支多则层数变少。文件系统和数据库的索引都是存放在磁盘上。磁盘IO次数与树的深度相同，由于磁盘特殊的结构，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O，即降低树的深度。故而不使用红黑树。
那可否设计为无限多路树，即退化为有序数组？
文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。B+树的多路存储允许每次加载B+树的一个结点，而后一步步往下找。
1.4 B树和B+树
B树和B+树的典型结构如下图所示，关于其特性可以参考博客 https://blog.csdn.net/herr_kun/article/details/80550652：
B树
B+ 树
这里讨论的是，为什么使用B+树数据结构存储索引（帮助MySQL高效获取数据的数据结构）？
- 磁盘读写代价更低 B+树的内部结点并没有指向关键字（root中的5，28，65）具体信息的指针。因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
- 遍历数据更加方便 多数时候需要从数据库中select多条数据，好比按照id进行排序后选100条。若是是多条的话，B树须要作局部的中序遍历，可能要跨层访问。而B+树因为全部数据都在叶子结点不用跨层，同时因为有链表结构，只须要找到首尾，经过链表横向遍历即可。为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存（不需要寻道时间，只需很少的旋转时间）。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
- 查询效率更加稳定 非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当
2. B+树索引
B+树索引在数据库中有一个特点是高扇出（指该模块直接调用的下级模块的个数）性，B+树的高度一般都在2~4层，即查询某一键值的行记录时最多只需要2到4次IO，查询时间在0.02~0.04秒。B+树索引可以分为聚集索引和辅助索引。
2.1 聚集索引
InnoDB存储引擎是索引组织表，即表中数据按照主键顺序存放。聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。
数据页上存放的是完整的每行的记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量。聚集索引的存储并不是物理上连续的，而是逻辑上连续的。
聚集索引对于主键的排序查找和范围查找速度非常快。如果查找主键某一范围内的数据，通过叶子节点的上层中间节点就可以找到页的范围，之后直接读取数据页即可。
2.2 辅助索引
对于辅助索引（secondary index），叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark，相应行数据的聚集索引键）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。 当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。
2.3 索引的创建与删除
2.4 Fast Index Creation
MySQL数据库对主键的添加和删除过程为：
- 首先创建一张新的临时表，表结构通过命令ALTER TABLE新定义的结构
- 然后把原表中数据导入到临时表
- 接着删除原表
- 最后把临时表重命名为原来的表名
对于辅助索引的创建，InnoDB存储引擎会对创建索引的表加上一个S锁。在创建过程中，不需要重建表，故而速度更快。删除辅助索引时，InnoDB存储引擎只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图上对该表的索引定义即可。
3. Cardinality 值
如果某个字段的取值范围很广，几乎没有重复，既属于高选择性，最适合用于B+树索引。Cardinality值表示索引中不重复记录数量的预估值。Cardinality/n_rows_in_table应尽可能接近1.
4. B+树索引的使用
4.1 联合索引
联合索引对表上的多个列进行索引。联合索引也是一颗B+树。
对于查询SELECT * FROM TABLE WHERE a=xxx and b=xxx/ SELECT * FROM TABLE WHERE a=xxx ORDER BY b 可以使用（a,b）联合索引。
对于查询SELECT * FROM TABLE WHERE a=xxx，也可以使用联合索引。
但是对于SELECT * FROM TABLE WHERE b=xxx，不能使用联合索引，因为b列不是排好序的。
4.2 覆盖索引
InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。
对于InnoDB存储引擎的辅助索引，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1, primary key2, ..., key 1, key2, ...）例如，下面语句可使用一次覆盖索引完成：
SELECT key2 FROM table WHERE key1 = xxx
SELECT primary key2, key2 FROM table WHERE key1=xxx
SELECT primary key1, key2 FROM table WHERE key1=xxx
SELECT primary key1, primary key2, key2 FROM table WHERE key1=xxx
4.3 优化器选择不使用索引的情况
在某些情况下，当执行EXPLAIN命令进行SQL语句分析时，会发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也即是直接进行全表扫描来得到数据。这种情况多发生于范围查找、JOIN链接操作等情况。例如：
SELECT * FROM orderdetails WHERE orderid>10000 and orderid<102000;
上述扫描可以通过orderid辅助索引来进行扫描，但是实际优化器使用聚集索引进行扫描。
这时因为用户选取的数据是整行信息，而OderID索引查询到指定数据，还需要进行一次书签访问来查找整行数据信息。虽然OderID索引中数据是顺序存放的，但是再进行一次书签查找的数据则是无序的，即磁盘上的离散读操作。如果要求访问的数据量很小，则优化器还是会选择辅助索引，但是当访问的数据占整个表中数据超过20%左右，优化器会选择聚集索引来查找数据。但是若使用的磁盘是固态硬盘，随机读操作很快，可以通过使用FORCE INDEX来强制使用某个索引：
SELECT * FROM orderdetails FORCE INDEX（OrderID）WHERE orderid>10000 and orderid<102000;
4.4 索引提示
MySQL数据库支持索引提示，显式地告诉优化器使用哪个索引，有两种情况可能用到INDEX HINT：
- MySQL数据库地优化器错误的选择了某个索引，导致查询很慢。这种情况较为少见，大多数时候优化器工作的非常有效
- 某SQL语句可以选择的索引非常多，这时优化器进行各个执行路径地成本分析开销可能会大于SQL语句本身。DBA或开发人员分析最优的索引选择，然后通过FORCE INDEX来强制优化器按指定索引完成查询
4.5 Multi-Range Read优化
MRR地好处：
- MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序地顺序进行书签查找
- 减少缓冲池中页被替换地次数
- 批量处理对键值的查询操作
对于InnoDB和MyISAM存储引擎的范围查询和JOIN查询操作，MRR工作方式为：
- 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据根据辅助索引键值排序的
- 将缓存中的键值根据RowID进行排序
- 根据RowID的排序顺序来访问实际地数据文件
此外，MRR还可以将某些范围查询，拆分为键值对，以此来进行批量的数据查询。例如：SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1<2000 AND key_part2 = 10000.
若没有MRR，此时查询类型为range，SQL优化器会先将key_part1大于1000且小于2000的数据都取出，然后再按key_part2的条件进行过滤。
若启用了MRR优化，优化器会先将查询条件进行拆分（（1000，1000），（1001,1000）（1002,1000）...（1999,1000）），然后再进行数据查询。
4.6 Index Condition Pushdown (ICP) 优化
在进行索引查询时，首先根据索引查找记录，然后判断是否可以进行WHERE条件的过滤，也就是将WHERE的部分过滤操作放在了存储引擎层。在某些查询下，可以大大减少上层SQL层对记录的索取，从而提高数据库的整体性能。
ICP优化支持range，ref, eq_ref, ref_or_null类型的查询，当优化器选择ICP优化时，可在执行计划的列Extra看到Using Index Condition提示。
5. hash索引
hash索引进行字典类型的数据查询（SELECT * FROM TABLE WHERE index_col='xxx'）的时间复杂度为O（1）。但是对于范围查找却无能为力。
6. 全文检索
6.1 概述
下面的SQL语句可以查询博客内容以xxx开头的文章，并且只要content添加了B+树索引，就能利用索引进行快速查询。
SELECT * FROM blog WHERE content like 'xxx%'
然而，更多的时候，用户需要查询的是博客内容包含单词xxx的文章，即：
SELECT * FROM blog WHERE content like '%xxx%'
全文检索（full-text search）是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。
6.2 倒排索引
倒排索引也是一种索引结构。它在辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。有两种表现形式：
- inverted file index {单词，单词所在文档ID}
- full inverted index {单词，（单词所在文档的ID，在文档中的位置）}
6.3 InnoDB 全文检索
在InnoDB存储引擎中，将（documentid， position）视为一个ilist。因此，在全文检索的表中，有两个列，一个是Word段，一个是ilist段，这个表称为Auxiliary Table（辅助表），存放于磁盘上。FTS Index Cache（全文检索索引缓存）是一个红黑树结构，用来提高全文检索的性能。参数innodb_ft_cache_size用来控制FTS Index Cache的大小，默认值是32M。当该缓存满时，会将其中的（word，ilist）分词信息同步到磁盘的Auxiliary Table中。增大该参数可以提高全文检索的性能，但是在宕机时，未同步到磁盘中的索引信息需要更多时间来回复。
stopword列表表示该列表中的Word不需要对其进行索引分词操作，例如单词the。
InnoDB 全文检索存在以下限制：
- 每张表只能有一个全文检索的索引
- 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则
- 不支持没有单词界定符的语言，如中文，日语，韩语等
6.4 全文检索
语法为：
正负表示这个单词一定出现或者一定不存在。