Juconcurrent 学而不思则罔,思而不学则殆。

Elasticsearch学习笔记(06) - 倒排索引简介


Elasticsearch的核心是基于倒排索引。因此,我们有必要了解一下倒排索引算法。

简单的例子

既然有倒排索引,那么也一定有正排索引。

我们以一本书为例,每本书都有目录页,目录页里面的每条记录都会存储内容的页码,我们可以很快地通过页码查找到具体的文档内容。

假如,我们想根据某些关键词,查找他们在哪些文档中出现了,仅仅使用目录页可能没办法实现。而有的书籍有索引页,索引页记录了文档关键词到文档页码的关联关系。这儿的索引页就是倒排索引。

我们总结一下:

  • 目录页 - 正排索引,文章id到文档内容和单词的关联。
  • 索引页 - 倒排索引,单词到文档内容的关联。

正排索引 倒排索引

正排和倒排的类比

假如有3本书,每本书的id和内容都不同,如下所示:

id Document
1 ElasticSearch Action
2 Mastering ElasticSearch
3 ElasticSearch Server

我们使用倒排索引,可建立如下结构:

Term Count DocumentId:Position
ElasticSearch 3 1:0 2:1 3:0
Action 1 1:1
Mastering 1 2:0
Server 1 3:1

其实,倒排索引由以下内容组成

  1. 单词词典 - 所有文档的单词,单词到倒排列表的关联关系
    • 单词词典可能会比较大,我们可针对它建立单词索引。常使用B+Tree或hash表来实现,以提高维护和查询的性能
  2. 倒排列表 - 单词和对应的文档组合,由倒排索引项组成。每个倒排索引项包含以下内容:
    • 文档id
    • TF,词频 - 单词在文档中出现的次数。可用于相关性打分
    • Position,位置 - 单词在文档中分词的位置。可用于语句搜索
    • Offset,偏移量 - 单词的开始位置。可用于高亮显示

以上面的例子为例,我们看一下单词ElasticSearch的倒排列表是怎样的。

id TF Position Offset
1 1 0 <0,13>
2 1 1 <10,23>
3 1 0 <0,13>

Elasticsearch中的倒排索引

  1. Elasticsearch的json文档中,每个字段都可以加入到倒排索引
  2. 可指定某些字段不做索引
    • 优点:节省存储空间
    • 缺点:字段无法被搜索

总结

我们简单地对倒排索引进行了说明,且未深入将Elasticsearch里面的各种算法。希望通过这篇文章,让读者对于倒排索引有一个入门级的了解。


Content