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

emanuel · 2021-04-28 15:59:52 · 热度: 71

前言

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

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

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

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

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

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

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

倒排索引由两部分构成：

它的结构如下：

单词词典的特性：

单词词典的实现：

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

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

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

倒排列表特性：

倒排列表元素数据结构：((DocID;TF;<POS>))

其中：

有下面单个文档

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

则他们生成的倒排索引

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

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

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

为您推荐与 elasticsearch 相关的帖子：

0 个赞 0 收藏

暂无回复。

需要登录后方可回复, 如果你还没有账号请点击这里注册。