最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

Es的倒排索引实现原理_倒排索引表

XAMPP案例 admin 2694浏览 0评论

引出

倒排索引也叫反向索引,对应还有正向索引,先了解正向索引,再来看倒排索引就很容易理解了。 

正向索引
正向索引结构如下:
zzzzzt0000039

假设用户输入了“Word1”,那么就需要遍历所有的Doc,找到Doc中包含“Word1”的文档,根据打分模型进行打分,然后根据分数排名显示给用户;到这大家应该知道问题所在,上述例子如果在Doc文档数量很多的时候,非常浪费性能,怎么解决这个问题呢?下面来看倒排索引。

 

倒排索引

在实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。—-百度百科

倒排索引结构如下:

zzzzzt38

从倒排索引结构中可以看到,假设用户输入的是“Word1”,可以很快的找到哪些文档中包含“Word1”,相比较正向索引,效率提高非常多。

以上两图只是简单的比较了正向索引和倒排索引区别,下面着重介绍倒排索引的核心概念

在Es中,一个分片是一个Lucene索引,也就是说Es的内部核心就是Lucene,那么Lucene是怎么实现倒排索引的呢?

Lucene的倒排索引由一个term词典表+倒排列表组成

词典表
用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。
对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构和树形词典结构。

 

倒排列表
用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词,每个文档会记录文档编号(DocID),单词在这个文档中出现的次数(TF)及单词在文档中哪些位置出现过等信息,这样与一个文档相关的信息被称做倒排索引项(Posting),包含这个单词的一系列倒排索引项形成了列表结构,这就是某个单词对应的倒排列表
如图:

zzzzzt038

倒排索引表

单词ID 单词 文档频率 倒排列表
1 奥迪 4 倒排索引项1,倒排索引项2,倒排索引项3 ,倒排索引项4
2 汽车 3 倒排索引项1,倒排索引项2,倒排索引项3
3 轮胎 2 倒排索引项1,倒排索引项2
4 内饰 2 倒排索引项1,倒排索引项2

转载请注明:XAMPP中文组官网 » Es的倒排索引实现原理_倒排索引表

您必须 登录 才能发表评论!