Elasticsearch中的倒排索引

frank_fun 发布于2019-07-16 15:42 / 3191人阅读

摘要：本篇文章主要介绍中的索引倒排索引分词在创建索引之前，会对文档中的字符串进行分词。简单来说，索引就是实现单词文档矩阵的具体数据结构，而倒排索引则是实现了这种数据结构的具体方式。

前言

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

分词

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

keyword类型的字符串不会被分词，搜索时全匹配查询

text类型的字符串会被分词，搜索时是包含查询

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

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

ik_max_word分词器: 最细粒度拆分，分词结果如下：

中华人民共和国

中华人民

中华

华人

人民共和国

人民

人

民

共和国

共和

和

国国

国歌

ik_smart分词器: 最粗粒度的拆分，分词结果如下：

中华人民共和国

国歌

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

单词-文档矩阵

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

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

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

倒排索引

倒排索引由两部分构成：

单词词典

倒排列表

它的结构如下：

单词词典

单词词典的特性：

是文档集合中所有单词的集合

它是保存索引的最小单位

其中记录着指向倒排列表的指针

单词词典的实现：

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

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

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

倒排列表

倒排列表特性：

记录出现过某个单词的文档列表

同时还记录单词在所有文档中的出现次数和偏移位置

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

其中：

DocID：出现某单词的文档ID

TF(Term Frequency)：单词在该文档中出现的次数

POS：单词在文档中的位置

举例

有下面单个文档

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

则他们生成的倒排索引

单词ID	单词	逆向文档频率	倒排列表(DocID;TF;)
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源码编译和Debug环境搭建

搜索引擎ElasticSearch的启动过程

Elasticsearch创建索引流程

Elasticsearch搜索过程详解

Elasticsearch搜索相关性排序算法详解

Elasticsearch中的倒排索引

ElasticSearch linux倒排索引 java倒排索引算法倒排序 java 集合倒排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/34524.html

elasticsearch学习笔记（一）——大白话告诉你什么是elasticsearch

摘要：对于倒排索引，也就是在全文检索时对每个词建立索引是采用倒排索引的方式。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。什么是elasticsearch？ wiki上面的解释是： Elasticsearch is a search engine based on the Lucene library. It provides a distributed, m...

darkbaby123 2019-07-16 15:32 评论0 收藏0
elasticsearch 概念（2）插件和使用

摘要：的精确值及倒排索引的数据可被广义的分为两种类型和。其次，为了完成此类域的搜索，倒排索引中的数据还需进行正规化为标准格式，才能评估其与用户搜索请求字符串的相似度。安装 ES依赖于JDK，使用Oracke JDK或OpenJDK均可。 JDK在不同平台的安装方式各异，具体方法这里不再介绍。ES的安装也非常容易，通常只需要简单修改其配置文件中的集群名称，并启动服务即可，这里不再赘述。 El...

Pines_Cheng 2019-07-16 15:04 评论0 收藏0
Elasticsearch-倒排索引

摘要：使用一种称为倒排索引的结构，它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的文档列表。但是，我们目前的倒排索引有一些问题和以独立的词条出现，然而用户可能认为它们是相同的词。 Elasticsearch 使用一种称为倒排索引的结构，它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的文档列...

ARGUS 2019-07-16 15:18 评论0 收藏0
Elasticsearch 实践一：初识

摘要：和使用了一个叫做倒排索引的结构来达到相同的目的。默认的，一个文档中的每一个属性都是被索引的有一个倒排索引和可搜索的。快速搭建测试环境 window下部署ELK（6.2.2系列）基础知识基本认知索引(index)：类似于传统关系数据库中的一个数据库; 复数词为 indices 或 indexes 类型(type):类似于传统关系数据库中的一个表文档(docuemnt):类似于传...

BlackFlagBin 2019-07-16 15:16 评论0 收藏0
elasticsearch学习笔记（三十一）——Elasticsearch doc value正排索

摘要：通过倒排索引锁定文档之后，看到每个的每个，然后进行排序，所谓的正排索引就是。对于而言，在建立索引的时候，一方面会建立倒排索引，以供搜索使用一方面会建立正排索引，也就是以供排序，聚合，过滤等使用。在我们搜索的时候，要依靠倒排索引，但是当我们排序的时候，需要依靠正排索引。通过倒排索引锁定文档document之后，看到每个document的每个field，然后进行排序，所谓的正排索引就是d...

antz 2019-07-16 15:36 评论0 收藏0