精华内容
下载资源
问答
  • 倒排索引数据结构是什么
    2020-07-03 23:31:01

    一. 倒排索引

    • 倒排索引(Inverted Index) 也被称为“反向索引”或“反向文件”,是一种索引数据结构。倒排索引在“内容”(例如,单词、数字)和存放内容的“位置”(例如,数据库、文件、一组文件)之间建立映射,其目的在于快速全文检索和使用最小处理代价将新文件添加进数据库。通过倒排索引,可以快速地根据“内容”查找到包含它的文件。倒排索引是目前文件检索系统中使用最广泛的数据结构,被广泛用于搜索引擎中。倒排索引有两种不同的索引形式:一种是 “给定一个词语,查找出所有包含这个词语的文档”:另一种是“给定一个词语,不仅能查找出所有包含这个词语的文档,还能查找出这个词语在这篇文档中文档位置”。显然,后者可以提供更多的功能(例如,短语搜索),但是需要更多的时间和空间来创建索引。

    二. 倒排索引原理

    1. 词语和文档的关系

    • “文档”是以文本形式存在的存储对象,它是一个比较宽泛的概念:一个 Word 文件、一条短信都可以称为一个文档。在搜索引擎中,文档般指的是 “互联网网页”。将多个文档聚集在一起,就形成了“文档集合”,或称为“语料库”。

    • 如果使用一个矩阵来描述词语和文档之间的关系,不难得出如下“词语-文档矩阵”。其中,每一列代表一个文档,每一行代表一个词语,每一个单元格代表“此文档中出现此词语的次数”。

    出现次数文档1文档2文档3文档4
    词语141
    词语234
    词语331
    词语439
    • 矩阵中的第一列说明 “在文档1中,词语1出现了4次、词语2和词语3均出现了3次,并且文档1中不再有其他词语出现"。同理,矩阵中的第行则说明“词语1在文档1中出现在4次,在文档4中出现1次,在其他文档中不出现"。其他行列同理。

    • 人们关心的是 “篇文档中出现了哪些词语”, 但搜索引擎更关心“二个词语在哪些文档中出现”,并且需要快速地把这些文档全部呈现出来。搜索引擎的索引实际上就是上述“词语–文档矩阵”这一概念数据模型的一种具体实现形式,倒排索引便是其中一种比较有效的实现方式,通过倒排索引,可以根据单词快速获取包含这个词语的文档列表。除此之外,搜索引擎中经常用到的还有“签名文件”“后缀树”等。

    2. 倒排索引的数据结构

    • 倒排索引可以使用这样一个Map来实现:如下图所示,每一个词语都是Map中的一个键(Key),这个键对应的Value 是一个集合,里面保存着包含这个词语的文档的编号。存储形式为: Map< String key, Set< Struct< DocID> value > >。
      在这里插入图片描述

    • 同理,如果要在倒排索引中加入更多信息,可以在Value 中增加记录项目,如下图所示。例如,加入“此词语在此文档中出现次数及位置”等信息。
      在这里插入图片描述

    3. 倒排索引的建立实例

    • 假设现在有两篇文档,每篇文档的内容如下:
    文档内容
    文档1The quick brown fox jumped over the lazy dog.
    文档2Quick brown foxes leap over lazy dogs in summer.
    • (1)文章本分词

    • 我们需要将整段的字 符串拆分成为一个一个的词语,即文本分词。英文句子由于单词间有空格分隔,比较容易处理,但中文不同,词语之间并没有空格分开。这时就需要借助专业分词工具将句子正确地切分成词语。例如,将“中国科学家屠呦呦获得诺贝尔医学和生理学奖”可以被拆分成“中国 科学家 屠呦呦 获得 诺贝尔 医学 和 生理学 奖”。

    • (2)去除无关词语

    • 英文中存在大量的“a”“the”“too”之类的对搜索没有实际帮助的词语,中文中的“的”“是”“这”等字也通常无具体含义。这些词语都可以直接被去除掉。另外,所有标点符号也可以一并去除。

    • (3)词语归一化

    • 我们通常希望在查询“fox"的时候将包含“Fox" “FOX"“foxes" 的文章一同查询出来,并且在查询"jump"的时候能将包含“jumped"“jumps"的文章也. 并查询出来。这时就要做统一大小写、 统一词语的格式等操作。

    • 经过上述操作,上述两个文档内容会“变成”以下文档:

    文档内容
    文档1quick brown fox jump over lazy dog
    文档2quick brown fox leap over lazy dog summer
    • (4)建立词语文档矩阵

    • 可以根据上述分析结果快速写出如下词语–文档矩阵:

    出现次数文档1文档1
    quick11
    brown11
    fox11
    jump1
    over11
    lazy11
    dog11
    leap1
    summer1
    • (5)建立倒排索引

    • 可以根据上述词语–文档矩阵建立如下倒排索引:

    Key(词语)Value(在哪些文档中出现)
    quick{1,2}
    brown{1,2}
    fox{1,2}
    jump{1}
    over{1}
    lazy{1,2}
    dog{1,2}
    leap{2}
    summer{2}

    4. 倒排索引的更新策略

    • 更新策略主要有4种:完全重建策略、再合并策略、原地更新策略及混合策略。

    • (1)完全重建策略:新文档并不立即被解析和加入索引中,而是先进行“文档暂存”。待文档暂存区中的文档达到一定数量后,将这些新文档和旧文档混在起, 对所有文档重建新索引,替换旧索引。这种方法代价极高,但主流商业搜索引擎有时会采用这种方法更新索引。

    • (2)再合并策略:新文档会立即被解析,但解析结果并不会立刻加入到旧索引中,而是进行“索引暂存”。索引暂存其实也是一个建立索引的过程。待索引暂存区达到一定数量后,暂存区中的索引和旧索引进行合并。

    • (3) 原地更新策略:新文档立刻被解析,解析结果立刻被加入旧索引中。这种方法有较好的时效性,在理论上是种比较优秀的策略。 为了加快索引速度, 索引内部-般都有一个“调优”的机制,例如,移动某些文件在磁盘上的位置,使索引过程中磁头移动距离尽可能小,磁盘等待时间尽量少。如果新文档立刻进入旧索引,那么索引内部就会不停地执行“调优”过程,有时反而会使性能下降。

    • (4)混合策略:其思想是混合地使用上述几种策略,取长补短,以达到最好的性能。

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

    2021-01-20 12:12:43
    Elasticsearch通过倒排索引数据结构来实现全文搜索 在关系数据库系统里,索引是检索数据最有效率的方式。但对于搜索引擎,它并不能满足其特殊要求,比如海量数据下比如百度或者谷歌要搜索百亿级的网页,如果使用...
  • 什么需要倒排索引 每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同的索引,才能起到最大化加快查询的目的。 Elasticsearch 是建立在...

    为什么需要倒排索引

    每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同的索引,才能起到最大化加快查询的目的。

    Elasticsearch 是建立在全文搜索引擎库 Lucene 基础上的搜索引擎,它隐藏了 Lucene 的复杂性,取而代之的提供一套简单一致的 RESTful API,不过掩盖不了它底层也是 Lucene 的事实。
    Elasticsearch 的倒排索引,其实就是 Lucene 的倒排索引。

    倒排索引的内部结构

    在这里插入图片描述
    Lucene 的倒排索,增加了最左边的一层「字典树」term index,它不存储所有的单词,只存储单词前缀,通过字典树找到单词所在的块,也就是单词的大概位置,再在块里二分查找,找到对应的单词,再找到单词对应的文档列表。

    当然,内存寸土寸金,能省则省,所以 Lucene 还用了 FST(Finite State Transducers)对它进一步压缩。

    FST 是什么?这里就不展开了,这次重点想聊的,是最右边的 Posting List 的,别看它只是存一个文档 ID 数组,但是它在设计时,遇到的问题可不少。

    Frame Of Reference

    原生的 Posting List 有两个痛点:

    • 如何压缩以节省磁盘空间
    • 如何快速求交并集(intersections and unions)

    先来聊聊压缩。

    我们来简化下 Lucene 要面对的问题,假设有这样一个数组:

    [73, 300, 302, 332, 343, 372]

    如何把它进行尽可能的压缩?

    Lucene 里,数据是按 Segment 存储的,每个 Segment 最多存 65536 个文档 ID, 所以文档 ID 的范围,从 0 到 2^16-1,所以如果不进行任何处理,那么每个元素都会占用 2 bytes ,对应上面的数组,就是 6 * 2 = 12 bytes.

    怎么压缩呢?

    压缩,就是尽可能降低每个数据占用的空间,同时又能让信息不失真,能够还原回来。

    Step 1:Delta-encode —— 增量编码

    我们只记录元素与元素之间的增量,于是数组变成了:

    [73, 227, 2, 30, 11, 29]

    Step 2:Split into blocks —— 分割成块

    Lucene里每个块是 256 个文档 ID,这样可以保证每个块,增量编码后,每个元素都不会超过 256(1 byte).

    为了方便演示,我们假设每个块是 3 个文档 ID:

    [73, 227, 2], [30, 11, 29]

    Step 3:Bit packing —— 按需分配空间

    对于第一个块,[73, 227, 2],最大元素是227,需要 8 bits,好,那我给你这个块的每个元素,都分配 8 bits的空间。

    但是对于第二个块,[30, 11, 29],最大的元素才30,只需要 5 bits,那我就给你每个元素,只分配 5 bits 的空间,足矣。

    这一步,可以说是把吝啬发挥到极致,精打细算,按需分配。

    以上三个步骤,共同组成了一项编码技术,Frame Of Reference(FOR):
    在这里插入图片描述

    Roaring bitmaps

    接着来聊聊 Posting List 的第二个痛点 —— 如何快速求交并集(intersections and unions)。

    在 Lucene 中查询,通常不只有一个查询条件,比如我们想搜索:

    • 含有“生存”相关词语的文档
    • 文档发布时间在最近一个月
    • 文档发布者是平台的特约作者

    这样就需要根据三个字段,去三棵倒排索引里去查,当然,磁盘里的数据,上一节提到过,用了 FOR 进行压缩,所以我们要把数据进行反向处理,即解压,才能还原成原始的文档 ID,然后把这三个文档 ID 数组在内存中做一个交集。

    即使没有多条件查询, Lucene 也需要频繁求并集,因为 Lucene 是分片存储的。

    同样,我们把 Lucene 遇到的问题,简化成一道算法题。

    假设有下面三个数组:

    [64, 300, 303, 343]

    [73, 300, 302, 303, 343, 372]

    [303, 311, 333, 343]

    求它们的交集。

    Option 1: Integer 数组

    直接用原始的文档 ID ,可能你会说,那就逐个数组遍历一遍吧,遍历完就知道交集是什么了。

    其实对于有序的数组,用跳表(skip table)可以更高效,这里就不展开了,因为不管是从性能,还是空间上考虑,Integer 数组都不靠谱,假设有100M 个文档 ID,每个文档 ID 占 2 bytes,那已经是 200 MB,而这些数据是要放到内存中进行处理的,把这么大量的数据,从磁盘解压后丢到内存,内存肯定撑不住。

    Option 2: Bitmap

    假设有这样一个数组:

    [3,6,7,10]

    那么我们可以这样来表示:

    [0,0,1,0,0,1,1,0,0,1]

    看出来了么,对,我们用 0 表示角标对应的数字不存在,用 1 表示存在。

    这样带来了两个好处:

    • 节省空间:既然我们只需要0和1,那每个文档 ID 就只需要 1 bit,还是假设有 100M 个文档,那只需要 100M bits = 100M * 1/8 bytes = 12.5 MB,比之前用 Integer 数组 的 200 MB,优秀太多。
    • 运算更快:0 和 1,天然就适合进行位运算,求交集,「与」一下,求并集,「或」一下,一切都回归到计算机的起点。

    Option 3: Roaring Bitmaps

    细心的你可能发现了,bitmap 有个硬伤,就是不管你有多少个文档,你占用的空间都是一样的,之前说过,Lucene Posting List 的每个 Segement 最多放 65536 个文档ID,举一个极端的例子,有一个数组,里面只有两个文档 ID:

    [0, 65535]

    用 Bitmap,要怎么表示?

    [1,0,0,0,….(超级多个0),…,0,0,1]

    你需要 65536 个 bit,也就是 65536/8 = 8192 bytes,而用 Integer 数组,你只需要 2 * 2 bytes = 4 bytes

    呵呵,死板的 bitmap。可见在文档数量不多的时候,使用 Integer 数组更加节省内存。

    我们来算一下临界值,很简单,无论文档数量多少,bitmap都需要 8192 bytes,而 Integer 数组则和文档数量成线性相关,每个文档 ID 占 2 bytes,所以:

    8192 / 2 = 4096

    当文档数量少于 4096 时,用 Integer 数组,否则,用 bitmap。

    在这里插入图片描述

    补充

    这里补充一下 Roaring bitmaps 和 之前讲的 Frame Of Reference 的关系。
    Frame Of Reference 是压缩数据,减少磁盘占用空间,所以当我们从磁盘取数据时,也需要一个反向的过程,即解压,解压后才有我们上面看到的这样子的文档ID数组:[73, 300, 302, 303, 343, 372] ,接着我们需要对数据进行处理,求交集或者并集,这时候数据是需要放到内存进行处理的,我们有三个这样的数组,这些数组可能很大,而内存空间比磁盘还宝贵,于是需要更强有力的压缩算法,同时还要有利于快速的求交并集,于是有了Roaring Bitmaps 算法。
    另外,Lucene 还会把从磁盘取出来的数据,通过 Roaring bitmaps 处理后,缓存到内存中,Lucene 称之为 filter cache。

    Lucene 为什么不用 b+ 树来搜索数据?

    Mysql 为什么不用 倒排索引来检索数据?

    b+树主要设计目的是减少搜索时访问磁盘的次数,而Lucene等搜索引擎设计的时候,追求的目标是倒排压缩率&倒排解压速度&倒排Bool运算速度。取倒排到内存运算的时候,是连续读取,时间开销和倒排的大小有关系,所以并不适合用b+数。

    同理Mysql等数据库使用索引的目的是快速定位某一行数据,若使用倒排这种线性化的数据结构存储数据,其查找的时候访问磁盘的次数会远大于使用b+的数据库。

    一句话,现有的pc架构 &业务需求决定了什么时候使用什么数据结构。

    展开全文
  • 先介绍一下正向索引: 当用户发起查询时(假设查询为一个关键词),搜索引擎会扫描索引库中的所有...为了增加效率,搜索引擎会把正向索引变为反向索引(倒排索引)即把“文档→单词”的形式变为“单词→文档”的形式。

    Elasticsearch——倒排索引

    1.正向索引和反向索引

    先介绍一下正向索引: 当用户发起查询时(假设查询为一个关键词),搜索引擎会扫描索引库中的所有文档,找出所有包含关键词的文档,这样依次从文档中去查找是否含有关键词的方法叫做正向索引。互联网上存在的网页(或称文档)不计其数,这样遍历的索引结构效率低下,无法满足用户需求。
    正向索引结构如下:
    文档1的ID→单词1的信息;单词2的信息;单词3的信息…
    文档2的ID→单词3的信息;单词2的信息;单词4的信息…
    在这里插入图片描述

    3.反向索引

    为了增加效率,搜索引擎会把正向索引变为反向索引(倒排索引)即把“文档→单词”的形式变为“单词→文档”的形式。倒排索引具体机构如下:
    单词1→文档1的ID;文档2的ID;文档3的ID…
    单词2→文档1的ID;文档4的ID;文档7的ID…
    在这里插入图片描述

    3. 单词-文档矩阵

    单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。

    • D1:乔布斯去了中国。
    • D2:苹果今年仍能占据大多数触摸屏产能。
    • D3:苹果公司首席执行官史蒂夫·乔布斯宣布,iPad2将于3月11日在美国上市。
    • D4:乔布斯推动了世界,iPhone、iPad、iPad2,一款一款接连不断。
    • D5:乔布斯吃了一个苹果。
      此时用户查询为“苹果 And (乔布斯 Or iPad2)”,表示包含单词“苹果”,同时还包含“乔布斯”或“iPad2”的其中一个。
      则“单词-文档”矩阵为:
      在这里插入图片描述
      该矩阵可以从两个方向进行解读:
    • 纵向: 表示每个单独的文档包含了哪些单词,比如D1包含了“乔布斯这个词”,D4包含了“乔布斯”和“iPad2”。
    • 横向: 表示哪些文档包含了该单词,比如D2、D3、D5包含了“苹果”这个词。

    搜索引擎的索引其实就是实现“单词-文档”矩阵的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式,但是“倒排索引”是实现单词到文档映射关系的最佳实现方式。

    4.倒排索引

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

    • 单词词典(Lexicon):搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
    • 倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。
    • 倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。
      在这里插入图片描述

    5.倒排索引简单实例

    还是用上面提到的例子:
    Doc1:乔布斯去了中国。
    Doc2:苹果今年仍能占据大多数触摸屏产能。
    Doc3:苹果公司首席执行官史蒂夫·乔布斯宣布,iPad2将于3月11日在美国上市。
    Doc4:乔布斯推动了世界,iPhone、iPad、iPad2,一款一款接连不断。
    Doc5:乔布斯吃了一个苹果。
    这五个文档中的数字代表文档的ID,比如"Doc1"中的“1”。
    通过这5个文档建立简单的倒排索引:
    在这里插入图片描述

    首先要用分词系统将文档自动切分成单词序列,这样就让文档转换为由单词序列构成的数据流,并对每个不同的单词赋予唯一的单词编号(WordID),并且每个单词都有对应的含有该单词的文档列表即倒排列表。如上表所示,第一列为单词ID,第二列为单词ID对应的单词,第三列为单词对应的倒排列表。如第一个单词ID“1”对应的单词为“乔布斯”,单词“乔布斯”的倒排列表为{1,3,4,5},即文档1、文档3、文档4、文档5都包含有单词“乔布斯”。

    这上面的列表是最简单的倒排索引,下面介绍一种更加复杂,包含信息更多的倒排索引。
    在这里插入图片描述
    TF(term frequency): 单词在文档中出现的次数。
    Pos: 单词在文档中出现的位置。
    这个表格展示了更加复杂的倒排索引,前两列不变,第三列倒排索引包含的信息为(文档ID,单词频次,<单词位置>),比如单词“乔布斯”对应的倒排索引里的第一项(1;1;<1>)意思是,文档1包含了“乔布斯”,并且在这个文档中只出现了1次,位置在第一个。

    展开全文
  • Elasticsearch 建立在全文搜索引擎 Apache Lucene™ 基础上,通过 Lucene 的倒排索引技术实现比关系型数据库更快的过滤,从而很方便的使大量数据具有搜索、分析和探索的能力。 毫无疑问,Elasticsearch的底层核心是...

    Elasticsearch 简介

    Elasticsearch 是一个分布式、高扩展、高实时的搜索与数据分析引擎。Elasticsearch 建立在全文搜索引擎 Apache Lucene™ 基础上,通过 Lucene 的倒排索引技术实现比关系型数据库更快的过滤,从而很方便的使大量数据具有搜索、分析和探索的能力。

    毫无疑问,Elasticsearch的底层核心是倒排索引。 Elasticsearch通过扩展服务器集群的方式,将数据以文档的形式,FST压缩的方式,分布式实时存储;同时为文件每一个字段添加倒排索引,通过倒排索引以及skip list 和 bitset 三种数据结构实现实时分布式分析和快速搜索的功能。

    Elasticsearch 数据存储

    先说Elasticsearch的文件存储,Elasticsearch是面向文档型数据库,一条数据在这里就是一个文档,用JSON作为文档序列化的格式,比如下面这条学生数据:

    {
    	"stuName":"Rose",
    	"age":18,
    	"gender":"Male",
    	"resume":"I am gooding at studying",
    	"tuition":26800.00,
    	"hobbies":["sleep","games"],
    	"address":{
    		"province":"JiangSu",
    		"city":"NanJing",
    		"district":"YuHua"
    	}
    }
    

    如果用传统的关系型数据库比如说mysql来存储上述这条数据时,我们能够想到的是去建立一张student表,表中有stuName,age,tuition,hobbies,address字段等,而在Elasticsearch里这就是一个记录student类型的文档,所有的字段类型都存在于这个文档的索引里。这里有一份简易的将Elasticsearch和关系型数据术语对照表:

    在这里插入图片描述

    Elasticsearch和传统的数据库一样,索引、类型、文档、字段都是一对多的关系。Elasticsearch数据交互可以通过HTTP的Restful请求方式直接请求,也可以通过java API请求。值得注意的是,Elasticsearch主要用来查询,因为其每一个字段都有倒排索引这种需要大量的储存空间,我刚开始接触Elasticsearch的事实增删改,如果不实用shell脚本的话,要一条一条的执行,增删改的效率很低,不如传统的数据库。事实上,现在市场的主流就是Elasticsearch与传统数据库公用,Elasticsearch用来查询,传统的用来增删改,Elasticsearch连接数据库和客户端搜索引擎的桥梁。

    倒排索引

    Elasticsearch倒排索引的精髓:

    倒排索引压缩储存空间,减少磁盘读取次数;严格储存结构,节省搜索时间。

    简单的来说,Elasticsearch将磁盘里的东西尽量搬进内存,减少磁盘随机读取次数(同时也利用磁盘顺序读特性),结合各种奇技淫巧的压缩算法,用极其苛刻的态度使用内存。

    Elasticsearch能够通过倒排索引来达到实时、高效的搜索是怎么实现的呢?下面我从时间和空间的概念来谈谈倒排索引的原理。

    倒排索引的空间结构是什么样的?

    首先根据上述例子拿出stuName,age,gender字段的来说:

    student类型的文档上层school对应着一个索引的index为1:

    PUT http://192.168.152.129:9200/school
    

    student类型的文档对应着一个index:

    | ID | stuName| age| gender |
    | -- |--------|----| -------| 
    | 1  | Rose   | 24 | Male   |
    | 2  | John   | 24 | Female |
    | 3  | Bill   | 29 | Female |
    

    stuName:

    | stuName| Posting List|
    |--------|-------------| 
    | Rose   |     1       | 
    | John   |     2       |  
    | Bill   |     3       | 
    

    age:

    | Term | Posting List |
    | ---- |--------------|
    | 24   | 	[1,2] 	  |
    | 29   | 	  3 	  |
    

    gender:

    |  Term  | Posting List |
    | ------ |--------------|
    | Female |      1       |
    |  Male  |    [2,3]     |
    

    如上所述,student所在的school索引index,student每个文档dictionary,student的每个字段Posting List都建立了索引。用一张图表示如下:
    在这里插入图片描述

    Posting List

    Posting List是Elasticsearch中为每个字段field自动提供的索引集合,比方说24,29 这些叫做 term,而 [1,2] 就是 posting list。Posting list 就是一个 int 的数组,存储了所有符合某个 term 的文档 id。

    Term Dictionary

    Elasticsearch中为了能够快速的找到某个term,也就是我们经常用某个字段来快速查询,为了实现这一功能,Term Dictionary就产生了。Term Dictionary的实现底层就是B+Tree,使用二分法进行查询term, logN 次磁盘查找效率,就像字典查询一样,首字母是什么,就先检索什么,然后再看第二个字母是什么,检索第二个字母,…,一直到检索到这个term为止。

    Term Index

    由于磁盘随机读的存在,就必须将一部分数据存在缓存内存中,但是Term Dictionary磁盘存储空间的巨大,又不能将Term Dictionary完整的放到内存里。因此就有了Term Index,它就像字典里一个更大的章节一样,每个大的章节再对应着多个小的章节Term Dictionary,这样就能实现速的找到某个term。

    Term Index、Term Dictionary和Posting List个关系

    如下图 所示:“A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, 和 “inn” 这些单词是如何储存在Elasticsearch里的呢?Term Index就像一棵倒挂的树一样,它就是这棵树的根节点,也就是这本字典;Term Dicitionary是根节点的子节点,存放着“t”、“A”、“i”,也就是所储存单词的前缀;然后Posting List就是相同前缀的单词(term)集合,里面装着我们要检索的单词(term)。因此通过 term index能够快速精确的检索到我们所需要的term

    在这里插入图片描述
    如下图所示,关系型数据库如Mysql 只有 term dictionary 这一层,是以 b-tree 排序的方式存储在磁盘上的。检索一个 term 需要若干次的 random access 的磁盘操作。而 Elasticsearch 在 term dictionary 的基础上添加了 term index 来加速检索,term index 以树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后,再去磁盘上找 term,大大减少了磁盘的 random access 次数。
    在这里插入图片描述

    倒排索引的时间概念是怎么节省的?

    B-Tree+整体分区快速查找

    上面说到Elasticsearch中的 term dictionary不同于关系型数据库的term dicitionary的结构B-Tree那样,将所存储的数据按照某种规则进行排序储存于磁盘里,然后通过二分法去查找某个term,这样能够达到log N的查询效率;而Elasticsearch中先把 term dictionary分为相同大小的块,然后递归去把每个块分成相同大小的块,进行快速查找。

    举个例子,对于1-16这组数据进行快速查找其中的某个值:

    B-Tree二分法
    在这里插入图片描述
    如图所示B-Tree二分法查找7这个数,需要4次方能查出来。同样的查找1和16也需要4次才能查找出来。

    B-Tree+整体分区法
    在这里插入图片描述
    如图所示B-Tree+整体分区法查找7的时候,只需3次就能找到,相当于“三分法”一样比二分法更加的有效率,但是如果数据每次“三分”时都处于中间,那就无形的增加了判断次数(这种做法,拿要检索的值7和中间块的两头6和11比较),但是这只是极少的数据而已,在海量的数据面前,这数据更是微不足道,所以根据二八定律,它基本上能满足搜索更快的需求。这种是将块或者区域作为一个整体的思想来实现快速搜索,有一点像希尔排序一样,虽然检索效率不稳定,但是能够解决大部分的数据效率问题,就等于实现了整个数据的效率问题。
    更为重要的是,Elasticsearch中不仅term dictionary实现了倒排索引,而且term index也采用了这种倒排索引,这就相当于又套了一层B-Tree+整体分区法,效率提高了一个档次。

    FST增量压缩技术

    上面说过,term index 在内存中是以 FST(finite state transducers)的形式保存的,其特点是非常节省内存。Term dictionary 在磁盘上是以分 block 的方式保存的,一个 block 内部利用公共前缀压缩,比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。那么什么是FTS呢?

    FST的含义:

    FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

    简单的来说,就是用更小的内存空间来储存更多的数据;这就是FST增量压缩技术的核心思想。那么Elasticsearch是如何使用FST来节省空间,达到快速检索的功能了?

    字节bitmaps存储

    之前说过,使用我们要储存term的前缀放入term dictionary似乎就是更小的空间;然而并不是,FST的所用的更小空间实际上是一个byte类型的数组,也就是所谓的字节数组,为了实现这种储存方式,Elasticsearch的倒排索引,将每一个term对应的posting list和其对应的term dictionary都采用short类型的数组建立索引,比如说mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号:0,1,2,3,4,5(term dictionary的block位置)。这就相当于Map<string, integer>的键值对的方式,来实现更小的空间储存。

    简单的posting list 和bitmaps对应关系如下:
    在这里插入图片描述

    字节数组分区bitset存储

    似乎按字节数组那样储存就已经是最小了,答案显然是错误的;倒排索引提供了一种针对特殊field,比如性别、状态这种只有极少的值,如果按照字节数组来存储,当有海量数据时,那么每一种值对应的term,bitmaps所储存的字节数组也会非常的大,那么该如何储存呢?Elasticsearch posting list倒排索引采用了字节数组分区存储;以0-65535为一个区,65536-131071为下一个区,以此类推,再用再用<商,余数>的组合表示每一组索引id,这样每组里的id范围都在0~65535内了。65535是short类型储存的最大值,正好是用2个字节能表示的最大数。

    简单的posting list 和bitset对应关系如下:
    在这里插入图片描述
    与其保存 100 个 0,占用 100 个 bit。还不如保存 0 一次,然后声明这个 0 重复了 100 遍。这就是bitset的核心所在。

    倒排索引规定:

    If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value

    上述规定posting list的数组长度超过4kb时采用字节数组分区bitset存储,低于4kb时采用字节bitmaps存储。这里的4kb 刚好是磁盘每次随机读取的一个块block的字节大小,更是linux系统规定内存每次读取最小的内存单位。

    联合索引查询

    传统关系型数据库的做法:
    在这里插入图片描述
    如上图所示,mysql怎么做到联合查询的呢?实际上是通过mysql的连接查询来实现的,那么连接查询是怎么查询的,首先拿出第一张表里的每一条数据,逐一到第二张表一条一条数据逐一的对照,不论对照是否匹配,都要进行匹配,上述是mysql连接查询的4种方式:内连接、左连接、右连接和全连接的结果,可以看出它们每一种都要匹配6*16=96次,才能得出结果。

    此外,对于关系型数据库 mysql 来说,如果你给 age 和 gender 两个字段都建立了索引,查询的时候只会选择其中最为严格的索引来使用,然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉,并且很多种情况比如包含NULL值的列、组合索引组合不当和like 前缀出现通配符等会导致索引失效,这样就大大的降低了检索效率。那么要如何才能联合使用两个索引呢?有两种办法:

    1. 使用 skip list 数据结构。同时遍历 gender 和 age 的 posting list,互相 skip;
    2. 使用 bitset 数据结构,对 gender 和 age 两个 filter 分别求出 bitset,对两个 bitset 做 “位与” 操作。

    skip list

    skip list数据结构核心是将一个有序链表level0,挑出其中几个元素到level1及level2,每个level越往上,选出来的指针元素越少,查找时依次从高level往低查找。也就是说每一个链表都有一个指针,每个指针都只要移动一次完整的遍历链表即可,这样比传统的数据库mysql 联表查询一条一条的遍历另一张表的效率要快很多。
    比如以下3个posting list,互相 skip过程:
    在这里插入图片描述
    执行整个过程如下:

    Next -> 2
    Advance(2) -> 13
    Advance(13) -> 13
    Already on 13
    Advance(13) -> 13 MATCH!!!
    Next -> 17
    Advance(17) -> 22
    Advance(22) -> 98
    Advance(98) -> 98
    Advance(98) -> 98 MATCH!!!
    

    最后得出的交集是 [13,98],所需的时间比完整遍历三个 posting list 要快得多。但是前提是每个 list 需要指出 Advance 这个操作,快速移动指向的位置。

    此外当得出这个结果交集的时候,Elasticsearch 还进行了以下方式对内存数据进行压缩,减少读取磁盘速度,提高效率。
    在这里插入图片描述
    对我们要查询的结果进行增量压缩,也就是posting list每一个结果都对应一个int类型的数值,那么第一个采用原值去储存,第二个采用第二个值与第一个值的差来储存,这样就能将posting list中大的值变的相对小一点,然后就可以用更小的空间去存储。

    bitset 按位与

    如果查询的数据是用bitset方式存储,那么就太过简单了,只要按位与,就能查询到两个结果的交集。

    参考文章

    时间序列数据库的秘密 (2)——索引

    展开全文
  • 倒排索引的英文原名是Inverted index,大概因为Invert有颠倒的意思,所以就被翻译成了倒排,然后我们就会在字面上出现误解:很容易让人理解为从A-Z颠倒成Z-A。...索引的数据结构基本上采用倒排索引的结构,luce
  • 深入理解正排索引与倒排索引(设计思想和数据结构
  • ES中的倒排索引什么

    千次阅读 2022-02-24 17:06:26
    传统的检索方式是通过文章,逐个遍历找到对应关键词的位置。 倒排索引,是通过分词策略,形成了词和文章的映射关系表,也称...倒排索引的底层实现是基于:FST(Finite State Transducer)有限状态转移器数据结构。 ...
  • #资源达人分享计划#
  • 深入理解--ES之倒排索引

    千次阅读 2021-01-29 14:48:00
    正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。 在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合。例如“文档1”经过分词,提取了20个关键词,每个...
  • Elasticsearch 使用一种称为 倒排索引 的结构,它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的文档列表。 例如,假设我们有两个文档,每个文档的 ...
  • 倒排索引结构

    千次阅读 2015-01-06 18:45:15
    简单总结:倒排索引它记录的是词,和词所存在的文档id。的所有列表。通过这种索引结构的存储方式,其查询速率可想而知。 什么叫搜索引擎? 很多朋友认为lucene就是搜索引擎,其实这是不对的。既然是搜索引擎,那肯定...
  • 从搜索引擎谈起 、倒排索引的基本概念 、倒排索引举例 、浅谈正排索引 、倒排索引的实现
  • 算法篇--倒排索引

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

    2021-05-07 14:44:24
    什么需要倒排索引 倒排索引,也是索引。 索引,初衷都是为了快速检索到你要的数据。 每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同...
  • 全文检索一般是查询包含某一或某些关键字记录,所以通过文档整体值建立的索引对提高查询速度是没有任何帮助的。为了解决这个问题,人们创建了一种新索引方法,这种索引方法就是倒排索引
  • 在各大搜索引擎中,输入关键字都可以找到我们想要的文章,还有InnoDB引擎中的全文索引,为什么能提高大量数据的检索,他们都有个共同的原因就是底层都是倒排索引算法。 我们先了解一些基本概念。 基本概念 文档 ...
  • 什么是倒排索引倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最...
  • ElasticSearch——倒排索引和正向索引

    千次阅读 2021-11-04 15:40:27
    ElasticSearch——倒排索引和正向索引 1、正向索引 正向索引 (forward index) 以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档 这种组织...
  • 什么是倒排索引

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

    2022-01-24 11:09:10
    索引是一种为了加快数据库查询的一种数据结构,是由一系列的存储在电脑磁盘上面的索引项构成的。 通过一些标识,来进行快速的查找数据 实际上,索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录。 ...
  • 倒排索引什么

    千次阅读 2019-03-04 00:11:34
    倒排索引什么 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最...
  • 搜索引擎最核心的技术, 倒排索引技术,倒排索引可能需要分成几篇文章才说得完,我们先会说说倒排索引的技术原理,然后会讲讲怎么用一些数据结构和算法来实现一个倒排索引,然后会说一个 索引器怎么通过 文档来生成...
  • 倒排索引处理文档

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

    千次阅读 2021-02-05 06:54:20
    前言最近在学习调研ElasticSearch,ES是一款热度较高的开源搜索服务器,能够提供近实时的数据全文检索功能,而实现检索功能一个其中较为重要的思想就是使用倒排索引,之所以成为倒排,与我们关系型数据库如Mysql的正...
  • Elasticsearch 中为什么选择倒排索引而选择 B 树索引前言为什么全文索引不使用 B+ 树进行存储全文检索正排索引倒排索引倒排索引如何存储数据FOR 压缩RBM 压缩倒排索引如何存储字典树(Tria Tree)FSTFSM构建 FST总结...
  • 将图的非线性结构和顶点的多维属性存储在倒排索引列表中的快速查询速度,并在多维网络上进行聚集查询(cuboid)。和交叉查询(crossboid)的算法在DBLP数据集上的实验即,该模型较GraphCube的查询效率更高,扩展性更...
  • ElasticSearch倒排索引详解

    千次阅读 2022-04-30 10:02:31
    概述 Lucene 作为 Apache 开源的...什么是倒排索引 搜索的核心需求是全文检索,全文检索简单来说就是要在大量文档中找到包含某个单词出现的位置,在传统关系型数据库中,数据检索只能通过 like 来实现。 例如需要在
  • ES简介及倒排索引

    千次阅读 2021-02-06 10:53:24
    ES的核心概念ES倒排索引 什么是ES? ES是Elasticsearch的简称,Elasticsearch是一个分布式可扩展的实时搜索和分析引擎,一个建立在全文搜索引擎 Apache Lucene™ 基础上的搜索引擎。Lucene只是一个框架,要充分利用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,808
精华内容 13,123
热门标签
关键字:

倒排索引数据结构是什么

数据结构 订阅