大数据-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，就是因为跳表可以跳过很多无效的对比。

跳表的实现：

搜索的过程：

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

添加元素，随机决定新添加元素的层数：

删除元素，修改跳表的有效层数：