倒排索引

倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。

图书和搜索引擎对比参考

• 图书
  • 正排索引：目录页
  • 倒排索引：索引页
• 搜索引擎
  • 正排索引：文档id到文档内容和单词的关联
  • 倒排索引：单词到文档Id的关系

例子：
左侧正排索引，右侧倒排索引

• 把左侧文档内容中的书名分成独立的单词，得到右侧Term中独立的单词
• count记录每个单词在文档中出现的频次
• DocumentId：Position，记录每个单词对应文档的id及文档中出现的位置

倒排索引核心组成

• 倒排索引包含两个部分
  • 单词词典（Term Dictionary），记录所有文档的单词，记录单词到倒排列表的关联关系
    • 单词词典一般比较大，可以通过B+树或哈希拉链法实现，以满足高性能的插入与查询
  • 倒排列表（Posting List）：记录单词对应的文档，由倒排索引项组成
    • 倒排索引项
      • 文档Id（Doc Id）
      • 词频 TF：该单词在文档中出现的次数，用于相关姓评分
      • 位置（Position）：单词在文档中分词的位置。用于语句搜索（phrase query）
      • 偏移（Offset）：记录单词的开始结束位置，实现高亮显示

例子：ElasticSearch 倒排列表（Posting List）

ElasticSearch的倒排索引

• ElasticSearch的JSON文档中每个字段，都有自己的倒排索引
• Mappings中可以指定对某些字段不做索引
  • 优点：节省存储空间
  • 缺点：字段无法被搜索