# 索引概述 - B+ 树索引 - 全文索引 - 哈希索引 # 数据结构与算法 ### 二分查找法 折半查找法 ### 二叉查找树和平衡二叉树  # B+ 树 ### 插入  1. 插入 28  2. 插入 70 根据中间的值 60 来拆分叶子节点  3. 插入 95  ### 删除  - 删除 70  - 删除 25 将 25 的右兄弟节点的 28 跟新到 Page Index 中  - 删除 60 Fill Factor 小于 50%，需要做合并操作  # B+ 树索引 查找某一键值的行记录时最多只需要 2 到 4 次 I/O（0.02s ~ 0.04s） ### 聚集索引 按照每张表的主键构造一个 B+ 树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。 - 页通过双向链表链接，页按照主键的顺序排序 - 每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。 - 对于排序查找和范围查找速度非常快 ### 辅助索引 当通过辅助索引来寻找数据时，InnoDB 存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。 ### B+ 树索引的分裂 - 若插入是随机的，则取页的中间记录作为分裂点的记录 - 若往同一方向进行插入的记录数量为 5，并且目前已经定位到的记录之后还有 3 条记录，则分裂点的记录为定位到的记录后的第 3 条记录，否则分裂点记录就是带插入的记录 ### B+ 树 Online DDL 在执行创建或删除操作的同时，将 INSERT、UPDATE、DELETE 这类 DML 操作日志写入到一个缓冲中。待完成索引创建后再将重做应用到表上。 - 辅助索引的创建与删除 - 改编自增长值 - 添加或删除外键约束 - 列的重命名 参数： - innodb_online_alter_log_max_size 缓冲大小由该参数控制，默认 128 MB。 # Cardinality 值 Cardinality/n_rows_in_table 应尽可能地接近 1，如果非常小，那么用户需要考虑是否还有必要创建这个索引。 激活： - 表中 1/16 的数据已发生过变化 - stat_modified_counter > 2000000000 - ANALYZE TABLE - SHOW TABLE STATUS - SHOW INDEX - SELECT INFORMATION_SCHEMA.TABLES/STATISTICS 采样： - 取得 B+ 树索引中叶子节点的数量，记为 A - 随机取得 B+ 树索引中的 8 个叶子节点。统计每个页不同记录的个数，即为 P1,P2,...,P8 - 根据采样信息给出 Cardinality 的预估值：Cardinality = (P1 + P2 + ... + P8) * A / 8 查看 ``` SHOW INDEX FROM <index_name>; ``` 参数 - innod_stats_sample_pages：设置统计采样页的数量，默认为 8 - innodb_stats_method：定义如何对待索引中出现的 NULL 值记录 - nulls_equal(默认)：将 NULL 值记录视为相等的记录 - nulls_unequal：将 NULL 值记录视为不同的记录 - nulls_ignored：忽略 NULL 值记录 - innodb_stats_persistent(默认：OFF)：是否将命令 ANALYZE TABLE 计算得到的 Cardinality 值存放到磁盘上。也可以通过命令 CREATE TABLE 和 ALTER TABLE 的选项 STATS_PERSISTENT 来对每张表进行控制 - innodb_stats_on_metadata(默认：OFF)：当通过命令 SHOW TABLE STATUS、SHOW INDEX 及访问 INFORMATION_SCHEMA 架构下的表 TABLES 和 STATISTICS 时，是否需要重新计算索引的 Cardinality 值 - innodb_stats_persistent_sample_pages(默认：20)：表示 ANALYZE TABLE 更新 Cardinality 值时每次采样页的数量。 - innodb_stats_transient_sample_pages(默认：8)：取代 innod_stats_sample_pages # B+ 树索引的使用 ### 优化器选择 - 索引覆盖（一般是20% 左右） ### INDEX HINT - FORCE INDEX(<index_name>) - USE INDEX(<index_name>) ### Multi-Range Read 优化 适用于 range、ref、eq_ref 类型的查询 优点： - MRR 使数据访问变的较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。 - 减少缓冲池中页被替换的次数。 - 批量处理对键值的查询操作。 工作原理 - 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。 - 将缓存中的键值根据 RowID 进行排序。 - 根据 RowID 的排序顺序来访问实际的数据文件。 参数 - optimizer_switch： - mrr=on,mrr_cost_based=off：将 MRR 优化总是设为开启状态 - read_rnd_buffer_size：控制键值的缓冲区大小，当当大于该值时，则执行器对已经缓存的数据根据 RowID 进行排序，并通过 RowID 来取得行数据。该值默认为 256K。 ### Index Condition Pushdown（ICP）优化 - 在取出索引的同时，判断是否可以进行 WHERE 条件的过滤。 - 支持 range、ref、eq_ref、ref_or_null 类型的查询 # 哈希算法 时间复杂度为O(1) ### 哈希表 - 哈希技术寻址 在哈希方式下，该元素处于 h(k) 中，即利用哈希函数 h，根据关键字 k 计算出槽的位置。函数 h 将关键字域 U 映射到哈希表 T[0...m-1] 的槽位上。  - 链接法 槽 j 中有一个指针，它指向由所有散列到 j 的元素构成的链表的头；如果不存在这样的元素，则 j 中为 NULL。  - 哈希函数的除法散列法 将关键字转换成自然数，然后通过除法散列（k除以m的余数），将关键字 k 映射到 m 个槽的某一个去：h(k) = k mod m， - m 的取值为略大于 2 倍的缓冲池页数量的质数。（假设 innodb_buffer_pool_size = 10M，则共有 640 个 16KB 的页，则需要分配 640 * 2 = 1280 个槽，因为需要取比 1280 略大的一个质数，应该是 1399） - 自然数：InnoDB 存储引擎将 space_id 左移 20 位，然后加上这个 space_id 和 offset，即关键字 k = space_id << 20 + space_id + offset # 全文索引 ### 概述 是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。 ### 倒排索引 全文检索通常使用倒排索引来实现。它在辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。 - inverted file index：表现形式为{单词，单词所在的文档的 ID} - full inverted index：表现形式为{单词，(单词所在文档的 ID，在具体文档中的位置)} 例如：  - inverted file index  - full inverted index  ### InnoDB 全文检索 - 需要将 word 存放到一张表中，这个标称为 Auxiliary Table (辅助表)。在 InnoDB 存储引擎中，为了提高全文检索的并行性能，共有 6 张 Auxiliary Table，每张表根据 word 的 Latin 编码进行分区 - 全文检索索引缓存(FTS Index Cache) 是一个平衡二叉树结构，其根据 (word, ilist) 进行排序。 - 查询时，Auxiliary Table 首先会将在 FTS Index Cache 中对应的 word 字段合并到 Auxiliary Table 中，然后再进行查询。 - 为了支持全文检索，文本表必须有一个命名为 FTS_DOC_ID 的列，起类型必须是 BIGINT UNSIGNED NOT NULL，并且 InnoDB 存储引擎自动会在该列上加入一个名为 FTS_DOC_ID_INDEX 的 Unique Index。 - 文档中分词的插入操作是在事务提交时完成，对于删除操作，其在事务提交时，不删除磁盘 Auxiliary Table 中的记录，而只是删除 FTS Cache Index 中的记录。对于 Auxiliary Table 中被删除的记录，InnoDB 存储引擎会记录其 FTS Document ID，并将其保存在 DELETED auxiliary table 中。在设置参数 innodb_ft_aux_table 后，用户同样可以访问 information_schema 架构下的表 INNODB_FT_DELETED 来观察删除的 FTS Docement ID。 - 如果需要将已经删除的记录从索引中彻底删除，该命令就是 OPTIMIZE TABLE。除了删除记录，还会对 Cardinality 重新统计 限制 - 每张表只能有一个全文检索的索引 - 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则。 - 不支持没有单词界定符(delimiter)的语言，如中文、日文、韩文等。 查看 1. 查看分词信息 ```mysql SET GLOBAL innodb_ft_aux_table='test/fts_a'; SELECT * FROM INFORMATION_SCHEMA.innodb_ft_index_table; -- 获取 fts_a 中的分词信息 ``` 2. 删除某文档信息 ```mysql DELETE FROM test.fts_a WHERE FTS_DOC_ID=7; 或 OPTIMIZE TABLE test.fts_a; ``` 3. 查看删除文档 ID 插入 DELETED 的信息 ```mysql SELECT * FROM INNODB_FT_DELETED; ``` 4. 查看 stopword 表 ```mysql SET GLOBAL innodb_ft_server_stopword_table = "test/user_stopword" ``` 参数 - innodb_ft_cache_size：FTS Index Cache 大小，默认 32M。当该缓存满时，会将其中的 (word, ilist) 分词信息同步到磁盘的 Auxiliary Table 中 - innodb_optimize_fulltext_only：OPTIMIZE TABLE 仅对索引中记录进行操作，不重新统计 Cardinality 等信息 - innodb_ft_num_word_optimize：限制每次实际删除的分词数量，默认值为 2000。 - innodb_ft_aux_table：查看表 xx 中的分词信息 ``` SET GLOBAL innodb_ft_aux_table='test/fts_a'; SELECT * FROM INFORMATION_SCHEMA.innodb_ft_index_table; -- 获取 fts_a 中的分词信息 ``` - innodb_ft_server_stopword_table：查看表 xx 中不需要对其进行索引分词操作的词 ### 全文检索 全文检索查询语法： ```mysql 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 } ``` - MATCH：指定了需要被查询的列 - AGAINST：指定了使用何种方法去进行查询。 ##### NATURAL LANGUAGE NATURAL LANGUAGE(默认)：表示查询带有指定的 word 文档。 ```mysql -- 不走全文检索 SELECT * FROM fts_a WHERE body LIKE '%Pease%'; -- 检索语句 SELECT * FROM fts_a WHERE MATCH(body) AGAINST ('Porridge' IN NATURAL LANGUAGE MODE); -- 简写 SELECT * FROM fts_a WHERE MATCH(body) AGAINST ('Porridge') ``` 查询结果集根据相关性排序，最高的放第一位 - word 是否在文档中出现 - word 在文档中出现的次数 - word 在索引列中的数量 - 多少个文档包含该 word ```mysql -- 查看相关性 SELECT fts_doc_id, body, MATCH(body) AGAINST ('Porridge' IN NATURAL LANGUAGE MODE) AS Relevance FROM fts_a ``` 全文索引因素 - 查询的 word 在 stopword 列中，忽略该字符串的查询 - 查询的 word 的字符串长度是否在区间 [innodb_ft_min_token_size(默认 3), innodb_ft_max_token_size(默认 84)] 内 ##### BOOLEAN ```mysql SELECT * FROM fts_a WHERE MATCH(body) -- 有字符串 Pease 和 hot 的文档 AGAINST ('+Pease +hot' IN BOOLEAN MODE); -- 有字符串 Pease 但没有 hot 的文档 AGAINST ('+Pease -hot' IN BOOLEAN MODE); -- 有字符串 Pease 或 hot 的文档 AGAINST ('Pease hot' IN BOOLEAN MODE); -- 字符串 Pease 和 pot 之间的距离需在 30 字节内 AGAINST ('"Pease pot"@30' IN BOOLEAN MODE) ``` - +：表示该 word 必须存在。 - -：表示该 word 必须被排除。 - (no operator)：表示该 word 可选，但是如果出现，其相关性会更高 - @distance：表示查询的多个单词之间的距离是否在 distance 之内，distance 的岗位是字节。 - \>：表示出现该单词时增加相关性 - \<：表示出现该单词时降低相关性 - ~：表示允许出现该单词，但是出现时相关性为负 - \*：表示以该单词开头的单词，如 lik\*，表示可以是 lik、like，又或者 likes。 - ""：表示短语 ##### QUERY EXPANSION ```mysql WITH EXPANSION IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION ``` - 第一阶段：根据搜索的单词进行全文索引查询。 - 第二阶段：根据第一阶段产生的分词在进行一次全文检索的查询 示例 ```mysql -- 创建表 CREATE TABLE articles ( id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY, title VARCHAR(2000), body TEXT, FULLTEXT (title, body) ) ENGINE=InnoDB; -- 插入数据 INSERT INTO articles (title, body) VALUES ('MySQL Tutorial','DBMS stands for DataBase ...'), ('How To Use MySQL Well','After you went through a ...'), ('Optimizing MySQL','In this tutorial we will show ...'), ('1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'), ('MySQL vs. YourSQL','In the following database comparison ...'), ('MySQL Security','When configured properly, MySQL ...'), ('Tuning DB2','For IBM database ...'), ('IBM History','DB2 history for IBM ...'); -- 查询 SELECT * FROM articles WHERE MATCH(title, body) AGAINST('database' WITH QUERY EXPANSION); ```