全文检索

一.概述

1.1 全文检索的概念

• 全文检索就是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。
• 它可以根据需要获得全文中有关文章，节，段，句，词等信息，也可以进行统计和分析。、
• MySQL中InnoDB存储引擎之前是不支持全文检索的，要使用全文检索的话只能使用MySIAM存储引擎，但是在1.2.x版本开始就支持全文检索了

1.2 问题的引入

• MySql中的InnoDB存储引擎中对于表索引的管理是采用B+树结构的，所以我们可以通过索引字段的前缀进行查找。例如：

  select * from blog where content like ‘xxx%’

• 上述sql语句可以在blog中查找内容以xxx开头的文章，并且只要content添加了B+树索引，那么就可以利用索引快速的进行查询。

问题：

• 但是在实际的用户查询操作中，上述查询并不符合用户的要求。因为在大多数的情况下，用户需要查询的是包含xxx的文章，而不是以xxx开头的文章。例如：

  select * from blog where content like ‘%xxx%’

• 而实际上，这种查询并不是B+树索引所能很好的完成的工作。所以需要使用其他的技术。

二. 全文检索的一般实现——倒排索引

• 全文检索通常会使用倒排索引实现。倒排索引同B+树索引一样，也是一种索引结构。
• 只是数据结构肯定是不同的，它通过一个辅助表，这个辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。这通常采用关联数组实现，有两种表现形式：
  1）inverted file index：{单词，单词所在的文档ID}
  2）full inverted index：{单词，{单词所在的文档ID，在具体文档中的位置} }
  举例如下：表T存储的内容如表所示

全文检索表

• DocumentId表示进行全文检索文档的ID，Text表示存储的内容，用户需要对存储的这些文档进行全文检索。例如查找出现过some单词的文档id，又或者查找单个文档中出现过两个some单词的文档id等

inverted file index的关联数组：

full inverted index的关联数组：

• 可以看到code存在于文档1中，单词days存在于文档3和文档6中。有了这个辅助表，就可以很简单的进行全文查询了，直接根据Documents得到包含查询关键字的文档，对于inverted file index，其仅存于文档id，而对于full inverted index，还可以获取到在相应文档中的位置。

总结：

• 倒排索引其实就是根据一个辅助表，表中存储了每个单词出现的文档id，甚至存储其在文档出现的位置。通过这个辅助表进行全文检索。

三. InnoDB全文检索

3.1 概述

• InnoDB存储引擎支持全文索引采用full inverted index的方式，将（DocumentId，Position）视为一个“ilist” 。
• 因此在全文检索的表中，一共有两列，一列是word字段，另一个是“ilist”，并且在word字段上设有索引。
• 此外，由于在ilist字段中存放了Poistion信息，所以可以进行Proximity Sreach，而MyISAM存储引擎不支持该特性。

3.2 实现

3.2.1 辅助表结构

• 之前所说，倒排索引需要将word存放到一张辅助表中，这个表称为Auxiliary Table（辅助表）。
• 在InnoDB存储引擎中，为了提高全文检索的并行性能，共有6张Auxiliary Table，目前每张表会根据word的Latin编码进行分区。

3.2.2 全文检索索引缓存

• Auxiliary Table是持久的表，存放在磁盘上。然而InnoDB为了提高全文检索的性能，引入了全文检索索引缓存（FTS Index Cache）。 其实就是增加了一个缓冲！每次先修改缓冲，再刷新回磁盘。
• FTS Index Cache 是一个红黑树结构，根据（word，ilist）进行排序。
• 也就是说，当我们进行插入操作的时候，我们的数据已经更新了磁盘上的表，但是有可能全文索引的更新还没有刷新回磁盘，仅仅是在缓冲池中修改了。InnoDB会批量的对Auxiliary Table进行更新。这种机制类似于插入缓冲！

3.2.3 FTS Document ID

• FTS Document ID是另外一个重要的概念，我们刚刚其实有提到，为了支持全文索引，必须有一个列与word进行映射，也就是为每一个word也添加索引。这一列被命名为FTS_DOC_ID，这是InnoDB存储引擎自动完成的。

3.2.4 stopword列表

• 该列表中会存储不需要对其索引分词操作的单词。例如 the 这个单词由于其不具有具体的意义，所以将其视为 stopword。

3.3 分词的插入和删除操作

• 文档中分词的插入操作是在事务提交时完成的，但是对于删除操作，其事务提交时，不会删除 Auxiliary Table中的记录，而是只删除FTS Index Cache中的记录。对于Auxiliary Table中被删除的记录，InnoDB存储引擎会记录其FTS Document ID，将其保存在DELETED auxiliary中。

四. innoDB存储引擎全文检索的限制

• 每张表只能由一个全文检索的索引：也就是说只能添加一个全文检索的索引，当然可以联合索引。
• 由多列组合而成的全文检索的索引必须使用相同的字符集与排序规则
• 不支持没有单词界定符的语言，如中文，日语，韩语等