InnoDB 存储引擎之索引和算法

本文主要是针对《Mysql技术内幕：InnoDB 存储引擎》一书中第五章关于 InnoDB 存储引擎的索引和算法的学习总结。

InnoDB 主要支持以下几种常见的索引：B+ 树索引，哈希索引，全文索引。

一、B+ 树索引

B+ 树索引的特点

B+ 树是为磁盘或者存取辅助设备设计的一种平衡查找树。
在 B+ 树中所有记录节点都是按照键值大小存放在同一层叶子节点上，并且各个叶子节点通过指针相连。
B+ 树索引并不能找到给定键值的具体行，而是能找到具体行所在的页，然后把该页读入内存中，再进行相应的查找。
B+ 树索引具有高扇出性，树的高度一般是 2~4 层，也就是查某一键值的行记录一般只需要 2~4 次。
数据库中 B+ 树索引分为聚集索引和辅助索引，叶子节点存放所有的数据。

聚集 B+ 树索引

聚集索引是按照每个表的主键构造的一颗 B+ 树，叶子节点是数据页，而非数据页的索引页中存放的仅仅是键值以及指向数据页的偏移量。
因为每张表只有一个主键，所以只能拥有一聚集索引。
聚集索引的存储不是物理上的连续，而是通过双向链表维持逻辑上的连续。
因为主键本身是排序的，如果查询时根据主键排序，不会产生再次的 filesort 操作。

辅助 B+ 树索引

辅助索引页称为非聚集索引，叶子节点并不包含行记录的全部数据。
叶子节点存放的是辅助索引的键值以及其对应主键值。
对于辅助索引的查找逻辑是先根据辅助索引页找到辅助索引对应的主键列表，然后再根据聚集索引页查到真正的行记录。

B+ 树索引的管理

索引的创建/删除

可以对索引的整个列进行索引，也可以只索引一个列的开头部分数据。
两种创建索引的方式(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 {INDEX|KEY} index_name

CREATE/DROP INDEX 一次只能创建一个索引，必须指定索引名称：

CREATE INDEX index_name
    [index_type] 
    ON table_name (index_col_name,...) [index_option]
    
DROP INDEX table_name
    ON table_name

可以通过 SHOW INDEX FROM table_name 查询相关索引信息：

SHOW INDEX 展示结果中每列的含义：

- Table：表的名称
- Non_unique：索引是否不唯一，0 表示唯一， 1 表示唯一
- Key_name：索引的名称
- Seq_in_index：该列在索引中位置，非联合索引都为 1，联合索引按照索引展示
- Column_name：列名称
- Collation：列以什么方式存储在索引中。可以是 A 或者 NULL，A 表示有序的，B+ 树索引都是 A
- Cardinality：索引中唯一值的数目的估计值，该值越大越好。该值不是实时计算的，可以通过运行 ANALYZE TABLE 进行更新
- Sub_part：如果列只是被部分地编入索引，如果是整列索引，则显示为 NULL
- Packed：指示关键字如何被压缩。如果没有被压缩，则为 NULL
- Null：如果列的定义中允许 NULL，则为 YES。如果没有，则该列含有 NO
- Index_type：索引的类型（BTREE, FULLTEXT, HASH, RTREE）
- Comment：注释

快速创建索引（Fast Index Creation）

MYSQL 5.5 版本之前对于索引的创建和删除都是通过复制的方式：

先创建一张临时表
然后把原表中的数据导入临时表
删除原始表
修改临时表的名字为原始表的名字

从 InnoDB 1.0.x 开始支持 Fast Index Creation 方式创建，简称 FIC。对于辅助索引的创建，首先会对该表加一个 S 锁，在创建的过程中不需要重建表，因此速度相对之前提高很多，但是创建的过程中只能对该表进行读，不能写。

在线数据定义(Online DDL)

从 Mysql 5.6 开始支持 Online DDL，允许辅助索引创建的同时还可以对表进行 UPDATE、DELETE、INSERT 操作，极大提高了数据库的可用性。

Online DDL 可以支持的操作如下：

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

创建索引通过选项 ALGORITHM 参数指定创建索引的方式：

ALGORITHM = COPY：表示通过创建临时表（复制）的方式
ALGORITHM = INPLACE：不需要创建临时表
ALGORITHM = DEFAULT：根据参数 old_alter_table 决定选择 COPY 还是 INPLACE 方式

Online DDL 的实现原理：

在创建索引时将 INSERT，UPDATE，DELETE 操作日志写入缓存，待完成索引创建后再重做引用到表上，保证了数据的一致性。
写入缓存的大小由参数 innodb_online_alter_log_max_size 参数设置，默认是 128MB。

Cardinality

上文中我们知道通过 SHOW INDEX 命令可以查看对应索引的 Cardinality，该值表示索引中不重复的预估值。

Cardinality 很关键，决定了索引是否具有高选择性，优化器会根据该值来判断是否使用索引。
该值越接近于表中真实的数据行数，选择性越高，如果使用索引的查询速度越快。
由于该值计算比较耗时，因此是一个预估的值，通过动态采样的方式计算得到。
默认情况下 InnnoDB 通过对 8 个叶子节点采样进行计算，通过参数 innodb_stats_sample_pages 来设置采样的个数。
ANALYSE TABLE，SHOW TABLE STATUS，SHOW INDEX 时都会导致重新去计算 Cardinality 的值，因此这些命令可以比较耗时。

B+ 树索引的应用

联合索引

联合索引是指对表中的多个字段进行索引。

联合索引要符合最左原则，假如我们建立了联合索引(a, b, c)，那么在查询时 [a], [a, b], [a, b, c] 的组合查询都可以使用该索引。
优化器对于联合索引的选择：

- 我们建一张表如下：
create table t (
    a int,
    b DATE
) ENGINNE=InnoDB;

alter table t 
    add key a_index (a),
    add key a_b_index (a, b);

- 执行如下查询，最终发现优化器选择 a_index 索引，因为该叶子节点包含单个键值，存放的记录更多
explain select * from t where a = 2;

- 执行如下查询，发现优化器选择 a_b_index 索引，因为在 a = 2 的情况下，b 已经排好序了，减少了一次排序的过程
explain select * from t where a = 2 order by b;

覆盖索引

覆盖索引是指从辅助索引中就可以查询出结果，而不需要查询聚集索引中真正的记录，由于辅助索引远远小于聚集索引，可以大大减少 IO 查询次数。

如果是使用了覆盖索引，则通过 explain 查看执行计划时会发现 Extra 字段显示为 Using index。
假如辅助索引 (key1, key2, key3)，聚集索引(pkey1, pkey2)，因为辅助索引叶子节点包含了 (pkey1, pkey2, key1, key2, key3)信息，对于这些值的查询都会使用覆盖索引。
select count(*) from table_name，如果存在辅助索引，优化器会选择辅助索引提高查询效率。

不使用索引的情况

在进行范围查找或者 join 连接操作时，在不能使用覆盖索引的情况下，如果发现使用辅助索引查找出来的结果占整个数据集蛮大一部分时，优化器会直接选择使用聚集索引进行全表顺序扫描。因为如果通过辅助索引查找到的数据较大时且为离散无序，则再会执行一次聚集索引的无序离散扫描，如果数据较大时，反而会降低性能。当然我们可以通过 force Index 来强制使用某个索引。

MRR 优化和 ICP 优化

MRR(Multi Range Read) 优化

MRR 优化是为了减少磁盘的随机访问次数，将随机访问转换为较为顺序的数据访问。优化策略如下：

- 将查询得到的辅助索引键值存放在缓存中
- 将缓存中的辅助索引键值根据 ROWID 排序
- 根据 ROWID 排序顺序来访问实际的数据文件，变成了较为顺序的聚集查询

使用 MRR 优化后，我们会在执行计划结果中看到 Extra 字段中含有 Using MRR

ICP(Index Condition Pushdown) 优化

ICP 从 MYSQL 5.6 版本开始支持，使用了 ICP 优化后，MYSQL 在取出索引的同时，判断是否可以进行 WHERE 条件的过滤。
也就是将 WHERE 条件的过滤放在存储引擎层，大大减少上层 SQL 层对数据的读取，从而提高性能。
如果使用 ICP 优化，执行计划的 Extra 字段会包含 Using Index Condition。

哈希索引

前面文章InnoDB 存储引擎的关键特性学习中提到过，哈希索引是自适应的，也就是 InnoDB 根据使用情况自动为辅助索引建立哈希索引，非人为干预。

通过 SHOW ENGINE INNODB STATUS 可以查看当前自适应哈希索引的使用情况
哈希索引只能用来搜索等值的查询，对于范围的查询便无能为力了
通过 innodb_adaptive_hash_index 参数可以用来禁用或者启动自适应哈希索引

全文检索

全文检索是将存储中数据库中的整本书或者整篇文章中的任意内容信息查找出来的技术，InnoDB 从 1.2.x 版本以后开始支持全文索引。

倒排索引

倒排索引是通过在辅助表中存放单词与单词在一个或者多个文档中所在位置的映射关系实现的，通常是用关联数组作存储结构。一般的存储形式有两种：

inverted file index： {单词，单词所在文档的 ID}
full inverted index： {单词，(单词所在文档的 ID，在具体文档的位置)}

InnoDB 全文检索的实现

InnoDB 存储引擎就是采用倒排索引中的 full inverted index 实现的。

Auxiliiary Table（辅助表）

存放倒排索引的表叫 Auxiliiary Table（辅助表），该表是持久的表，存放在磁盘上。

FTS Index Cache（全文检索索引缓存）

FTS Index Cache 是用来提高全文检索性能的，是一个红黑树结构。每次事务提交操作，InnoDB 会将倒排索引数据先插入到 FTS Index Cache 中，而不是每次都更新 Auxiliiary Table，然后在下次全文检索时，首先会将 FTS Index Cache 中 word 字段合并到 Auxiliiary Table，然后再进行查询，这种 Merge 操作很类似“插入缓存”的概念，

- innodb_ft_cache_size 参数用来控制 FTS Index Cache 的大小，默认是 32M。
- 当该缓存满时，会将其中数据同步到 Auxiliiary Table。

通过参数 innodb_ft_aux_table 设置来观察倒排索引表 Auxiliiary Table 中的数据：

-- 设置 innodb_ft_aux_table 等于 test 数据下的 table_a 表。
set GLOBAL innodb_ft_aux_table='test/table_a';
-- 通过 information_schema 下的表 INNODB_FT_INDEX_TABLE 便可以看到 Auxiliiary Table 数据信息。
select * from information_schema.INNODB_FT_INDEX_TABLE;

FTS_DOC_ID

- InnoDB 为了支持全文索引，每个设置全文索引的表中必须有一个字段用来标记文本的 ID，那就是 FTS_DOC_ID
- FTS_DOC_ID 类型是 BIGINT UNSIGNED NOT NULL
- InnoDB 会自动为 FTS_DOC_ID 列加上名为 FTS_DOC_ID_INDEX 的唯一索引

全文索引的删除操作

- InnoDB 对于删除操作，在事务提交时，并不会删除 Auxiliiary Table 中的记录，只是删除 FTS Index Cache 中的记录
- 在删除操作后，InnoDB 会记录其 FTS_DOC_ID 并保存在 DELETED Auxiliiary Table 中
- 通过 information_schema 下的表 INNODB_FT_DELETED 来观察删除的 FTS_DOC_ID
- 通过命令 OPTIMIZE TABLE 可以将已经删除的记录从 Auxiliiary Table 中彻底删除

stopword 列表

- stopword 列表中存放了不需要对其进行索引分词的单词列表
- 通过 information_schema.INNODB_FT_DEFAULT_STOPWORD 可以查看默认的 stopword 列表，默认 36 个
- 用户可以通过参数 innodb_ft_server_stopword_table 来自定义 stopword 列表

InnoDB 全文索引存在的限制：

- 每张表只能有一个全文检索的索引
- 由多个列组成的全文索引，每个列字符集和排序规则必须相同
- 不支持没有单词分界符的语言，如中文，日语等

全文索引语法

添加全文索引

- ALTER TABLE 时添加全文索引
alter table testtable add fulltext index testfulltext(clumn1,clumn2); 

- CREATE TABLE 时添加全文索引
CREATE TABLE articles ( 
    id INTUNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY, 
    title VARCHAR(200), 
    body TEXT, 
    FULLTEXT (title,body)
) ENGINE=InnoDB CHARACTER SET utf8mb4;

使用全文索引查找

通过 MATCH() … AGAINST() … 来进行全文检索的的查询，MATCH 指定了被查询的列，AGAINST 指定用何种方法进行查询。

- 如果没有设置全文索引使用 MATCH() ... AGAINST() ...，Mysql 会抛出异常
- 在使用 MATCH 函数进行查询，返回的结果按照返回结果的相关性降序排序，相关性由单词出现的次数，出现在几个文档中等来决定
- 如果查询的 word 在 stopword 列表中，则忽略该单词的查询
- 查询的 word 长度必须在区间[innodb_ft_min_token_size, innodb_ft_max_token_size]，默认是[3, 84]

Natural Language 查询模式

Natural Language 是默认的查询模式

- 按自然语言搜索模式查询 
SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('关键词' IN NATURAL LANGUAGE MODE);

BOOLEAN 查询模式

若全文检索按照 BOOLEAN 模式进行查询，那么查询字符串前后的字符有特殊含义：

1. +： 表示该 word 必须存在
2. -： 表示该 word 必须被排除
3. (no operator)：没有特殊表示 该 word 出现是可选的，如果出现，其相关性会更高
4. >: 表示该单词出现时，增加其相关性
5. <：表示该单词出现时，降低其相关性
6. ~：该单词出现，相关性为负
7. *：表示以该单词开头的单词

以下是以 BOOLEAN 模式进行查询的例子：

- 按布尔全文搜索模式查询，匹配既有管理又有数据库的记录 
SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('+数据库 +管理' IN BOOLEAN MODE); 

- 按布尔全文搜索模式查询，匹配有数据库，但是没有管理的记录 
SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('+数据库 -管理' IN BOOLEAN MODE); 

- 按布尔全文搜索模式查询，匹配MySQL，但是把数据库的相关性降低 
SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('>数据库 +MySQL' INBOOLEAN MODE);

Query Expansion

Mysql 还支持全文索引的扩展查询，通过在查询短语中添加 WITH QUERY EXPANSION 可以开启扩展查询，查询分为两个阶段：

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

select * from articles
    where MATCH(title, body)
    AGAINST('database' WITH QUERY EXPANSION)

Query Expansion 查询会来带一些非相关性查询，所以使用起来要谨慎

InnoDB 存储引擎之索引和算法

一、B+ 树索引

B+ 树索引的特点

聚集 B+ 树索引

辅助 B+ 树索引

B+ 树索引的管理

Cardinality

B+ 树索引的应用

哈希索引

全文检索

倒排索引

InnoDB 全文检索的实现

全文索引语法

继续阅读

Testlink安装部署之XAMPP

set define off关闭替代变量功能

报错：'mysql' 不是内部或外部命令，也不是可运行的程序或批处理文件。

Linxu常用命令技巧汇总

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艰难安装LDAP,SSL认证

《Linux命令行与Shell脚本编程大全第2版.布卢姆》pdf

MySQL的4种隔离级别？出现问题

XX系统实施过程问题总结

无组件上传图片到数据库中，最完整解决方案

【MySQL数据库】数据库索引事务1.索引2.事务

neo4j之cypher使用文档

NOSQL安全攻击

mybatis_入门程序Mybatis入门

登录plsql 报错 the account is locked --用户被锁

SequoiaDB巨杉数据库C++驱动概述