ElasticSearch（es）倒排索引

目录

一、ElasticSearch

二、倒排索引 

1. 正向索引

2. 倒排索引

具体细节

1. 文档分析

2. 索引构建

3. 索引存储

4. 词条编码

5. 索引优化

6. 查询处理

示例

总结

3. 正向和倒排

 三、总结

倒排索引的基本概念

为什么倒排索引快

---

一、ElasticSearch

        Elasticsearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎，基于RESTful web接口。Elasticsearch是用Java语言开发的，并作为Apache许可条款下的开放源码发布，是一种流行的企业级搜索引擎。Elasticsearch用于云计算中，能够达到实时搜索，稳定，可靠，快速，安装使用方便。官方客户端在Java、.NET（C#）、PHP、Python、Apache Groovy、Ruby和许多其他语言中都是可用的。根据DB-Engines的排名显示，Elasticsearch是最受欢迎的企业搜索引擎，其 次是Apache Solr，也是基于Lucene

演示：京东，淘宝

Lucene是一个Java语言的搜索引擎类库,是Apache公司的顶级项目，由DougCutting于1999年研发。

官网地址: https:// lucene.apache.org/

重要特性：

• 1、分布式的实时文件存储，每个字段都被索引并可被搜索
• 2、实时分析的分布式搜索引擎
• 3、可以扩展到上百台服务器，处理PB级结构化或非结构化数据

二、倒排索引 

倒排索引的概念是基于MySQL这样的正向索引而言的。

1. 正向索引

那么什么是正向索引呢？例如给下表（tb_goods）中的id创建索引：

如果是根据id查询，那么直接走索引，查询速度非常快。

但如果是基于title做模糊查询，只能是逐行扫描数据，流程如下：

• 1）用户搜索数据，条件是title符合 "%手机%"
• 2）逐行获取数据，比如id为1的数据

• 3）判断数据中的title是否符合用户搜索条件
• 4）如果符合则放入结果集，不符合则丢弃。回到步骤1

逐行扫描，也就是全表扫描，随着数据量增加，其查询效率也会越来越低。当数据量达到数百万时，就是一场灾难。

2. 倒排索引

倒排索引中有两个非常重要的概念：

文档（ Document ）：用来搜索的数据，其中的每一条数据就是一个文档。例如一个网页、一个商品信息

词条（ Term ）：对文档数据或用户搜索数据，利用某种算法分词，得到的具备含义的词语就是词条。例如：我是中国人，就可以分为：我、是、中国人、中国、国人这样的几个词条

创建倒排索引是对正向索引的一种特殊处理，流程如下：

1. 将每一个文档的数据利用算法分词，得到一个个词条
2. 创建表，每行数据包括词条、词条所在文档id、位置等信息
3. 因为词条唯一性，可以给词条创建索引，例如hash表结构索引

如图：

倒排索引的搜索流程如下（以搜索"华为手机"为例）：

• 1）用户输入条件 "华为手机" 进行搜索。
• 2）对用户输入内容分词，得到词条： 华为 、 手机 。
• 3）拿着词条在倒排索引中查找，可以得到包含词条的文档id：1、2、3。
• 4）拿着文档id到正向索引中查找具体文档。

如图：

虽然要先查询倒排索引，再查询倒排索引，但是无论是词条、还是文档id都建立了索引，查询速度非常快！无需全表扫描。

---

具体细节

Elasticsearch 的底层原理涉及到多个层面，包括文档分析、索引构建、存储和查询处理等方面。下面详细解释这些方面的具体实现：

1. 文档分析

• 分析器(Analyzer): 当文档被索引时，它们会被传递给一个分析器，分析器负责将文档分解成一系列的词条(terms)。分析器通常包括分词器(Tokenizers)和过滤器(Token Filters)。
  • 分词器: 将文本分割成单词或符号。
  • 过滤器: 对分词结果进行处理，如大小写转换、去除停用词等。

2. 索引构建

• 词条(Terms): 从文档中提取出来的关键词。
• 文档ID(Document IDs): 每个文档都有一个唯一的ID。
• 倒排列表(Posting Lists): 对于每个词条，Elasticsearch维护了一个文档ID列表，其中包含了包含该词条的所有文档的ID。

3. 索引存储

Elasticsearch 使用 Lucene 作为其底层索引存储层。Lucene 使用倒排索引结构，主要包括以下几个组成部分：

• 词条字典(Terms Dictionary): 存储所有唯一词条的有序列表。
• 倒排文件(Postings File): 存储词条对应的文档ID列表。
• 频率文件(Frequency File): 存储每个词条在每个文档中的出现次数。
• 位置文件(Position File): 存储每个词条在文档中的位置信息，这对于短语查询非常重要。

4. 词条编码

词条在索引中通常是按照字典顺序排列的，以便快速定位。Lucene 使用多种编码技术来减少存储空间的需求，比如：

• 前缀编码(Prefix Coding): 利用词条间的相似性来减少存储需求。
• 可变字节编码(VByte Encoding): 一种用于整数编码的方法，可以有效地压缩文档ID列表。
• Gamma 编码: 用于编码整数的一种方式，特别适用于文档ID这样的非负整数。

5. 索引优化

• 合并(Merging): Lucene 会定期合并较小的索引片段，以减少碎片化。
• 缓存: Elasticsearch 使用多种缓存策略来加速查询，包括过滤器缓存(Filter Cache)、字段数据缓存(Field Data Cache)等。
• 段(Segments): Lucene 将索引划分为多个段，每个段是一个独立的倒排索引。这有助于减少锁的竞争，提高并发性能。

6. 查询处理

• 查询解析: 当用户提交查询时，Elasticsearch 首先解析查询，将其转换为 Lucene 可以理解的形式。
• 倒排列表获取: 根据查询中的词条，Elasticsearch 从索引中获取相应的倒排列表。
• 合并结果: 如果查询包含多个词条，则需要合并这些词条对应的文档ID列表。
• 评分与排序: 根据相关性评分算法对结果进行评分，并根据评分排序。
• 结果返回: 最终返回排序后的文档列表给用户。

示例

假设我们有两个文档：

• 文档1: "The quick brown fox jumps over the lazy dog."
• 文档2: "A quick movement of the enemy will jeopardize six gunboats."

对于词条 "quick"，倒排列表将是 [1, 2]，表示文档1和文档2都包含词条 "quick"。

当用户搜索 "quick" 时，Elasticsearch:

1. 查找词条 "quick" 的倒排列表 [1, 2]。
2. 返回包含这两个文档ID的结果集。

总结

        通过上述机制，Elasticsearch 能够高效地处理各种复杂的全文搜索请求。索引构建时采用的分析器确保了文档能够被正确地拆解为词条，而倒排索引的设计则允许快速定位包含特定词条的文档集合。同时，通过多种优化技术和缓存策略，Elasticsearch 保证了高性能和高可用性。

3. 正向和倒排

那么为什么一个叫做正向索引，一个叫做倒排索引呢？

• 正向索引是最传统的，根据id索引的方式。但根据词条查询时，必须先逐条获取每个文档，然后判断文档中是否包含所需要的词条，是根据文档找词条的过程。
• 而倒排索引则相反，是先找到用户要搜索的词条，根据词条得到保护词条的文档的id，然后根据id获取文档。是根据词条找文档的过程。

正向索引：

优点：

• 可以给多个字段创建索引
• 根据索引字段搜索、排序速度非常快

缺点：

• 根据非索引字段，或者索引字段中的部分词条查找时，只能全表扫描。

倒排索引：

优点：

• 根据词条搜索、模糊搜索时，速度非常快

缺点：

• 只能给词条创建索引，而不是字段
• 无法根据字段做排序

 三、总结

        Elasticsearch (ES) 使用倒排索引来加速文本的搜索速度。倒排索引之所以高效，主要是因为它改变了数据的组织方式，使得查询操作可以快速完成。

倒排索引的基本概念

        传统的正向索引是按照文档到词的方式存储的，即每个文档记录了它包含哪些词语。而倒排索引则反过来，它是按照词到文档的方式存储的，即每个词对应了包含该词的所有文档列表。

为什么倒排索引快

倒排索引之所以能够实现快速搜索，主要得益于以下几个方面：

1. 减少扫描范围：

   • 倒排索引将查询从文档到词的模式转变为词到文档的模式。这意味着当我们搜索一个词时，可以直接定位到包含这个词的所有文档，而无需遍历整个文档集合。

2. 高效的数据结构：

   • 词条按字典序排序，并且使用高效的数据结构（如跳表、B树等）来存储，这使得查找词条变得非常迅速。
   • 倒排列表使用诸如可变字节编码、Gamma 编码等编码技术来压缩文档ID列表，减少存储空间的同时也提升了读取速度。

3. 缓存机制：

   • Elasticsearch 使用多种缓存机制，如过滤器缓存、字段数据缓存等，来缓存常用数据，从而避免频繁地从磁盘读取数据，显著提升查询性能。

4. 并发处理：

   • Elasticsearch 可以在多个节点上并行处理查询请求，利用集群中的多台机器来加速查询过程。

5. 优化的搜索算法：

   • Elasticsearch 使用高效的搜索算法来处理复杂的查询条件，例如使用布尔逻辑运算来组合不同的查询条件，以及利用跳表等数据结构来减少不必要的文档比较。

6. 索引合并与优化：

   • Lucene 会定期合并较小的索引片段，以减少碎片化，优化索引结构，从而提高查询效率。

7. 内存映射：

   • Elasticsearch 和 Lucene 会利用内存映射技术将索引文件映射到内存中，这使得数据可以直接在内存中操作，大大加快了访问速度。

        综上所述，倒排索引的设计和实现通过减少不必要的数据访问、利用高效的数据结构和算法、优化存储格式以及利用缓存和并发处理等手段，实现了非常高的搜索性能。这些特性共同作用，使得Elasticsearch能够在大规模数据集中实现快速准确的全文搜索。