倒排索引

Elasticsearch 是一个基于 Lucene 构建的分布式搜索引擎，它能够以非常高的效率执行全文搜索查询。在 Elasticsearch 的核心，倒排索引（Inverted Index） 是最重要的数据结构之一。理解倒排索引的原理对于理解 Elasticsearch 的搜索性能至关重要。

什么是倒排索引？

倒排索引是一种用于快速查找包含特定词汇的文档的数据结构。它类似于一本书的索引页，但结构上是“倒过来”的，因此得名。

正向索引 vs. 倒排索引

0 正向索引（Forward Index） 是基于文档构建的，记录了每个文档中包含的词汇。对于每个文档，你可以找到它包含哪些词汇。

倒排索引（Inverted Index） 是基于词汇构建的，记录了每个词汇在哪些文档中出现。对于每个词汇，你可以迅速找到包含它的文档列表。

例如，假设有三篇文档如下：

“Elasticsearch 是一个分布式搜索引擎”

“分布式系统可以提供高可用性”

“搜索引擎使用倒排索引进行高效搜索”

正向索引会记录每个文档中有哪些词：

Doc1: ["Elasticsearch", "是", "一个", "分布式", "搜索", "引擎"]

Doc2: ["分布式", "系统", "可以", "提供", "高", "可用性"]

Doc3: ["搜索", "引擎", "使用", "倒排索引", "进行", "高效", "搜索"]

1

2

3

而倒排索引则会记录每个词在哪些文档中出现：

"Elasticsearch": [1]

"分布式": [1, 2]

"搜索": [1, 3]

"引擎": [1, 3]

"倒排索引": [3]

1

2

3

4

5

这样，当你查询一个词汇时，比如 “搜索”，Elasticsearch 可以通过倒排索引立即返回它出现在 Doc1 和 Doc3 中，而不需要遍历所有的文档。

倒排索引的构建

在 Elasticsearch 中，文档首先会被分析和处理，然后生成倒排索引。其过程大致如下：

文档分词：每个文档都会经过 分析器（Analyzer） 的处理，分析器负责将文档的文本分解成词项（terms）。例如，句子 “Elasticsearch 是一个分布式搜索引擎” 可能被分解为 [“elasticsearch”, “分布式”, “搜索”, “引擎”]。

标准化和过滤：分词后，分析器通常会进行进一步的处理，例如将所有词项转为小写、删除停用词（如 “是”, “一个”）等。这一步使得倒排索引更具可查询性。

构建倒排列表：倒排索引将每个词项与它所出现的文档ID关联。词项是倒排索引的键，文档ID列表则是值。对于每个词项，Elasticsearch 还可能记录一些额外信息，如词频（TF）和词项在文档中的位置（用于短语匹配和邻近查询）。

倒排索引的结构

倒排索引的核心部分可以分为以下几个组成部分：

词汇表（Term Dictionary）：词汇表保存了所有被索引的词项，通常是以字典形式存储。通过这个表，Elasticsearch 可以快速定位某个词项是否存在。

倒排列表（Posting List）：对于每个词项，倒排列表记录了所有包含该词项的文档ID。倒排列表还可以包含附加信息，如：

词项频率（Term Frequency, TF）：记录该词项在文档中出现的次数。

文档频率（Document Frequency, DF）：记录该词项在整个索引中出现的文档总数。

位置（Position）：词项在文档中的位置，用于支持短语和邻近查询。

例如，对于词项 “搜索”，倒排列表可能是这样的：

"搜索": [(Doc1, Position: 5), (Doc3, Position: 3, 7)]

1

这意味着 “搜索” 在文档1中出现过，并且在文档3中出现过两次，分别位于位置3和7。

倒排索引的查询原理

倒排索引使得 全文搜索查询 变得非常高效。例如，当你向 Elasticsearch 发起搜索请求时，比如查找包含词项 “搜索引擎” 的文档，Elasticsearch 可以执行以下步骤：

查找词项：Elasticsearch 首先在词汇表中查找 “搜索” 和 “引擎” 这两个词项，找到它们的倒排列表。

合并倒排列表：Elasticsearch 会合并这两个词项的倒排列表，找到同时包含 “搜索” 和 “引擎” 的文档。由于每个词项都与它的文档ID相关联，合并列表的操作非常快速。

计算相关性：在找到匹配的文档后，Elasticsearch 会根据一些算法（如 TF-IDF 或 BM25）对文档进行评分，衡量它们与查询的相关性。这个步骤基于词项频率、文档频率等信息，最终返回最相关的文档。

倒排索引的优势

快速检索：倒排索引的结构使得对于某个词项的检索速度极快，尤其在海量文档中，查询性能仍能保持在毫秒级别。

低内存占用：虽然倒排索引记录了大量的词项和文档ID，但通过压缩算法和优化的数据结构，倒排索引可以保持较低的内存使用率。

支持复杂查询：倒排索引不仅支持简单的关键词查询，还支持短语、前缀、邻近查询等复杂的搜索条件。

测试分析

Elasticsearch使用一种称为倒排索引的结构，它适用于快速的全文搜索。一个倒排索引由文档中所有不重复的列表构成，对于其中每个词，有一个包含的它的文档列表。

假设我们有两个文档，每个文档的内容如下：

1. The quick brown fox jumped over the lazy dog

2. Quick brown foxes leap over lazy dogs in summer

1

2

要创建倒排索引，首先要将每个文档内容拆分成单独的词，创建一个包含所有不重复词条的排序列表，然后列出每个词条出现在哪个文档，结果如下图所示：

现在我们想要搜索 quick down，我们只需要查找包含每个词条的文档：

两个文档都匹配，但是第一个文档比第二个匹配度更高，如果我们使用仅计算匹配条数量的简单相似性算法，那么对于我们查询的相关性来讲，第一个文档比第二个文档更佳。

读写流程

创建文档

向Elasticsearch中添加一个文档对象，由于ES是分布式集群并且底层设计了一个索引由众多Shard分片，所以添加文档时需要确定该文档属于哪个分片，确定规则为：

shard = has(routing) % number_of_primary_shards

1

routing 是一个可变值，默认是文档的ID，也可以设置成一个自定义的值

routing 通过hash函数生成一个数字，然后这个数字再除以number_of_primary_shards（主分片的数量）后得到余数，这个分布在0到number_of_primary_shards - 1 之间的余数，就是我们寻求的文档所在分片的位置。

写文档流程

以官网的例子进行分析，从图中可看出一个集群由三个节点组成，有两个分片，两个副本。

写操作必须在主分片上面完成之后，才能被复制到其他节点作为分片副本，新建、索引和删除请求都是写操作。

客户端向Master发送写入请求，该节点作为协调节点

根据文档的_id确定分片，图中请求文档属于分片0，协调节点请求转到节点的主分片

在节点3上执行请求，成功之后，节点3根据副本数将请求并行转到副本分片对应节点，一旦副本分片执行完成，都向节点3报告成功，节点3将协调节点报告成功，协调节点向客户端报告成功

读文档流程

一个搜索请求必须询问请求的索引中所有分片的某个副本来进行匹配，假设一个索引由5个主分片，每个主分片有一个副本分片，共10个分片，一次搜索请求会由5个分片来共同完成，他们可能是主分片，也可能是副分片。也就是说，一次搜索请求只会命中所有分片副本中的一个。

一次检索流程主要分为两个阶段：

Query阶段

Fetch阶段

Query阶段

客户端发送Search请求到Node3

Node3将查询请求转发到索引的每个主分片或副分片中

每个分片在本地执行查询，并使用本地的Term/DocumentFrequency信息进行打分，添加结果到大小 from+size的本地优先队列中

每个分片返回各自优先队列中所有文档的ID和排序值给协调节点，协调节点合并这些值到自己的优先队列中，产生一个全局排序后的列表

Fetch阶段

协调节点相关Node发送GET请求

分片所在节点向协调节点返回数据

协调节点等待所有文档数据被取得，然后返回给客户端

分片所在节点在返回文档时，处理有可能出现的 _source 字段和高亮参数