5.1 InnoDB 存储引擎索引概述

常见的索引：

1 B+ 数索引

2 全文索引

3 哈希索引 ： 哈希索引是自适应的， InnoDB 存储引擎根据表的使用情况自动为表生成哈希索引。

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

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

5.2 数据结构与算法

5.2.1 二分查找法

每页 Page Directory 中的槽 是按照主键的顺序存放的， 对于某一条具体记录的查询时通过对 Page Directory 进行二分查找得到的。（待理解）

5.2.2 二叉搜索树和平衡二叉树

在二叉查找树中， 左子树的键值总是小于根的键值， 右子树的键值总是大于根的键值。

平衡二叉树： 首先符合二叉查找树的定义， 其次必须满足任何节点的两个子树的高度最大差为 1.

5.3 B+ 树

5.3.1 B+ 数的插入操作

因为 B+ 数结构主要用于磁盘， 页的拆分意味着磁盘的操作， 所以应该在可能的情况下尽量减少页的拆分拆分。 因此， B+ 数同样提供了类似于平衡二叉树的旋转（Rotation）功能。(待理解)

5.3.2 B+ 数的删除操作

与插入不同的是， 删除根据填充因子的变化来衡量。

5.4 B+ 数索引

B+ 索引在数据库中一个特点是高扇出性， 因此在数据库中， B+ 数的高度一般都在 2~4 层。

B+ 数索引分为聚集索引（clustered index）和辅助索引（secondary index） ，内部都是 B+ 数， 叶子节点存放着所有的数据. 不同的是， 叶子节点存放的是否是一整行的信息。（存放所有数据存疑）

5.4.1 聚集索引 **

每张表只能拥有一个聚集索引。

// 通过 py_innodb_page_info 工具分析表空间。page level 为 0000 的即是数据页。 要分析 page // level 为 0001 的页， 当前聚集索引的 B+ 树高度为 2 ， 该页是 B+ 数的根                                        // 待实验

聚集索引的存储并不是物理上连续的， 而是逻辑上连续的。 这其中有两点： 一是页通过双向链表链接， 按照主键顺序排序； 另一点是每个页中的记录也是通过双向链表进行维护的， 物理存储上可以同样不按照主键存储。

聚集索引的另一个好处是， 它对于主键排序查找和范围查找速度非常快。

可以看到虽然使用 order by 对记录进行排序， 但在实际过程中并没有进行 filesort 操作。

另一个是范围查询（range query）， 如果要查找主键某一个范围内的数据， 通过叶子节点的上层中间节点就可以得到页的范围， 之后直接读取数据页即可。

rows 代表一个估计的值而不是一个确切的值。

5.4.2 辅助索引 **

当通过辅助索引来寻找数据时， InnoDB 存储引擎会遍历辅助索引并通过叶级别的指针获得执行指向聚集索引的主键， 然后通过主键索引来找到一个完整的行记录。

5.4.3 B+ 树索引的分裂

5.4.4 B+ 树索引的管理

1 索引管理

查看索引信息， show index from t；

Cardinality: 非常关键的值， 表示索引中唯一值的数据估计值。

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

2 Fast Index Creation(快速索引创建)

由于 FIC 在索引创建的过程中对表加上了 S 锁， 因此在创建过程中只能对该表进行读操作， 若有大量事务需要对目标进行写操作， 那么数据库的服务同样不可用。 此外， FIC 方式只限定于辅助索引， 对于主键的创建和删除同样需要重建一张表。

3 Online Schema Change（在线结构改变）

Mysql 5.6 版本开始支持 Online DDL 操作， 其允许辅助索引创建的同时， 还允许其他如 insert， update， delete 这类 DML 操作， 极大地提高了 MySQL 在生产环境的可用性。

其他

主键与聚集索引的区别：

问题：

聚集索引， 与 辅助索引 分别位于 B 数的什么位置？

1 若为聚集索引， 树高为 3 的树，最多搜索 3 次 IO

2 若为辅助索引，

辅助索引：

http://www.zhaochenxi.com/2015/07/03/mysql-innodb%E8%BE%85%E5%8A%A9%E7%B4%A2%E5%BC%95/

5.5 Cardinality （基数值）

5.5.1 什么是Cardinality

如果某个字段的取值范围很广， 几乎没有重复， 即属于高选择性， 此时使用 B+ 数索引最合适。通过 show index 结构中 Cardinality 来判断高选择性。

5.5.2 InnoDB 存储引擎的Cardinality统计 **

在 InnoDB 存储引擎中， Cardinality 统计信息的更新发生在两个操作中： Insert 和 update。 不可能每次 insert 和 update 更新 Cardinality 信息， 这样会增加系统负担， 对于大表统计， 时间成本太大。

Cardinality 信息的更新策略：

一 表中 1 / 16 的数据已经发生过变化

二 stat_modified_counter > 2 000 000 000

第一种策略为自从上次统计 Cardinality 信息后， 表中 1 / 16 的数据已经发生变化。

第二种情况考虑的是， 如果表中某一行数据频繁地进行更新操作， 这时表中的数据实际并没有增加， 实际发生变化的还是这一行数据。stat_modified_counter, 用来表示发生变化的次数， 当 stat_modified_counter 大于 2 000 000 000 时， 则同样需要更新 Cardinality 信息。

第三种 即为 analyze table 来手动更新。 

参数 innodb_stats_sample_pages 设置统计 Cardinality 时每次采样页的数量， 默认为 8.  参数 innodb_stats_method 用来判断如何对待索引的 NULL 值记录， 默认值为 nulls_equal, 表示 将 NULL 值记录视为相等的记录。 其有效值还有 nulls_unequal, nulls_ignored.

5.6 B+ 树索引的使用

5.6.1 不同应用中 B+ 数索引的使用。

5.6.2 联合索引 **

对于查询 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 值， 1,2,1,4,1,2 显然不是排序的。

联合索引的第二个好处是已经对第二个键值进行了排序处理。

5.6.3 覆盖索引（covering index）

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

5.6.4 优化器选择不使用索引的情况

5.6.5 索引提示

使用 use index 来告诉优化器可以选择某索引：

select * from t use index(a) where a=1 and b=2;

use index 只是告诉优化器可以选择该索引， 实际上优化器还是根据自己的判断进行选择。 通过 force index 来指定某个索引来完成查询。

5.6.6 Multi-Range Read 优化 （没看懂）

5.6.7 Index Condition Pushdown（ICP）优化 （没看懂）

5.7 哈希算法

5.7.1 哈希表

5.7.2 InnoDB 存储引擎中的哈希算法

5.7.3 自适应哈希索引

自适应哈希索引由 innodb 存储引擎自己控制的。 可以通过参数 Innodb_adaptive_hash_index 来禁用或启用该特性， 默认为开启。

5.8 全文检索

5.8.1 概述

从 Innodb 1.2.x 开始， innodb 开始支持全文检索， 支持 MyISAM 存储引擎的全部功能， 并且还支持其他的一些特性。

5.8.2 反向索引，（叫倒排索引， 不能很好表达 索引从 关键词 -> 文档的关系）

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

inverted file index ，表现形式为{单词， 单词所在文档的 ID}

full inverted index ,表现形式为 {单词， （单词所在文档的 ID， 在具体文档中的位置）}

相比之下， full inverted index 占用更多的空间， 但是更好地定位数据， 并扩充一些其他的搜索特性。

5.8.3 InnoDB 全文索引

问： Auxiliary  table ,在什么位置？

Innodb 从 1.2.x 开始支持全文检索， 采用 full inverted index 形式。

Auxiliary Table 是持久的表， 存放在磁盘上。 FTS Index Cache （全文检索索引缓存）， 用来提高全文检索的性能。

FTS Index Cache 是一个红黑数结构， 其根据（word , ilist） 进行排序。Innodb 存储引擎会批量对 Auxiliary Table 进行更新， 而不是每次插入后更新一次 Auxiliary Table.

设置 innodb_ft_aux_table 来观察 反向索引的 auxiliary table。 

set global innodb_ft_aux_table = "test/fts_a";

在 information_schema 架构的表 innodb_ft_index_table 得到表 fts_a 的分词信息。

参数 innodb_ft_cache_size 来控制 FTS Index Cache 的大小， 默认为 32M. 

在 Innodb 中， 与 word 进行映射的列 FTS_DOC_ID, 其类型必须是 BIGINT UNSIGNED NOT　NULL. 并且 INNODB会自动 在该列上加入一个名叫 FTS_DOC_ID_INDEX 的 unique index. 上述操作都由 INNODB 自己完成， 用户也可以在建表时自己添加 FTS_DOC_ID 以及相应的 Unique Index.

文档中分词插入操作实在事务提交时完成， 然而对于删除操作， 其在事务提交时， 不删除磁盘 Auxiliary Table 中的记录， 而只是删除 FTS Cache Index 中的记录。并将其保存在 DELETED auxiliary table 中。在 information_schema 库中的 innodb_ft_deleted 表中观察 FTS Document ID.

Innodb 提供了一种方式， 允许用户手工将已经删除的记录从索引中彻底删除， 该命令为 optimize table. 因为该命令还会进行一些其他操作， 如 Cardinality 的重新统计， 若用户仅对 反向索引进行操作， 可以通过参数 innodb_optimize_fulltext_only.

mysql>set global innodb_optimize_fulltext_only=1;

mysql>optimize table fts_a;

运行 optimize table 可将记录进行彻底的删除， 并且彻底删除的文档 ID 会记录到表 INNODB_FT_BEING_DELETED 中。

stopword 列, 表示该列表中的 word 不需要对其进行索引分词操作。在 数据库 information_schema 库中， 表明 innodb_ft_default_stopword, 默认有 36 个stopword. 此外用户可以通过 参数 innodb_ft_server_stopword_table 来定义 stopword 列表。如：

mysql>set global innodb_ft_server_stopword_table="test/user_stopword";

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

一 每张表只能有一个全文检索的索引。

二 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则。

三 不支持没有单词界定符（delimiter）的语言， 如 中文， 日文， 韩语等。

创建全文索引：

create fulltext index idx_fts on fts_a(body);

5.8.4 全文检索

1 Natural Lanuage (默认的全文检索查询模式)

select * from fts_a where match(body) against('Porridge');

select fts_doc_id, body, match(body) against('Porridge' in natural language mode) as relevance from fts_a;

用 explain 的显示中， type 显示 fulltext, 即表示使用全文检索的反向索引。

在 where 条件中使用 match 函数， 查询返回的结果是根据相关性（relevance）进行降序排列的， 即相关性最高的结果放在第一位。相关性依据以下四个条件：

一 word 是否在文档中出现。

二word 在文档中出现的次数。

三 word 在索引列中的数量。

四 多少个文档包含该 word。

参数 innodb_ft_min_token_size 和 innodb_ft_max_token_size 控制 innodb 存储引擎查询字符的长度。

2 Boolean

当使用该修饰符时， 查询字符串的前后字符会有特殊的含义， 如下例中 + 和 - 表示这个单词必须出现， 或者一定不存在。

select * from fts_a where  match(body) against('+please -hot' IN BOOLEAN MODE);

3 Query Expansion

mysql 还支持全文检索的扩展查询。 这种查询通常在查询的关键词太短， 用户需要 implied knowledge(隐含只是时)进行。该查询分两个阶段。

第一阶段：根据搜索的单词进行全文索引查询。

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

select * from articles where match(title, body) against('database' in natural language mode);

select * from articles where match(title, body) against('database' with query expansion);