倒排索引

正排索引与倒排索引

以图书为例：

• 正排索引——目录页
• 倒排索引——索引页（按关键词找到对应页/对应文章）

搜索引擎：

• 正排索引——文档id到文档内容和单词的关联
• 倒排索引——单词到文档id的关系

正排索引与倒排索引的简单结构示意：

正排索引：

文档ID	文档内容
1	Mastering ElasticSearch
2	ElasticSearch Server
3	ElasticSearch Essentials

倒排索引：

Term	Count	Document ID:Position
ElasticSearch	3	1:1,2:0,3:0
Mastering	1	1:0
Server	1	2:1
Essentials	1	3:1

倒排索引的核心组成

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

ElasticSearch的倒排索引

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