0


大数据-182 Elasticsearch - 原理剖析 数据结构-倒排索引、SkipList 跳表

点一下关注吧!!!非常感谢!!持续更新!!!

目前已经更新到了:

  • Hadoop(已更完)
  • HDFS(已更完)
  • MapReduce(已更完)
  • Hive(已更完)
  • Flume(已更完)
  • Sqoop(已更完)
  • Zookeeper(已更完)
  • HBase(已更完)
  • Redis (已更完)
  • Kafka(已更完)
  • Spark(已更完)
  • Flink(已更完)
  • ClickHouse(已更完)
  • Kudu(已更完)
  • Druid(已更完)
  • Kylin(已更完)
  • Elasticsearch(正在更新…)

章节内容

上节我们完成了如下的内容:

  • Elasticsearch 索引文档存储段合并
  • Elasticsearch 存储文件详解

在这里插入图片描述

Elasticsearch 数据结构

倒排索引

概念概述

倒排索引是全文检索的根基,理解了倒排索引之后才能算是入门了全文检索的领域,倒排索引的概念很简单,也很好理解。

在这里插入图片描述
倒排索引由两部分组成,所有独立的词列表称为索引,词对应的一系列表统称为倒排表。(《信息检索》)

  • 索引表,叫 Terms Dictionary,是由于一系列的Term组成的
  • 倒排表,称 Posting List,即是由所有的Term对应的Postings组成的

如果存储一个倒排索引数据?选择哪种数据结构?

全文搜索引擎通常是需要存储大量的文本,不仅仅是Postings可能会是非常巨大,同样Dictionary的大小极可能也是非常庞大,真正的搜索引擎的倒排索引实现都极其复杂,因为它直接影响了搜索性能和功能。

在这里插入图片描述
Lucene的实现非常高级,它的关键特性是能够将整个倒排索引序列化存储在磁盘上,同时它必须是能够满足快速度写的需求,Lucene为了极致的搜索体验,引用多种数据结构和算法。

Lucene索引文件分析

Lucene 是一个基于 Java 的开源全文检索库,由 Doug Cutting 于 1999 年创建。Lucene 的核心功能是为应用程序提供高效的文本索引和搜索能力,它可以帮助开发者构建快速、可扩展的全文搜索功能。Lucene 本身是一个低级库,并不提供图形界面或高级应用功能,它更多是作为一个底层工具被集成到其他系统或框架中。

  • 索引(Index): 索引是 Lucene 的核心组件之一,它是为了加速搜索过程而创建的数据结构。Lucene 会将文档中的文本分解为称为 “倒排索引”(inverted index)的形式。倒排索引类似于书的索引页,它列出了每个关键字在文档中的位置。这样,当用户搜索特定的词或短语时,Lucene 可以快速查找到包含该词的文档。
  • 文档(Document): 在 Lucene 中,文档是搜索和索引的基本单元。每个文档由若干字段(Field)组成,字段可以包含不同类型的数据,比如标题、内容、日期等。文档在 Lucene 中通常与数据库中的一条记录相对应。
  • 字段(Field): 字段是文档的组成部分,每个字段可以存储不同类型的数据,比如字符串、数字、日期等。字段可以指定是否被索引,是否被存储,以及是否可以被搜索等。
  • 分词器(Analyzer): 分词器负责将输入的文本分解为词汇单元(Token),这些词汇单元是 Lucene 用来索引和搜索的基础。例如,对于中文文本,分词器需要将连续的字符切分为有意义的词汇;对于英文文本,它会移除标点符号、转换大小写等。不同的语言和需求可能需要不同的分词器。
  • 查询(Query): Lucene 提供了多种类型的查询(Query),允许用户构建复杂的搜索逻辑,比如布尔查询(Boolean Query)、短语查询(Phrase Query)、范围查询(Range Query)等。查询的作用是通过匹配倒排索引来查找符合条件的文档。
  • 评分(Scoring): Lucene 对搜索结果进行评分,根据文档与查询的匹配程度返回一个相关性得分(Relevance Score)。默认情况下,Lucene 使用 TF-IDF(词频-逆文档频率)算法来计算得分,确保更相关的文档排在搜索结果的前面。
  • 索引器(Indexer): 索引器负责将文档中的数据转化为倒排索引。Lucene 的索引过程包括将文档分解为词汇单元,过滤掉不必要的词(如停用词),然后将有意义的词汇存入倒排索引中。索引器还负责定期优化索引以提高搜索效率。
  • 存储与合并(Storage and Merging): Lucene 的索引存储是分段式的,每次索引操作会创建新的段(segment)。Lucene 会定期合并这些段以减少碎片、提高性能。段是不可变的,这样的设计使得 Lucene 能够高效地进行并发搜索和索引操作。

在这里插入图片描述
Lucene将索引文件拆分为了多个文件,这里仅讨论倒排索引的部分:

  • tip:Lucene把用于存储Terms的索引文件叫Terms Index,它的后缀是:tip
  • doc:把Postings信息分别存储在doc,分别记录Postings的DocId信息和Term词频信息
  • tim:Terms Dictionary的文件后缀称为tim,它是Term与Positings的关系纽带,存储了Term和其对应的Postings文件指针

在这里插入图片描述

  • Term Dictionary:把Term按字典排序,然后用二分法查找Term(存在磁盘)在Lucene,Terms Dictionary被存储在 tim 文件上,当一个Segment的文档数量越来越多的同时 Dictionary 的词汇也会越来越多,那查询效率必然也会越来越慢。如果有一个很好的结构也为Dictionary构建一个索引,将Dictionary的索引进一步压缩,这就是后来的Terms Index(.tip)。
  • TermIndex:是Term Dictionary的索引,存Term的前缀,和与该前缀对应的Term Dictionary中的第一个Term的Block的位置,找到这个第一个Term后会再往后顺序查找,直到找到目标Term(存在内存)。

小节一下:

  • 通过Terms Index(tip)可以快速的在Terms Dictionary(tim)中找到你想要的Term,以及它对应的Postings文件指针(指向doc)
  • Terms Index 实际上一个或者多个FST组成的,Segment上每个字段都有自己的一个FST(FST Index)记录在tip上(FST类似一种TRIE树)

Trie

Trie被称作字典树、前缀树(Prefix Tree)、单词查找树:Trie搜索字符串的效率主要跟字符串的长度有关(O(len(单词长度)))
使用Trie存储: cat->1,dog->2,doggy->3,does->4,cast->5,add->6,这六个单词时,如下图:

在这里插入图片描述
Tire时间复杂度:O(len(key))
FST,不但能共享前缀还能共享后缀,不但能判断查找的Key是否存在,还能给出响应的输入output,它在时间复杂度和空间复杂度上都做了最大程度的优化,使得Lucene能够将Term Index完全加载到内存,快速的定位Term找到响应的output(posting倒排列表)

SkipList应用

概念概述

假设某个索引字段中有sex、address字段,检索条件为:sex=‘female’ and address=‘北京’

  • 给定查询过滤条件 sex='female’的过程就是先从Term index找到female在Term Dictionary的大概位置
  • 再从 Term Dictionary里精确的找到 Female 这个Term,然后得到一个posting list或者一个指向posting list位置的指针
  • 查询 address=‘北京’ 的过程类似的,得到一个posting list或者一个指向posting list位置的指针

需要计算出 sex=‘female’ and address=‘北京’ 就是把两个 positing list做一个与合并。
ES中使用SkipList数据结构,同时遍历sex和address的posting list,相互skip。

有序集合计算交集

list1: {1,2,3,4,20,21,50,60,70}
list2: {50,70}

求交集 拉链法

两个指针指向首元素,比较元素的大小:

  • 如果相同,放入结果集,随意移动一个指针
  • 否则,移动值较小的一个指针,直到队尾

这种方法的优势:

  • 集合中的元素最多被比较一次,时间复杂度O(N)
  • 多个有序集合可以同时进行

求交集 跳表SkipList

有序链表集合求交集,跳表是最常用的数据结构,它可以将有序集合求交集的复杂度有O(N)降至O(Log(N))
如果使用拉链法,会发现每个元素都要被比对但是其中很多都是无效比对,时间复杂度为O(N),所谓跳表可以把时间复杂优化至LogN,就是因为跳表可以跳过很多无效的对比。

在这里插入图片描述
跳表的实现:
在这里插入图片描述
搜索的过程:

  • 从顶层链表的首元素开始,从左往右搜索,直到找到一个大于或者等于目标的元素,或者到达当前层链表的尾部
  • 如果该元素等于目标元素,则表明该元素已经被找到
  • 如果该元素大于目标元素或已经到达链表的尾部,则退回到当前层前一个元素,然后转入下一层进行搜索

添加元素,随机决定新添加元素的层数:
在这里插入图片描述
删除元素,修改跳表的有效层数:
在这里插入图片描述


本文转载自: https://blog.csdn.net/w776341482/article/details/143108876
版权归原作者 武子康 所有, 如有侵权,请联系我们删除。

“大数据-182 Elasticsearch - 原理剖析 数据结构-倒排索引、SkipList 跳表”的评论:

还没有评论