Elaticsearch倒排索引

2021-09-21
ES倒排索引基本原理

索引(index)可以分为正序索引(Forward Indexes)和倒排索引(Inverted Index)两种。在关系型数据库中使用索引可以避免数据检索走全表扫描,将检索的时间复杂度从O(n)降到了O(logn)。例如,一本字典在开篇几页记录了每个字和所在页码的映射关系,当我们需要查阅某个字的时候不需要从每一页开始搜索,通过这个映射关系就能快速找到需要搜索的词项。假设现在有三个文档:doc1, doc2, doc3

doc1: Welcome to Hotel California

doc2: Welcome to the heaven

doc3: the dog is very cute

在关系型数据库中存储这三个文档并且建立索引,文档在数据库中的存储结构大概如下所示

Doc ID Doc Content
1 Welcome to Hotel California
2 Welcome to the heaven
3 the dog is very cute

通过建立这种文档id与文档内容的映射关系,在关系型数据库中可以快速查找到文档的具体位置,但是如果需要对文档中某些词项进行检索,则需要进行全表扫描,这个时候正序索引就失效了。

倒排索引的思想是建立文档中每个词项与文档的的映射关系,如下所示

Term Doc Id
welcome Doc1, Doc2
to Doc1,Doc2
the Doc2,Doc3
dog Doc3
heaven Doc2
.... ...

可以看出通过倒排索引,搜索任意一个词项都能快速定位到所在位置。通过上述例子可以看出顺序索引是文档ID与文档内容和单词的关联,倒排索引是单词到文档ID的映射关系。

倒排索引核心组成

倒排索引主要包括两部分:单词词典和倒排列表。

  • 单词词典:记录所有文档的单词,记录单词和倒排列表的关联关系
  • 倒排列表:记录单词与对应文档集合,由倒排索引项组成
    • 倒排索引项:主要由文档ID,词频TF(单词在文档中出现的次数,用于相关性评分),位置(Position,单词在文档中分词的位置,用于语句搜索) ,偏移(Offset,记录单词的开始结束位置,用于实现高亮显示)

Elaticsearch的JSON文档中每个字段都有自己的倒排索引,可以对文档中不需要搜索的字段不做索引,这样可以节省存储空间