MySQL-InnoDB存储引擎索引、B+树索引、哈希算法、全文检索_有哪些引擎支持b+树

概述

InnoDB存储引擎 支持 以下几种常见的索引：

• B+树索引
• 哈希索引
• 全文索引

InnoDB存储引擎 支持的 哈希索引 是 自适应的
InnoDB存储引擎 会根据 表的使用情况 自动 为表生成 哈希索引，不能人为干预是否在一张表中生成哈希索引

B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引
B+树索引 的构造 类似于 二叉树，根据键值（Key Value）快速找到数据。

注意　B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树。

B+树索引 并不能 找到 一个给定键值 的 具体行
B+树索引 能找到的 只是 被查找数据行 所在的“页”
然后数据库 通过 把页 读入到内存，再在内存中进行查找，最后得到要查找的数据

B+树(重要!!!)

B+树和二叉树、平衡二叉树一样，都是经典的数据结构
B+树 由 B树 和 索引顺序访问方法演化而来

B+树 是为 磁盘 或 其他直接存取辅助设备 设计的 一种 平衡查找树
在B+树中，所有记录节点 都是 按 键值的大小顺序 存放在 同一层的叶子节点上，由各叶子节点指针进行连接

插入

B+树的插入 必须保证 插入后 叶子节点中的记录 依然排序，同时需要考虑插入到B+树的三种情况，每种情况都可能会导致不同的插入算法

为了保持平衡对于新插入的键值可能需要做大量的拆分页（split）操作
因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作

B+树同样提供了类似于平衡二叉树的旋转（Rotation）功能
旋转 发生在 Leaf Page已经满，但是 其左右兄弟节点 没有满的情况下
这时B+树 并不会急于 去做 拆分页的操作，而是将 记录 移到 所在页 的 兄弟节点上
在通常情况下，左兄弟 会被 首先检查 用来做 旋转操作

删除

B+树 使用 填充因子（fill factor） 来控制 树的删除变化，50%是填充因子可设的最小值
B+树的删除操作 同样 必须保证 删除后 叶子节点中的记录依然排序，同插入一样，B+树的删除操作 同样需要考虑 以下三种情况，与插入不同的是，删除 根据 填充因子的变化 来衡量

B+树索引(重要!!!)

数据库中的B+树索引 可以分为 聚集索引（clustered inex）和 辅助索引（secondary index），但是 不管是 聚集 还是 辅助的索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据
聚集索引 与 辅助索引 不同的是，叶子节点 存放的 是否是 一整行的信息

聚集索引

InnoDB存储引擎表 是 索引组织表，即 表中数据 按照 主键顺序 存放
聚集索引（clustered index） 就是按照 每张表的主键 构造一棵B+树，同时 叶子节点中 存放的 即为 整张表的行记录数据，也将 聚集索引的叶子节点 称为 数据页
聚集索引的这个特性 决定了 索引组织表中(的)数据 也是 索引的一部分
同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接

由于实际的数据页 只能按照 一棵 B+树 进行排序，因此每张表只能拥有一个聚集索引。

在多数情况下，查询优化器倾向于采用聚集索引
因为聚集索引 能够 在B+树索引 的 叶子节点上 直接找到数据
此外，由于定义了数据的逻辑顺序，聚集索引 能够 特别快地 访问 针对范围值的查询
查询优化器 能够快速发现 某一段范围的数据页需要扫描

数据页上 存放的是 完整的 每行的记录
而在非数据页的索引页中，存放的 仅仅是 键值 及 指向数据页 的 偏移量，而不是一个完整的行记录

聚集索引的存储并不是物理上连续的，而是逻辑上连续的

• 一是(数据)页通过双向链表链接，(数据)页按照主键的顺序排序
• 另一点是每个(数据)页中的记录 也是通过 双向链表 进行维护的，物理存储上可以同样不按照主键存储

聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快，叶子节点的数据 就是 用户所要查询的数据

如果 针对 主键使用ORDER BY对记录进行排序，但是在实际过程中并没有进行所谓的filesort操作，这就是因为聚集索引的特点
如果要查找 主键某一范围内的数据，通过 叶子节点 的 上层中间节点 就可以得到 页的范围，之后直接读取数据页即可

辅助索引

对于辅助索引（Secondary Index，也称非聚集索引），叶子节点 并不包含 行记录的全部数据
叶子节点 除了 包含 键值以外，每个叶子节点中的索引行中 还包含了 一个书签（bookmark），该书签 用来告诉 InnoDB存储引擎 哪里可以找到 与索引相对应的行数据
由于InnoDB存储引擎表 是 索引组织表，因此InnoDB存储引擎 的 辅助索引的书签 就是 相对应行数据 的 聚集索引键

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

B+树索引的分裂

B+树索引页的分裂 并不总是 从页的中间记录 开始，这样可能会导致页空间的浪费
InnoDB存储引擎的Page Header中有以下几个部分用来保存插入的顺序信息：

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通过这些信息，InnoDB存储引擎 可以决定 是向左还是向右 进行分裂，同时决定 将分裂点 记录为哪一个
若插入是随机的，则取页的中间记录 作为 分裂点的记录

若 往同一方向 进行插入的记录数量为5，并且 目前已经定位（cursor）到的记录（InnoDB存储引擎插入时，首先需要进行定位，定位到的记录 为 待(要)插入记录 的 前一条记录）之后 还有3条记录
则 分裂点的记录 为 定位到的记录 后的 第3条记录
否则 分裂点记录 就是 待插入的记录

B+树索引的管理

索引管理

索引的创建和删除可以通过两种方法，一种是ALTER TABLE，另一种是CREATE/DROP INDEX
通过ALTER TABLE创建索引的语法为：

ALTER TABLE tbl_name
|ADD{INDEX|KEY}[index_name]
[index_type](index_col_name,...)[index_option]...

ALTER TABLE tbl_name
DROP PRIMARY KEY
|DROP{INDEX|KEY}index_name
1
2
3
4
5
6
7

CREATE/DROP INDEX的语法同样很简单：

CREATE[UNIQUE]INDEX index_name
[index_type]
ON tbl_name(index_col_name,...)

DROP INDEX index_name ON tbl_name
1
2
3
4
5

可以设置对整个列的数据进行索引，也可以只索引一个列的开头部分数据
若用户想要查看表中索引的信息，可以使用命令SHOW INDEX FROM table_name，每列的含义如下：

• Table：索引所在的表名
• Non_unique：非唯一的索引，primary key是0，因为必须是唯一的
• Key_name：索引的名字，可以通过这个名字来执行DROP INDEX
• Seq_in_index：索引中该列的位置
• Column_name：索引列的名称
• Collation：列以什么方式存储在索引中。可以是A或NULL。B+树索引总是A，即排序的。如果使用了Heap(堆)存储引擎，并且建立了Hash索引，这里就会显示NULL了。因为Hash根据Hash桶存放索引数据，而不是对数据进行排序
• Cardinality：非常关键的值，表示 索引中 唯一值 的 数目 的 估计值。Cardinality表的行数应尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此索引
• Sub_part：是否是 列的(某一)部分 被索引(比如列的前100个字符)，如果索引整个列，则该字段为NULL
• Packed：关键字如何被压缩。如果没有被压缩，则为NULL
• Null：是否 索引的列 含有NULL值
• Index_type：索引的类型，InnoDB存储引擎只支持B+树索引，所以这里显示的都是BTREE
• Comment：注释

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引
这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了
所以这个值是不太准确的，只是一个大概的值
如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令

Fast Index Creation-快速索引创建

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

• 首先创建一张新的临时表，表结构为通过命令ALTER TABLE新定义的结构
• 然后把原表中数据导入到临时表
• 接着删除原表
• 最后把临时表重名为原来的表名

可以发现，若用户对于一张大表进行索引的添加和删除操作，那么这会需要很长的时间
更关键的是，若有大量事务需要访问正在被修改的表，这意味着数据库服务不可用
而这对于Microsoft SQL Server或Oracle数据库的DBA来说，MySQL数据库的索引维护始终让他们感觉非常痛苦

InnoDB存储引擎从InnoDB 1.0.x版本开始支持一种称为Fast Index Creation（快速索引创建）的索引创建方式——简称FIC

对于辅助索引的创建，InnoDB存储引擎 会对 创建索引的表 加上一个 S锁(共享锁)
在创建的过程中，不需要重建表，因此速度较之前提高很多，并且数据库的可用性也得到了提高

删除辅助索引操作就更简单了，InnoDB存储引擎 只需更新 内部视图，并将 辅助索引(使用)的空间 标记为 可用，同时删除 MySQL数据库 内部视图上 对 该表的索引(的)定义即可

由于FIC在索引的创建的过程中对表加上了S锁(共享锁)，因此在创建的过程中 只能 对该表进行读操作，若有大量的事务需要对目标表进行写操作，那么数据库的服务同样不可用

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

需要特别注意的是，临时表的创建路径 是 通过参数tmpdir进行设置的
必须保证tmpdir有足够的空间可以存放临时表，否则会导致创建索引失败

Online Schema Change(待完善)

Online Schema Change（在线架构改变，简称OSC）最早是由Facebook实现的一种在线执行DDL的方式，并广泛地应用于Facebook的MySQL数据库
所谓“在线”是指在事务的创建过程中，可以有读写事务对表进行操作，这提高了原有MySQL数据库在DDL操作时的并发性

Online DDL

虽然FIC可以让InnoDB存储引擎避免创建临时表，从而提高索引创建的效率，但索引创建时 会阻塞 表上的DML操作
OSC虽然解决了上述的部分问题，但是还是有很大的局限性
MySQL 5.6版本开始支持Online DDL（在线数据定义）操作，其允许辅助索引创建的同时，还允许其他诸如INSERT、UPDATE、DELETE这类DML操作，这极大地提高了MySQL数据库在生产环境中的可用性

此外，不仅是辅助索引，以下这几类DDL操作都可以通过“在线”的方式进行操作：

• 辅助索引的创建与删除
• 改变自增长值
• 添加或删除外键约束
• 列的重命名

通过新的ALTER TABLE语法，用户可以选择索引的创建方式：

ALTER　TABLE tbl_name
|ADD{INDEX|KEY}[index_name]
[index_type](index_col_name,...)[index_option]...
ALGORITHM[=]{DEFAULT|INPLACE|COPY}
LOCK[=]{DEFAULT|NONE|SHARED|EXCLUSIVE}
1
2
3
4
5

ALGORITHM指定了创建或删除索引的算法

• COPY表示按照MySQL 5.1版本之前的工作模式，即创建临时表的方式
• INPLACE表示 索引创建或删除操作 不需要创建临时表
• DEFAULT表示根据参数old_alter_table来判断是通过INPLACE还是COPY的算法，该参数的默认值为OFF，表示采用INPLACE的方式

上面脚本中LOCK部分 为 索引创建或删除时 对表添加锁的情况，可有的选择为：

• NONE，执行索引创建或者删除操作时，对目标表不添加任何的锁，即事务仍然可以进行读写操作，不会收到阻塞，因此这种模式可以获得最大的并发度
• SHARE，这和之前的FIC类似，执行索引创建或删除操作时，对目标表加上一个S锁(共享锁)。对于并发地读事务，依然可以执行，但是遇到写事务，就会发生等待操作。如果存储引擎不支持SHARE模式，会返回一个错误信息
• EXCLUSIVE，在EXCLUSIVE模式下，执行索引创建或删除操作时，对目标表加上一个X锁(排他锁)。读写事务都不能进行，因此会阻塞所有的线程，这和COPY方式运行得到的状态类似，但是不需要像COPY方式那样创建一张临时表
• DEFAULT，DEFAULT模式 首先 会判断 当前操作 是否可以使用 NONE模式，若不能，则判断 是否可以使用 SHARE模式，最后判断 是否可以使用 EXCLUSIVE模式。也就是说DEFAULT会通过判断事务的最大并发性来判断执行DDL的模式

InnoDB存储引擎实现Online DDL的原理是 在执行创建或者删除操作的同时，将INSERT、UPDATE、DELETE这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此达到数据的一致性
这个缓存的大小由参数innodb_online_alter_log_max_size控制，默认的大小为128MB

若要更新的表比较大，并且在创建过程中伴有大量的写事务，如遇到innodb_online_alter_log_max_size的空间不能存放日志时，会抛出类似如下的错误

Error:1799SQLSTATE:HY000(ER_INNODB_ONLINE_LOG_TOO_BIG)
Message:Creating index'idx_aaa'required more than'innodb_online_alter_log_max_size'bytes of modification log.Please try again.
1
2

对于这个错误，可以调大参数innodb_online_alter_log_max_size，以此获得更大的日志缓存空间
此外，还可以设置ALTER TABLE的模式为SHARE，这样在执行过程中不会有写事务发生，因此不需要进行DML日志的记录

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

Cardinality

并不是在所有的查询条件中出现的列都需要添加索引
对于什么时候添加B+树索引，一般的经验是，在访问 表中 很少一部分时 使用B+树索引才有意义
对于性别字段、地区字段、类型字段，它们可取值的范围很小，称为低选择性
例如按性别进行查询时，可取值的范围一般只有’M’、‘F’。因此SQL语句得到的结果可能是该表50%的数据（假设男女比例1∶1），这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即属于高选择性，则此时使用B+树索引是最适合的

怎样查看索引是否是高选择性的呢？可以通过SHOW INDEX结果中的列Cardinality来观察
Cardinality值非常关键，表示 索引中 不重复记录数量 的 预估值
同时需要注意的是，Cardinality是一个预估值，而不是一个准确值，基本上用户也不可能得到一个准确的值
在实际应用中，Cardinality/n_rows_in_table应尽可能地接近1
如果非常小，那么需要考虑是否还有必要创建这个索引

InnoDB存储引擎的Cardinality统计

在InnoDB存储引擎中，Cardinality统计信息的更新发生在两个操作中：INSERT和UPDATE
根据前面的叙述，不可能在每次发生INSERT和UPDATE时就去更新Cardinality信息，这样会增加数据库系统的负荷，同时对于大表的统计，时间上也不允许数据库这样去操作
因此，InnoDB存储引擎内部对更新Cardinality信息的策略为：

• 表中1/16的数据已发生过变化
• stat_modified_counter＞2 000 000 000

第一种策略为自从上次统计Cardinality信息后，表中1/16的数据已经发生过变化，这时需要更新Cardinality信息
第二种情况考虑的是，如果对表中某一行数据频繁地进行更新操作，这时表中的数据实际并没有增加，实际发生变化的还是这一行数据，则第一种更新策略就无法适用这这种情况。故在InnoDB存储引擎内部有一个计数器stat_modified_counter，用来表示发生变化的次数，当stat_modified_counter大于2 000 000 000时，则同样需要更新Cardinality信息

InnoDB存储引擎内部 是怎样 来进行 Cardinality信息的统计和更新操作的？
同样是通过采样的方法,默认InnoDB存储引擎对8个叶子节点（Leaf　Page）进行采用。采样的过程如下：

1. 取得B+树索引中叶子节点的数量，记为A
2. 随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，…，P8
3. 根据采样信息给出Cardinality的预估值：Cardinality=（P1+P2+…+P8）*A/8。

通过上述的说明可以发现，在InnoDB存储引擎中，Cardinality值是通过对8个叶子节点预估而得的，不是一个实际精确的值
每次对Cardinality值的统计，都是通过随机取8个叶子节点得到的，这同时又暗示了另一个Cardinality现象，即每次得到的Cardinality值可能是不同的
有一种情况可能使得每次观察到的索引Cardinality值都是一样的，那就是表足够小，表的叶子节点数小于或者等于8个。这时即使随机采样，也总是会采取到这些页，因此每次得到的Cardinality值是相同的

在InnoDB 1.2版本之前，可以通过参数innodb_stats_sample_pages用来设置统计Cardinality时每次采样页的数量，默认值为8
参数innodb_stats_method用来判断 如何对待 索引中 出现的NULL值记录
该参数默认值为nulls_equal，表示 将 NULL值记录 视为 相等的记录
其有效值还有nulls_unequal，nulls_ignored，分别表示 将NULL值记录 视为 不同的记录 和 忽略NULL值记录

当执行SQL语句ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX 以及 访问INFORMATION_SCHEMA架构下的表TABLES和STATISTICS时 会导致 InnoDB存储引擎 去 重新计算 索引的Cardinality值
若表中的数据量非常大，并且表中存在多个辅助索引时，执行上述这些操作可能会非常慢

InnoDB1.2版本提供了更多的参数对Cardinality统计进行设置

B+树索引的使用

不同应用中 B+树索引的 使用

在OLTP应用中，查询操作只从数据库中取得一小部分数据，一般可能都在10条记录以下，甚至在很多时候只取1条记录
如根据主键值来取得用户信息，根据订单号取得订单的详细信息，这都是典型OLTP应用的查询语句
在这种情况下，B+树索引建立后，对该索引的使用应该只是通过该索引取得表中少部分的数据
这时建立B+树索引才是有意义的，否则即使建立了，优化器也可能选择不使用索引

对于OLAP应用，情况可能就稍显复杂了。不过概括来说，在OLAP应用中，都需要访问表中大量的数据，根据这些数据来产生查询的结果，这些查询多是面向分析的查询，目的是为决策者提供支持
如这个月每个用户的消费情况，销售额同比、环比增长的情况。因此在OLAP中索引的添加根据的应该是宏观的信息，而不是微观，因为最终要得到的结果是提供给决策者的
在OLAP应用中，通常会需要对时间字段进行索引，这是因为大多数统计需要根据时间维度来进行数据的筛选

联合索引

联合索引是指对表上的多个列进行索引
联合索引的创建方法与单个索引创建的方法一样，不同之处仅在于有多个索引列

从本质上来说，联合索引也是一棵B+树，不同的是 联合索引的键值 的数量 不是1，而是大于等于2，如下图：

可以观察到多个键值的B+树情况，和单个键值的B+树并没有什么不同，键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据
就上面的例子来说，即（1，1）、（1，2）、（2，1）、（2，4）、（3，1）、（3，2）
数据按（a，b）的顺序进行了存放

因此，对于查询SELECT*FROM TABLE WHERE a=xxx and b=xxx，显然是可以使用（a，b）这个联合索引的
对于单个的a列查询SELECT*FROM TABLE WHERE a=xxx，也可以使用这个（a，b）索引
但对于b列的查询SELECT*FROM TABLE WHERE b=xxx，则不可以使用这棵B+树索引
可以看到叶子节点上的b值为1、2、1、4、1、2，显然不是排序的，因此对于b列的查询使用不到（a，b）的索引
这也是联合索引最左原理

联合索引的第二个好处是已经对第二个键值进行了排序处理
联合索引（a，b）其实是根据列a、b进行排序，因此下列语句可以直接使用联合索引得到结果：

SELECT...FROM TABLE WHERE a=xxx ORDER BY b
1

对于联合索引（a，b，c）来说，下列语句同样可以直接通过联合索引得到结果：

SELECT...FROM TABLE WHERE a=xxx ORDER BY b
SELECT...FROM TABLE WHERE a=xxx AND b=xxx ORDER BY c
1
2

但是对于下面的语句，联合索引不能直接得到结果，其还需要执行一次filesort排序操作，因为索引（a，c）并未排序：

SELECT...FROM TABLE WHERE a=xxx ORDER BY c
1

覆盖索引(重要)

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

如果一个索引包含了（或覆盖了） 满足 查询语句中 字段与条件的数据 就叫做 覆盖索引

覆盖索引技术最早是在InnoDB Plugin中完成并实现，这意味着对于InnoDB版本小于1.0的，或者MySQL数据库版本为5.0或以下的，InnoDB存储引擎不支持覆盖索引特性

对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1，primary key2，…，key1，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;
1
2
3
4

此外，在通常情况下，诸如（a，b）的联合索引，一般是不可以选择列b中所谓的查询条件
但是如果是统计操作，并且是覆盖索引的，则优化器会 进行选择 使用 联合索引

注：遇到以下情况，执行计划不会选择覆盖查询

• select选择的字段中 含有 不在索引中的字段 ，即索引没有覆盖全部的列
• where条件中 不能含有 对索引进行like的操作

优化器不使用索引的情况(待完善)

在某些情况下，当执行EXPLAIN命令进行SQL语句的分析时，会发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是直接进行全表的扫描来得到数据
这种情况多发生于范围查找、JOIN链接操作等情况下

可以使用关键字FORCE INDEX来强制使用某个索引

SELECT*FROM orderdetails FORCE INDEX(OrderID)
WHERE orderid > 10000 and orderid < 102000;
1
2

索引提示

MySQL数据库支持索引提示（INDEX HINT），显式地告诉优化器使用哪个索引
以下两种情况可能需要用到INDEX HINT

• MySQL数据库的优化器错误地选择了某个索引，导致SQL语句运行的很慢。这种情况在最新的MySQL数据库版本中非常非常的少见。优化器在绝大部分情况下工作得都非常有效和正确
• 某SQL语句可以选择的索引非常多，这时优化器选择执行计划时间的开销可能会大于SQL语句本身

在MySQL数据库中Index Hint的语法如下：

tbl_name[[AS]alias][index_hint_list]
index_hint_list:
index_hint[,index_hint]...
index_hint:
USE{INDEX|KEY}
[{FOR{JOIN|ORDER BY|GROUP BY}]([index_list])
|IGNORE{INDEX|KEY}
[{FOR{JOIN|ORDER BY|GROUP BY}](index_list)
|FORCE{INDEX|KEY}
[{FOR{JOIN|ORDER BY|GROUP BY}](index_list)
index_list:
index_name[,index_name]...
1
2
3
4
5
6
7
8
9
10
11
12

USE INDEX只是告诉优化器可以选择该索引，实际上优化器还是会再根据自己的判断进行选择
如果要确定指定某个索引来完成查询，那么最可靠的是使用FORCE INDEX，而不是USE INDEX

Multi-Range Read(MRR)优化(重要!!!)

MySQL5.6版本开始支持Multi-Range Read（MRR）优化
Multi-Range Read优化的目的 就是为了 减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，这对于IO-bound类型的SQL查询语句可带来性能极大的提升
Multi-Range Read优化可适用于range，ref，eq_ref类型的查询

MRR优化有以下几个好处：

• MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找
• 减少缓冲池中页被替换的次数
• 批量处理对键值的查询操作

对于InnoDB和MyISAM存储引擎 的 范围查询 和 JOIN查询操作，MRR的工作方式如下：

• 将 查询得到的 辅助索引键值 存放于 一个缓存中，这时 缓存中的数据 是根据 辅助索引键值 排序的
• 将缓存中的键值根据RowID进行排序
• 根据RowID的排序顺序来访问实际的数据文件

此外，若InnoDB存储引擎或者MyISAM存储引擎的缓冲池不是足够大，即不能存放下一张表中的所有数据，此时频繁的离散读操作 还会导致 缓存中的页被替换出缓冲池，然后又不断地被读入缓冲池
若是按照主键顺序进行访问，则可以将此重复行为降为最低

Multi-Range Read还可以 将某些范围查询，拆分为键值对，以此来进行 批量的数据查询
这样做的好处是可以在拆分过程中，直接过滤一些不符合查询条件的数据，例如：

SELECT*FROM t
WHERE key_part1 >=1000 AND key_part1 < 2000
AND key_part2 = 10000;
1
2
3

倘若启用了Multi-Range Read优化，优化器会先将查询条件进行拆分，然后再进行数据查询
就上述查询语句而言，优化器会将查询条件拆分为（1000，1000），（1001，1000），（1002，1000），…，（1999，1000），最后再根据这些拆分出的条件进行数据的查询

是否启用Multi-Range Read优化可以通过参数optimizer_switch中的标记（flag）来控制
当mrr为on时，表示启用Multi-Range Read优化

mrr_cost_based标记 表示 是否通过cost based的方式 来选择 是否启用mrr
若将mrr设为on，mrr_cost_based设为off，则总是启用Multi-Range Read优化

参数read_rnd_buffer_size用来控制键值的缓冲区大小，当大于该值时，则执行器对已经缓存的数据根据RowID进行排序，并通过RowID来取得行数据。该值默认为256K

Index Condition Pushdown（ICP）优化(待完善)

Multi-Range Read一样，Index Condition Pushdown同样是MySQL 5.6开始支持的一种 根据索引进行查询 的 优化方式
之前的MySQL数据库版本不支持Index Condition Pushdown，当进行索引查询时，首先根据索引来查找记录，然后再根据WHERE条件来过滤记录
在支持Index Condition Pushdown后，MySQL数据库会在取出索引的同时，判断 是否可以进行 WHERE条件的过滤，也就是将 WHERE的部分过滤操作 放在了 存储引擎层
在某些查询下，可以大大减少上层SQL层对记录的索取（fetch），从而提高数据库的整体性能

Index Condition Pushdown优化支持range、ref、eq_ref、ref_or_null类型的查询，当前支持MyISAM和InnoDB存储引擎
当优化器选择Index Condition Pushdown优化时，可在执行计划的列Extra看到Using index condition提示

注意　NDB Cluster存储引擎支持Engine Condition Pushdown优化
不仅可以进行“Index”的Condition Pushdown，也可以支持非索引的Condition Pushdown，不过这是由其引擎本身的特性所决定的
另外在MySQL 5.1版本中NDB Cluster存储引擎就开始支持Engine Condition Pushdown优化

阅读参考(重要!!!)：
神奇的 SQL 之 ICP → 索引条件下推
神奇的 SQL 之 WHERE 条件的提取与应用

Batched Key Access(BKA) 和 Block Nested-Loop(BNL)(待完善)

阅读参考：InnoDB ICP、MRR、BAK特性

哈希算法

哈希表

哈希表（Hash Table）也称散列表，由 直接寻址表 改进 而来
先来看直接寻址表，当关键字的全域U比较小时，直接寻址是一种简单而有效的技术

假设某应用要用到一个 动态集合(下图中右侧的部分)，其中每个元素 都有一个 取自全域U={0，1，…，m-1} 的 关键字。同时假设没有两个元素具有相同的关键字
用一个数组(右侧)（即直接寻址表）T[0…m-1] 表示 动态集合，其中每个位置（或称槽或桶） 对应 全域U中的一个关键字,，如下图
槽k 指向 集合中 一个关键字为k的元素
如果该集合中没有关键字为k的元素，则T[k]=NULL

直接寻址技术存在一个很明显的问题，如果域U很大，在一台典型计算机的可用容量的限制下，要在机器中存储大小为U的一张表T就有点不实际，甚至是不可能的
如果实际要存储的关键字集合K 相对于 U来说很小，那么分配给T的大部分空间都要浪费掉

在哈希方式下，该元素处于h(k)中，即利用 哈希函数h，根据 关键字k 计算出 槽的位置
函数h 将 关键字域U 映射到 哈希表T[0…m-1]的槽位上

哈希表技术很好地解决了直接寻址遇到的问题，但是这样做有一个小问题，如上图的两个关键字可能映射到同一个槽上
一般将这种情况称之为发生了碰撞（collision）
在数据库中一般采用最简单的碰撞解决技术，这种技术被称为链接法（chaining）

在链接法中，把 散列到 同一槽中的所有元素 都放在 一个链表中，如下图所示
槽j中有一个指针，它指向 由所有散列到j的元素 构成的链表 的 头
如果不存在这样的元素，则j中为NULL

最后要考虑的是哈希函数h 必须可以 很好地 进行散列
最好的情况是能避免碰撞的发生
即使不能避免，也应该使碰撞在最小程度下产生
一般来说，都将关键字转换成自然数，然后通过 除法散列、乘法散列或全域散列来实现
数据库中一般采用除法散列的方法，在哈希函数的除法散列法中，通过 取 k除以m 的 余数，将关键字k映射到m个槽的某一个去，即哈希函数为：h(k)=k mod m

InnoDB存储引擎中的哈希算法

InnoDB存储引擎 使用 哈希算法 来对 字典进行查找，其 冲突机制 采用 链表方式，哈希函数 采用 除法散列 方式
对于 缓冲池页 的 哈希表来说，在缓冲池中的Page页 都有一个 chain指针，它 指向 相同哈希函数值 的 页
对于除法散列，除数m的取值为 略大于2倍的 缓冲池页数量的质数

例如：当参数innodb_buffer_pool_size的大小为10M，则共有640个16KB的页(在InnoDB存储引擎中，默认每个页的大小为16KB)
对于 缓冲池(的)页 (的)内存 的 哈希表来说，需要分配640×2=1280个槽，但是由于1280不是质数，需要取比1280略大的一个质数，应该是1399，所以在启动时会分配1399个槽的哈希表，用来 哈希查询 所在缓冲池中 的 页

InnoDB存储引擎的缓冲池 对于 其中的页 是怎么进行查找的呢？上面只是给出了一般的算法，怎么将 要查找的页 转换成 自然数？
InnoDB存储引擎 的 表空间 都有一个 space_id，用户所要查询的 应该是 某个表空间 的 某个连续16KB 的 页，即 偏移量offset。InnoDB存储引擎 将 space_id左移20位，然后 加上这个 space_id 和 offset，即关键字K=space_id << 20 + space_id + offset，然后通过 除法 散列到 各个槽中去

自适应哈希索引

自适应哈希索引 采用 哈希表的方式实现
不同的是，这仅是数据库自身创建并使用的，DBA本身并不能对其进行干预
自适应哈希索引 经 哈希函数 映射到 一个哈希表中，因此对于字典类型的查找非常快速

哈希索引 只能用来 搜索 等值的查询，对于其他查找类型，如范围查找，是不能使用哈希索引的

通过命令SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况
通过参数innodb_adaptive_hash_index来禁用或启动此特性

全文检索

基本介绍

全文检索（Full-Text Search） 是将 存储于 数据库中的整本书或整篇文章中的任意内容信息 查找出来 的 技术
它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析

在之前的MySQL数据库中，InnoDB存储引擎并不支持全文检索技术
大多数的用户转向MyISAM存储引擎，这可能需要进行表的拆分，并将需要进行全文检索的数据存储为MyISAM表
这样的确能够解决逻辑业务的需求，但是却丧失了InnoDB存储引擎的事务性，而这在生产环境应用中同样是非常关键的

从InnoDB 1.2.x版本开始，InnoDB存储引擎开始支持全文检索，其支持MyISAM存储引擎的全部功能

倒排索引

全文检索 通常使用 倒排索引（inverted index）来实现
倒排索引同B+树索引一样，也是一种索引结构
它在辅助表（auxiliary table）中 存储了 单词与单词自身 在一个或多个文档中 所在位置之间 的 映射
这通常利用关联数组实现，其拥有两种表现形式：

• inverted file index，其表现形式为{单词，单词所在文档的ID}
• full invertedindex，其表现形式为{单词，(单词所在文档的ID，在具体文档中的位置)}

例如，表t存储的内容如下所示：

DocumentId 表示 进行全文检索文档的Id，Text表示存储的内容，用户需要对存储的这些文档内容进行全文检索。例如，查找出现过Some单词的文档Id，又或者查找单个文档中出现过两个Some单词的文档Id，等等
对于inverted file index的关联数组，其存储的内容如下所示：
可以看到单词code存在于文档1和4中，单词days存在与文档3和6中
之后再要进行全文查询就简单了，可以直接根据Documents得到包含查询关键字的文档
对于inverted file index，其仅存取文档Id，而full inverted index存储的是对(pair)，即(DocumentId，Position)，因此其存储的倒排索引如下所示：
full inverted index还存储了单词所在的位置信息，如code这个单词出现在（1∶6），即文档1的第6个单词为code。相比之下，full inverted index占用更多的空间，但是能更好地定位数据，并扩充一些其他的搜索特性

InnoDB全文检索

InnoDB存储引擎从1.2.x版本开始支持全文检索的技术，其采用full inverted index的方式
在InnoDB存储引擎中，将(DocumentId，Position)视为一个“ilist”
因此在全文检索的表中，有两个列，一个是word字段，另一个是ilist字段，并且在word字段上有设有索引
此外，由于InnoDB存储引擎在ilist字段中存放了Position信息，故可以进行Proximity Search(邻近搜索)，而MyISAM存储引擎不支持该特性

在InnoDB存储引擎中，为了提高全文检索的并行性能，共有6张Auxiliary Table，目前每张表根据word的Latin编码进行分区
Auxiliary Table是持久的表，存放于磁盘上

FTS Index Cache-全文检索索引缓存

在InnoDB存储引擎的全文索引中，还有另外一个重要的概念FTS Index Cache（全文检索索引缓存），其用来提高全文检索的性能
FTS Index Cache是一个红黑树结构，其根据（word，ilist）进行排序
这意味着插入的数据已经更新了对应的表，但是 对全文索引的更新 可能在 分词操作后 还在FTS Index Cache中，Auxiliary Table可能还没有更新
InnoDB存储引擎会批量对Auxiliary Table进行更新，而不是每次插入后更新一次Auxiliary Table
当对全文检索进行查询时，Auxiliary Table首先会将在FTS Index Cache中对应的word字段合并到Auxiliary Table中，然后再进行查询
这种merge操作非常类似之前介绍的Insert Buffer的功能，不同的是Insert Buffer是一个持久的对象，并且其是B+树的结构
然而FTS Index Cache的作用又和Insert Buffer是类似的，它提高了InnoDB存储引擎的性能，并且由于其根据红黑树排序后进行批量插入，其产生的Auxiliary Table相对较小

InnoDB存储引擎允许用户查看指定倒排索引的Auxiliary Table中分词的信息，可以通过设置参数innodb_ft_aux_table来观察倒排索引的Auxiliary Table

SET GLOBAL innodb_ft_aux_table='表名';
1

在上述设置完成后，就可以通过查询information_schema架构下的表INNODB_FT_INDEX_TABLE得到相应表中的分词信息

当数据库关闭时，在FTS Index Cache中的数据库会同步到磁盘上的Auxiliary Table中
然而，如果当数据库发生宕机时，一些FTS Index Cache中的数据库可能未被同步到磁盘上。那么下次重启数据库时，当用户对表进行全文检索（查询或者插入操作）时，InnoDB存储引擎会自动读取未完成的文档，然后进行分词操作，再将分词的结果放入到FTS Index Cache中

参数innodb_ft_cache_size用来控制FTS Index Cache的大小，默认值为32M
当该缓存满时，会将其中的(word，ilist)分词信息同步到磁盘的Auxiliary Table中
增大该参数可以提高全文检索的性能，但是在宕机时，未同步到磁盘中的索引信息可能需要更长的时间进行恢复

FTS Document ID

在InnoDB存储引擎中，为了支持全文检索，必须有一个列与word进行映射，在InnoDB中这个列被命名为FTS_DOC_ID，其类型必须是BIGINT UNSIGNED NOT NULL，并且InnoDB存储引擎自动会在该列上加入一个名为FTS_DOC_ID_INDEX的Unique Index
上述这些操作都由InnoDB存储引擎自己完成，用户也可以在建表时自动添加FTS_DOC_ID，以及相应的Unique Index
由于列名为FTS_DOC_ID的列具有特殊意义，因此创建时必须注意相应的类型，否则MySQL数据库会抛出错误

分词的插入与删除

文档中分词的插入操作 是在 事务提交时完成
对于删除操作，其在事务提交时，不删除磁盘Auxiliary Table中的记录，而只是删除FTS Cache Index中的记录
对于Auxiliary Table中被删除的记录，InnoDB存储引擎 会记录 其FTS Document ID，并将其保存在DELETED auxiliary table中
在设置参数innodb_ft_aux_table后，同样可以访问information_schema架构下的表INNODB_FT_DELETED来观察删除的FTS Document ID
由于文档的DML操作 实际 并不删除 索引(辅助表)中的数据，相反 还会在 对应的DELETED表中插入记录，因此随着应用程序的允许，索引(辅助表)会变得非常大，即使索引(辅助表)中的有些数据已经被删除，查询也不会选择这类记录
为此，InnoDB存储引擎提供了一种方式，允许手工地将已经删除的记录从索引(辅助表)中彻底删除，该命令就是OPTIMIZE TABLE
因为OPTIMIZE TABLE还会进行一些其他的操作，如Cardinality的重新统计，若用户希望仅对倒排索引进行操作，那么可以通过参数innodb_optimize_fulltext_only进行设置

SET GLOBAL innodb_optimize_fulltext_only=1
OPTIMIZE TABLE table_name;
1
2

若被删除的文档非常多，那么OPTIMIZE TABLE操作可能需要占用非常多的时间，这会影响应用程序的并发性，并极大地降低用户的响应时间。用户可以通过参数innodb_ft_num_word_optimize来限制每次实际删除的分词数量。该参数的默认值为2000

stopword列表

stopword列表（stopword list）表示 该列表中的word 不需要对其 进行索引分词操作
例如，对于the这个单词，由于其不具有具体的意义，因此将其视为stopword
InnoDB存储引擎有一张默认的stopword列表，其在information_schema架构下，表名为INNODB_FT_DEFAULT_STOPWORD，默认共有36个stopword
此外用户也可以通过参数innodb_ft_server_stopword_table来自定义stopword列表

innodb_ft_server_stopword_table="table_name";
1

小结

当前InnoDB存储引擎的全文检索还存在以下的限制：

• 每张表 只能有一个 全文检索的索引
• 由 多列组合而成的 全文检索的索引列 必须使用 相同的字符集与排序规则
• 不支持没有单词界定符（delimiter）的语言，如中文、日语、韩语等

全文检索语法

MySQL数据库支持全文检索（Full-Text Search）的查询，其语法为：

MATCH(col1,col2,...)AGAINST(expr[search_modifier])
search_modifier:
{
IN NATURAL LANGUAGE MODE
|IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION
|IN BOOLEAN MODE
|WITH QUERY EXPANSION
}
1
2
3
4
5
6
7
8

MySQL数据库通过MATCH()…AGAINST()语法支持全文检索的查询
MATCH指定了需要被查询的列
AGAINST指定了使用何种方法去进行查询

Natural Language

全文检索通过MATCH函数进行查询，默认采用Natural Language模式，其表示 查询 带有 指定word 的文档

SELECT*FROM table_name
WHERE MATCH(column_name)
AGAINST('word'IN NATURAL LANGUAGE MODE);

SELECT*FROM table_nameWHERE MATCH(column_name) AGAINST('word');
1
2
3
4
5

注意：table_name是TEXT类型，并且有FULLTEXT INDEX 在其身上
若表没有创建倒排索引，则执行MATCH函数会抛出类似如下错误

ERROR 1191(HY000):Can't find FULLTEXT index matching the column list
1

在WHERE条件中使用MATCH函数，查询返回的结果 是根据 相关性（Relevance）进行降序排序的，即相关性最高的结果放在第一位
相关性的值是一个非负的浮点数字，0表示没有任何的相关性
根据MySQL官方的文档可知，其相关性的计算依据以下四个条件：

• word是否在文档中出现
• word在文档中出现的次数
• word在索引列中的数量
• 多少个文档包含该word

对于InnoDB存储引擎的全文检索，还需要考虑以下的因素：

• 查询的word在stopword列中，忽略该字符串的查询
• 查询的word的字符长度是否在区间[innodb_ft_min_token_size，innodb_ft_max_token_size]内，参数innodb_ft_min_token_size和innodb_ft_max_token_size控制InnoDB存储引擎查询字符的长度，当长度小于innodb_ft_min_token_size，或者长度大于innodb_ft_max_token_size时，会忽略该词的搜索。在InnoDB存储引擎中，参数innodb_ft_min_token_size的默认值为3，参数innodb_ft_max_token_size的默认值为84

Boolean

MySQL数据库允许使用IN BOOLEAN MODE修饰符 来进行 全文检索
当使用该修饰符时，查询字符串 的 前后字符 会有 特殊的含义
例如下面的语句要求查询有字符串Pease但没有hot的文档，其中+和-分别表示这个单词必须出现，或者一定不存在

SELECT * FROM table_name
WHERE MATCH(column_name) AGAINST('+Pease-hot' IN BOOLEAN MODE)
1
2

Boolean全文检索支持以下几种操作符：

• +表示该word必须存在。
• -表示该word必须被排除。
• （no operator）表示该word是可选的，但是如果出现，其相关性会更高
• @distance表示 查询的 多个单词之间的距离 是否在 distance之内，distance的单位是字节。这种全文检索的查询也称为Proximity Search(邻近搜索)。如MATCH（body）AGAINST（'"Pease pot"@30' IN BOOLEAN MODE）表示字符串Pease和pot之间的距离需在30字节内
• ＞表示出现该单词时增加相关性
• ＜表示出现该单词时降低相关性
• ～表示允许出现该单词，但是出现时相关性为负（全文检索查询允许负相关性）
• * 表示 以该单词开头的单词，如lik*，表示可以是lik、like，又或者likes
• " 表示短语

Query Expansion

MySQL数据库还支持全文检索的扩展查询
这种查询通常在查询的关键词太短，用户需要implied knowledge（隐含知识）时进行
例如，对于单词database的查询，用户可能希望查询的不仅仅是包含database的文档，可能还指那些包含MySQL、Oracle、DB2、RDBMS的单词
而这时可以使用Query Expansion模式来开启全文检索的implied knowledge

通过在查询短语中添加WITH QUERY EXPANSION或IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION可以开启blind query expansion（又称为automatic relevance feedback）。该查询分为两个阶段

• 第一阶段：根据搜索的单词进行全文索引查询
• 第二阶段：根据第一阶段产生的分词再进行一次全文检索的查询

索引匹配方式、索引设计原则(待完善)

explain字段含义(待完善)