倒排索引 订阅
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。 展开全文
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。
信息
特殊要求
海量数据
构建方法
使用hash去重单词term
中文名
倒排索引
外文名
inverted index
倒排索引概述
在关系数据库系统里,索引是检索数据最有效率的方式,。但对于搜索引擎,它并不能满足其特殊要求:1)海量数据:搜索引擎面对的是海量数据,像Google,百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ,面对如此海量数据 ,使得数据库系统很难有效的管理。2)数据操作简单:搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、 删、 改、 查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 ,搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。 [1] 
收起全文
精华内容
下载资源
问答
  • 倒排索引
    2022-01-24 11:09:10

    索引

    这两个词中都包含了一个词,索引

    索引是一种为了加快数据库查询的一种数据结构,是由一系列的存储在电脑磁盘上面的索引项构成的。

    通过一些标识,来进行快速的查找数据

    实际上,索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录。

    上面都在说使用索引的好处,但过多的使用索引将会造成滥用。因此索引也会有它的缺点:虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE和DELETE。因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件。

    建立索引会占用磁盘空间的索引文件。

    正排索引

    概念

    正排表是以文档的ID为key,表中记录文档中每个关键字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。

    特点

    这种组织方法在建立索引的时候结构比较简单,建立比较方便且易于维护;

    因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。

    若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。

    但是在查询的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。

    存储演示

    商品1 -> [(关键词1,出现3次,位置为1,3,5), (关键词2,出现2次,位置为2,6), (关键词4,出现1次,位置为10), …]
    商品2 -> [(关键词1,出现1次,位置为1), (关键词3,出现4次,位置为2,4,7,9), …]
    商品3 -> [(关键词2,出现2次,位置为1,4), (关键词4,出现3次,位置为2,7,10), …]
    商品4 -> [(关键词5,出现1次,位置为1), (关键词6,出现1次,位置为2), …]

    img

    倒排索引

    概念

    倒排表以字或词为关键字进行索引,表中关键字所对应的记录表项记录了出现这个字或词的所有文档,

    一个表项就是一个字表段,它记录该文档的ID和字符在该文档中出现的位置情况。

    特点

    每个字或词对应的文档数量在动态变化,所以倒排表的建立和维护都较为复杂,

    但是在查询的时候由于可以一次得到查询关键字所对应的所有文档,所以效率高于正排表。

    在全文检索中,检索的快速响应是一个最为关键的性能,而索引建立由于在后台进行,尽管效率相对低一些,但不会影响整个搜索引擎的效率。

    存储演示

    关键词1 -> [商品1,商品2]
    关键词2 -> [商品1,商品3]
    关键词3 -> [商品2]
    关键词4 -> [商品1,商品3]
    关键词5 -> [商品4]
    关键词6 -> [商品4]

    什么是倒排索引与正向索引

    总结

    正排索引

    一般是通过key,去找value。例如:当用户在主页上搜索关键词“SEO”时,假设只存在正向索引(forward index),那么就需要扫描索引库中的所有文档,找出所有包含关键词“SEO”的文档。

    倒排索引

    从词的关键字,去找文档。例如:在**搜索引擎 **中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎索引库中,关键词也已经转换为关键词ID)。例如“文档1”经过分词,提取了20个关键词,每个关键词都会记录它在文档中的出现次数和出现位置。

    更多相关内容
  • Elasticsearch之倒排索引

    2021-01-20 12:12:43
    倒排索引 Elasticsearch通过倒排索引的数据结构来实现全文搜索 在关系数据库系统里,索引是检索数据最有效率的方式。但对于搜索引擎,它并不能满足其特殊要求,比如海量数据下比如百度或者谷歌要搜索百亿级的网页,...
  • 倒排索引java实现

    2020-10-02 01:00:14
    倒排索引的java实现,对于已经转化为txt的网页文档使用IK分词,然后建索引 倒排索引的java实现,对于已经转化为txt的网页文档使用IK分词,然后建索引
  • 读取 10 个 .txt 文本构建序列表,排序并输出排序列表。 输入两个词,空格隔开,搜索,输出两个词的公有文本。
  • 今天小编就为大家分享一篇python 实现倒排索引的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 使用倒排索引实现的简单的搜索引擎demo 能对莎士比亚全集的文本进行搜索,并显示该词语所在的篇目和所在句子 源代码及说明也可在github获取 https://github.com/yunwei37/myClassNotes
  • MapReduce程序 完整实验报告 和 jar包 和简单实验数据
  • 基于hadoop集群系统(也可以在伪分布式系统上运行)系统使用Java编写的倒排索引实现,具有使用停词表功能,使用正则表达式选择规范的单词。代码重构了setup(),map(),combiner(),partitation()和reducer()函数,...
  • 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。这篇文章主要介绍了Python倒排索引之查找...
  • BSBI倒排索引算法

    2018-10-29 11:12:03
    python3.6实现中文语料文本的BSBI算法(倒排索引)索引程序实现。包括中文文本分词,停用词表。
  • 利用倒排索引和向量空间模型实现的信息检索系统。 完成工作: 带位置信息的倒排索引 转化空间模型 TOP K查询 BOOL查询 初步查询 拼写矫正 名词查询 拼写矫正(以下) 运行 环境要求:python3 在初次运行程序前请下载...
  • Boolean Retrival(布尔检索) and Posting Lists(倒排索引表)问题描述利用文档和词项的布尔关系建立倒排索引表,根据倒排索引表进行布尔表达式查询.这里只实现AND操作.布尔检索布尔检索模型React了文档和词项集合的...
  • 一个使用倒排索引和向量空间模型的简单信息检索项目。 1)源代码只是一个python文件ir.py。 2)代码是用Python 2.7编写的。 3)代码中的query_file和base_dir变量要分别设置为query文件和blogs目录。 4)查询...
  • 基于倒排索引的可验证混淆关键字密文检索方案
  • C++倒排索引

    2021-03-30 21:00:16
    读入文本集,建立倒排索引,内含有的TXT文本可以替换,源代码可以直接运行 读入文本集,建立倒排索引,内含有的TXT文本可以替换,源代码可以直接运行
  • 运行说明:在linux终端输入 $ hadoop jar test-1.0-SNAPSHOT.jar WordCount /input/* /MyOutput1/ 后两个参数是hdfs上面【输入】的文本文件目录和【输出】目录。 记得清空输出目录。
  • C语言实现的倒排索引算法(含全部源码) C语言实现的倒排索引算法(含全部源码) C语言实现的倒排索引算法(含全部源码) C语言实现的倒排索引算法(含全部源码)
  • hadoop hadoop课程主页 这里是我的一些hadoop程序 最基本的wordcount,倒排索引,还有一个是对倒排索引的排序。数据用的是hadoop课程上给的武侠小说的数据。
  • 倒排索引引擎

    2017-05-24 08:12:37
    数据库索引
  • 最近正在学习Hadoop的知识,一步步来,这里先给大家分享一篇关于Hadoop编程基于MR程序实现倒排索引的文章,还是不错的,供需要的朋友参考。
  • 算法篇--倒排索引

    千次阅读 2021-08-01 17:28:39
      见其名知其意,有倒排索引,对应肯定,有正向索引。正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。   在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词...

    一、前言

      见其名知其意,有倒排索引,对应的肯定就有正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。对于倒排索引的快速形象的了解可以参考这篇文章:搜索引擎概述之倒排索引

      在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎索引库中,关键词也已经转换为关键词ID)。例如“文档1”经过分词,提取了20个关键词,每个关键词都会记录它在文档中的出现次数和出现位置。

      得到正向索引的结构如下:一般是通过key,去找value。
    “文档1”的ID > 单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;…………。
    “文档2”的ID > 此文档出现的关键词列表。
    在这里插入图片描述
      当用户在主页上搜索关键词“华为手机”时,假设只存在正向索引(forward index),那么就需要扫描索引库中的所有文档,找出所有包含关键词“华为手机”的文档,再根据打分模型进行打分,排出名次后呈现给用户。因为互联网上收录在搜索引擎中的文档的数目是个天文数字,这样的索引结构根本无法满足实时返回排名结果的要求。

      所以,搜索引擎会将正向索引重新构建为倒排索引,即把文件ID对应到关键词的映射转换为关键词到文件ID的映射,每个关键词都对应着一系列的文件,这些文件中都出现这个关键词。

      得到倒排索引的结构如下:从词的关键字,去找文档。
    “关键词1”:“文档1”的ID,“文档2”的ID,…………。
    “关键词2”:带有此关键词的文档ID列表。
    在这里插入图片描述

    二、单词——文档矩阵

      单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,下图展示了其含义。每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系。
    在这里插入图片描述
      从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其它单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过单词1,而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。

      搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式,所以本博文主要介绍“倒排索引”的技术细节。
     

    三、倒排索引基本概念

      文档(Document):一般搜索引擎的处理对象是互联网网页,而文档这个概念要更宽泛些,代表以文本形式存在的存储对象,相比网页来说,涵盖更多种形式,比如Word,PDF,html,XML等不同格式的文件都可以称之为文档。再比如一封邮件,一条短信,一条微博也可以称之为文档。

      文档集合(Document Collection):由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。

      文档编号(Document ID):在搜索引擎内部,会将文档集合内每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识,这样方便内部处理,每个文档的内部编号即称之为“文档编号”,后文有时会用DocID来便捷地代表文档编号。

      单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。

      倒排索引(Inverted Index):倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

      单词词典(Lexicon):搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

      倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。

      倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

    关于这些概念之间的关系,通过下图可以比较清晰的看出来。
    在这里插入图片描述

    四、倒排索引简单实例

      倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。

      假设文档集合包含五个文档,每个文档内容如下图所示,在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。
    在这里插入图片描述
      中文和英文等语言不同,单词之间没有明确分隔符号,所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流,为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引。在下图中,“单词ID”一栏记录了每个单词的单词编号,第二栏是对应的单词,第三栏即每个单词对应的倒排列表。比如单词“谷歌”,其单词编号为1,倒排列表为{1,2,3,4,5},说明文档集合中每个文档都包含了这个单词。
    在这里插入图片描述
      之所以说上图所示倒排索引是最简单的,是因为这个索引系统只记载了哪些文档包含某个单词,而事实上,索引系统还可以记录除此之外的更多信息。下图是一个相对复杂些的倒排索引,与上图的基本索引系统比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。在图5的例子里,单词“创始人”的单词编号为7,对应的倒排列表内容为:(3:1),其中的3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次,其它单词对应的倒排列表所代表含义与此相同。
    在这里插入图片描述
      实用的倒排索引还可以记载更多的信息,下图所示索引系统除了记录文档编号和单词频率信息外,额外记载了两类信息,即每个单词对应的“文档频率信息”(对应下图的第三栏)以及在倒排列表中记录单词在某个文档出现的位置信息。
    在这里插入图片描述
      “文档频率信息”代表了在文档集合中有多少个文档包含某个单词,之所以要记录这个信息,其原因与单词频率信息一样,这个信息在搜索结果排序计算中是非常重要的一个因子。而单词在某个文档中出现的位置信息并非索引系统一定要记录的,在实际的索引系统里可以包含,也可以选择不包含这个信息,之所以如此,因为这个信息对于搜索系统来说并非必需的,位置信息只有在支持“短语查询”的时候才能够派上用场。

      以单词“拉斯”为例,其单词编号为8,文档频率为2,代表整个文档集合中有两个文档包含这个单词,对应的倒排列表为:{(3;1;<4>),(5;1;<4>)},其含义为在文档3和文档5出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第四个单词是“拉斯”。

      上图所示倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此,区别无非是采取哪些具体的数据结构来实现上述逻辑结构。

      有了这个索引系统,搜索引擎可以很方便地响应用户的查询,比如用户输入查询词“Facebook”,搜索系统查找倒排索引,从中可以读出包含这个单词的文档,这些文档就是提供给用户的搜索结果,而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序,计算文档和查询的相似性,按照相似性得分由高到低排序输出,此即为搜索系统的部分内部流程,具体实现方案本书第五章会做详细描述。
     

    五、单词词典

      单词词典是倒排索引中非常重要的组成部分,它用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。

      对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构和树形词典结构。

    1.哈希加链表:

      下图是这种词典结构的示意图。这种词典结构主要由两个部分构成:

      主体部分是哈希表,每个哈希表项保存一个指针,指针指向冲突链表,在冲突链表里,相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词获得相同的哈希值,如果是这样,在哈希方法里被称做是一次冲突,可以将相同哈希值的单词存储在链表里,以供后续查找。
    在这里插入图片描述
      在建立索引的过程中,词典结构也会相应地被构建出来。比如在解析一个新文档的时候,对于某个在文档中出现的单词T,首先利用哈希函数获得其哈希值,之后根据哈希值对应的哈希表项读取其中保存的指针,就找到了对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词,说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,相应的词典结构也就建立起来了。

      在响应用户查询请求时,其过程与建立词典类似,不同点在于即使词典里没出现过某个单词,也不会添加到词典内。以上图为例,假设用户输入的查询请求为单词3,对这个单词进行哈希,定位到哈希表内的2号槽,从其保留的指针可以获得冲突链表,依次将单词3和冲突链表内的单词比较,发现单词3在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的倒排列表来进行后续的工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

    2.树形结构:

      B树(或者B+树)是另外一种高效查找结构(PS:MySQL就是B树索引最好的例子),下图是一个 B树结构示意图。B树与哈希方式查找不同,需要字典项能够按照大小排序(数字或者字符序),而哈希方式则无须数据满足此项要求。

      B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用,最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。
    在这里插入图片描述

    六、倒排索引数据结构

      倒排索引的核心分为两部分,第一部分为单词词典(Term Dictionary),记录所有文档的单词以及单词到倒排列表的关联关系。在前面的例子中,单词的量并不是很多,但是在实际生产中,单词量会非常大,所以实际会采用 B+ 树和哈希拉链法去存储单词的词典,以满足高性能的插入与查询。

      第二部分是倒排列表(Posting List),它记录了单词对应文档的结合,倒排列表是由倒排索引项(Posting) 组成,倒排索引项包含:

    • 文档 ID:用于获取原始信息
    • 词频(TF,Term Frequency):该单词在文档中出现的次数,用于相关性评分
    • 位置(Position):单词在文档中分词的位置,用于语句搜索(Phrase Query)
    • 偏移(Offset):记录单词的开始结束位置,实现高亮显示(比如用 GitHub 搜索的时候,搜索的关键词会高亮显示)

    下面我们来用一张图来整体看下倒排索引:(PS:如果类比现代汉语词典的话,那么Term就相当于词语,Term Dictionary相当于汉语词典本身,Term Index相当于词典的目录索引)
    在这里插入图片描述
      一个倒排索引是由单词词典(Term Dictionary)和倒排列表(Posting List)组成的,单词词典会记录倒排列表中每个单词的偏移位置。比如当搜索 Allen 的时候,首先会通过单词词典快速定位到 Allen,然后从 Allen 这里拿到在倒排列表中的偏移,快速定位到在倒排列表中的位置,从而真正拿到倒排索引项 [12,15](这里只是列了下 Document ID,其实是像上面讲的包含 4 项信息的项),拿到这个项可以去索引上拿到原始信息,可以去计算打分排序返回给用户。

      倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件被称之为倒排文件,倒排文件是存储倒排索引的物理文件。
    在这里插入图片描述

    七、ElasticSearch 倒排索引

      在了解了倒排索引的数据结构后,让我们来看下 ES 中的倒排索引吧!

      那么在 ElasticSearch 中的文档是基于 Json 格式的,其中一个文档包含多个字段,每个字段都会有自己的倒排索引。在 Mapping 中可以去设置对某些字段不做索引,这样做可以节省存储空间,但同时也会导致这个字段无法搜索了。比如一个文档,其中包含两个字段 username 和 job:

    {
        "username":"wupx",
        "job":"programmer"
    }
    

      在构建索引的时候是根据字段构建的,那么 ES 中 username 会有一个倒排索引,job 也会有一个倒排索引。
    在这里插入图片描述

    八、ElasticSearch读写操作

    参考:ElasticSearch技术原理

    1.基本概念:

    索引(Index):ES将数据存储于一个或多个索引中,索引是具有类似特性的文档的集合,类比传统关系型数据库的一个数据库(database),或者一个数据存储方案(schema)。索引由其名称(必须全小写字符)进行标识,并通过引用此名称完成文档的创建、搜索、更新及删除操作。

    类型(Type):类型是索引内部的逻辑分区(category/partition),一个索引内部可定义一个或多个类型(type)。类比传统关系型数据库的一张表。

    文档(Document):文档是索引和搜索的原子单位,它是包含了一个或多个域(field)的容器,采用JSON格式表示。文档由一个或多个域组成,每个域拥有一个名字及一个或多个值,类比传统关系型数据库的一条记录。

    节点(Node):一个运行中的ElasticSearch实例为一个节点,而集群是由一个或多个拥有相同cluster.name配置的节点组成。ES集群中的节点有三种不同的类型:

    • 主节点:负责管理集群范围内的所有变更,主节点并不需要涉及到文档级别的变更和搜索等操作,可通过属性node.master进行设置。
    • 数据节点:存储数据和其对应的倒排索引,可通过属性node.data属性进行设置。
    • 协调节点:如果node.master和node.data属性均为false,则此节点称为协调节点,用来响应客户请求,均衡每个节点的负载。

    分片(Shard):一个索引中的数据保存在多个分片中,相当于水平分表。一个分片便是一个Lucene的实例,它本身就是一个完整的搜索引擎。分片是数据的容器,文档保存在分片内,分片又被分配到集群内的各个节点,当集群的规模扩大或缩小时,ES自动在各节点中迁移分片,使得数据均衡分布。一个分片可以是主分片或者副本分片,索引内任意一个文档都归属于一个主分片,所以主分片的数目决定着索引能够保存的最大数据量,一个副本分片只是一个主分片的拷贝,并为搜索和返回文档的读操作提供服务。

    2.写操作(write):

      索引新文档(create):当用户向一个节点提交了一个索引新文档的请求,节点会计算新文档应该加入到哪个分片(shard)中。

    • (1)每次写入新文档时,都会先写入内存中,并将这一操作写入一个translog文件(transaction.log)中,此时如果执行搜索操作,这个新文档不能被索引到;
    • (2)ES每隔1秒(这个时间可修改)进行一次刷新(refresh)操作,将在这1秒时间内写入内存的文档写入一个文件系统缓存(filesystem cache)中,并构成一个分段(segment)。此时这个segment里的文档可以被搜索到,但是尚未写入硬盘,可能会因宕机而导致文档丢失;
    • (3)不断有新的文档写入,则这一过程将不断重复执行,不断生成新的segment文件,而translog文件将越来越大;
    • (4)每隔30分钟或者translog文件变得很大,则执行一次fsync操作,此时所有在文件系统缓存中的segment将被写入磁盘,而translog将被删除(此后会生成新的translog);

      ES引入了translog来记录两次fsync之间所有的操作,这样机器从故障中恢复或重新启动,ES便可以根据translog进行还原。当然,translog本身也是文件,存于内存中,也存在数据丢失的可能性,因此,ES会每隔5秒或者一次写入请求完成后将translog写入磁盘。此外,由于不断生成新的segment文件,对于一个分片进行查询请求时,会轮流查询分片中的所有segment,这非常影响搜索的性能,因此ES会自动启动合并segment的工作,将一部分segment合并成一个新的大segment,所有被合并的旧segment被清除。

      更新(update)和删除(delete)文档:ES的索引是不能修改的,因此更新和删除操作并不是直接在原索引上执行。每个分区上的segment都会维护一个del文件,用来记录被删除的文档,每当用户发起一个删除请求,文档并没有被真正删除,索引也没有发生改变,而是在del文件中标识该文档已被删除。因此,被删除的文档依然可以被检索到,只是在返回结果时被过滤掉,每次启动segment合并工作时,那些被标识为删除的文档才会被真正删除。

      更新文档首先查找原文档,得到该文档的版本号,然后将修改后的文档写入内存,即写入一个新文档,同时旧文档被标识为删除。

    3.读操作(read):

      查询的过程大体上分为查询(query)和取回(fetch)两个阶段,通过广播查询请求到所有相关分片,并将它们的响应整合成全局排序后的结果集合,这个结果集合会返回给客户端。

    • (1)当一个节点接收到一个搜索请求,则这个节点就变成了协调节点;
    • (2)广播请求到索引中每一个节点的分片,查询请求可以被某个主分片或者某个副本分片处理;
    • (3)每个分片将会在本地构建一个优先级队列。如果客户端要求返回结果排序中从第from开始数量为size的结果集,则每个节点都需要生产一个from+size大小的结果集,因此优先级队列的大小为from+size,分片仅会返回一个轻量级的结果给协调节点。
    • (4)协调节点将所有分片的结果汇总,并进行全局排序,得到最终的查询排序结果。
    • (5)以上步骤为查询阶段,得到一个排序结果,标记出哪些文档是符合搜索要求的,仍然需要获取这些文档返回客户端。协调节点向含有该文档的分配发送get请求,分片获取文档返回给协调节点,协调节点将结果返回给客户端。

    参考:
    什么是倒排索引?
    《从零开始学习自然语言处理(NLP)》-倒排索引(1)
    倒排索引为什么叫倒排索引?
    Elasticsearch倒排索引结构
    https://www.elastic.co/guide/cn/elasticsearch/guide/current/inverted-index.html
    搜索引擎之倒排索引解读

    展开全文
  • 倒排索引源码 java 车间火花实践 在本次研讨会中,练习的重点是使用 和 API,以及数据处理。 练习在 Java 和我的 github 帐户中都可用(这里是 java)。 你只需要克隆项目就可以了! 如果您需要帮助,请查看解决方案...
  • c++实现倒排索引算法

    2020-12-03 17:17:12
    c++倒排索引算法
  • 需求 有如下数据 a.txt hello tom hello jim hello kitty hello rose b.txt hello jerry hello jim hello kitty hello jack c.txt hello jerry hello java hello c++ hello c++ 需要输出如下格式: ...1
  • 采用MFC可视化,通过建立倒排索引表,简单实现了搜索功能
  • 文档倒排索引的MapReduce程序设计与实现
  • 针对SSE-1密文检索方案的一些性能缺陷,采用不同的加密策略,在lucene倒排索引的基础上,设计了密文倒排索引Crypt-Lucene,同时结合云计算特点,设计了并行构建Crypt-Lucene方案,理论分析了方案的性能,并通过实验...
  • 倒排索引如何建立 以及如何压缩
  • 倒排索引处理文档

    2014-01-16 09:06:17
    倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,561
精华内容 19,424
关键字:

倒排索引