文章目录
  1. 哈希索引
  2. 全文检索

哈希索引

InnoDB存储引擎是使用哈希算法对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列。被除数K=sapce_id<<20+sapce_id+offset。

全文检索

全文检索使用倒排索引实现，它在辅助表中存储单词与单词自身在一个或多个文档中所在位置的映射，这使用关联数组实现，存在两种表现形式：

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

存放这些映射关系的表称为辅助表(Auxiliary Table)，与之相对应的内存中的镜像为全文检索索引缓存(FTS Index Cache)。

全文检索索引缓存是一个红黑树结构，当对全文检索进行查询时，辅助表先将全文检索索引缓存中对应的word字段合并到辅助表

在InnoDB存储引擎中，必须有一列与word进行映射，该列被命名为FTS_DOC_ID，其类型必须为BIGINT UNSIGNED NOT NULL。

word的插入在事务提交时完成，而对于删除操作，在事务提交时，InnoDB存储引擎并不会删除辅助表中的记录，而只是删除全文检索索引缓存中的记录。对这些从全文检索索引缓存中删除的记录，InnoDB存储引擎会记录其”单词所在文档的ID”并将其保存到DELETED辅助表中，

这样，每次删除记录时，不但不会将辅助表中的记录删除，还会写入DELETED辅助表中，为此，InnoDB存储引擎提供了OPTIMIZE TABLE命令将已经删除的记录从索引中彻底删除。