Elasticsearch源码解读六:ES中的倒排索引

2019-05-10 Lanffy 更多博文 » 博客 » GitHub »

ElasticSearch

原文链接 https://lanffy.github.io/2019/05/10/Inverted-Index-In-Elasticsearch
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。



前言

Elasticsearch创建索引流程一文中,介绍了ES创建索引的流程。再流程中是调用Lucene的接口来创建索引的。本篇文章主要介绍ES中的索引——倒排索引

分词

在创建索引之前,会对文档中的字符串进行分词。ES中字符串有两种类型,keyword和text。

  • keyword类型的字符串不会被分词,搜索时全匹配查询
  • text类型的字符串会被分词,搜索时是包含查询

不同的分词器对相同字符串分词的结果大有不同,选择不同的分词器对索引的创建有很大的影响

如拆分“中华人民共和国国歌”

  1. ik_max_word分词器: 最细粒度拆分,分词结果如下:
    • 中华人民共和国
    • 中华人民
    • 中华
    • 华人
    • 人民共和国
    • 人民
    • 共和国
    • 共和
    • 国国
    • 国歌
  2. ik_smart分词器: 最粗粒度的拆分,分词结果如下:
    • 中华人民共和国
    • 国歌

可见,再ES中创建索引,选择合适的分词器是很重要的。

单词-文档矩阵

- 单词1 单词2 单词3 单词4
文档1
文档2
文档3
文档4

该矩阵是表达单词和文档两者之间包含关系的概念模型。 从横向看,每行代表文档包含了哪些单词,比如文档1包含了单词1和单词3,而不包含其它单词。 从纵向看,每列代表了某个单词存在于哪些文档。比如单词1在文档1和文档4中出现过。

简单来说,索引就是实现“单词-文档矩阵”的具体数据结构,而倒排索引则是实现了这种数据结构的具体方式。

倒排索引

倒排索引由两部分构成:

  • 单词词典
  • 倒排列表

它的结构如下: -w462

单词词典

单词词典的特性:

  1. 是文档集合中所有单词的集合
  2. 它是保存索引的最小单位
  3. 其中记录着指向倒排列表的指针

单词词典的实现: -w477

单词词典有两种数据结构实现:B+树Hash表

B+树和Mysql索引结构中主键索引数据结构一样,这里就不再介绍了

哈希表的key是单词的hash值,值是单词的链表,因为hash算法会有冲突的情况发生,所以这里的值是一个集合,里面保存着相同hash值得单词以及改词指向倒排列表的指针

倒排列表

倒排列表特性:

  1. 记录出现过某个单词的文档列表
  2. 同时还记录单词在所有文档中的出现次数和偏移位置

倒排列表元素数据结构:$$(DocID;TF;)$$

其中:

  • DocID:出现某单词的文档ID
  • TF(Term Frequency):单词在该文档中出现的次数
  • POS:单词在文档中的位置

举例

有下面单个文档

- 内容
文档1 百度的年度目标
文档2 AI技术生态部的年度目标
文档3 AI市场的年度目标

则他们生成的倒排索引

单词ID 单词 逆向文档频率 倒排列表(DocID;TF;<POS>)
1 目标 3 (1;1;),(2;1;),(3;1;)
2 年度 3 (1;1;),(2;1;),(3;1;)
3 AI 2 (2;1;),(3;1;)
4 技术 1 (2;1;)
5 生态 1 (2;1;)
6 市场 1 (3;1;)

比如单词“年度”,单词ID为2,在三个文档中出现过,所以逆向文档频率为3,同时倒排索引中的元素也有三个:(1;1;<2>),(2;1;<4>),(3;1;<3>)。拿第一个元素(1;1;<2>)进行说明,他表示“年度”再文档ID为1的文档中出现过1次,出现的位置是第二个单词

倒排索引的搜索过程

直到了倒排索引的内部结构之后,就能很好理解倒排索引的搜索过程了,其内部搜索过程如下图所示:

系列文章

  1. ElasticSearch源码解读一:源码编译和Debug环境搭建
  2. ElasticSearch源码解读二:启动过程详解
  3. Elasticsearch源码解读三:创建索引过程详解
  4. Elasticsearch源码解读四:搜索过程详解
  5. Elasticsearch源码解读五:搜索相关性排序算法详解
  6. Elasticsearch源码解读六:ES中的倒排索引
  7. Elasticsearch源码解读七:常见用法手册