Elasticsearch 的倒排索引原理

🕵️‍♀️ Elasticsearch 的核心：倒排索引原理

Elasticsearch 是基于Apache Lucene库构建的，而倒排索引正是 Lucene 的基石。它彻底颠覆了传统数据库按行存储和查找的模式，实现了基于内容的快速定位。

1. 什么是倒排索引？

要理解倒排索引，我们先看传统的正排索引 (Forward Index)，即关系型数据库（如 MySQL）的索引：

在正排索引中，我们需要遍历文档内容（或至少索引的字段）来查找包含特定词语的文档。

倒排索引则采取了相反的逻辑：它不再根据文档 ID查找内容，而是根据“词条 (Term)”来查找它出现在哪些文档 ID中。

核心结构：词条字典与倒排列表

倒排索引由两大核心部分组成：

1. 词条字典 (Term Dictionary):存储了所有文档中出现过的、唯一的词条列表。这些词条通常经过排序，方便快速查找。
2. 倒排列表 (Posting List):对于词条字典中的每一个词条，都有一个与之关联的列表，记录了该词条在哪些文档中出现过。

2. 倒排索引的构建过程（数据写入）

当一个新文档被写入 Elasticsearch 时，它会经历一个称为分析 (Analysis)的过程，并最终构建成倒排索引的结构。

步骤 1: 分词 (Tokenization)

ES 使用分析器 (Analyzer)对文本字段进行处理。分析器通常包含三个阶段：

• 字符过滤器 (Character Filters):处理原始文本，例如删除 HTML 标签或将全角字符转为半角。
• 分词器 (Tokenizer):将处理后的文本拆分成独立的词条 (Tokens)。例如，将句子拆分成单词。
• 词条过滤器 (Token Filters):对词条进行标准化处理，例如：
  • 小写化 (Lowercasing):将 “Winter” 变为 “winter”。
  • 停用词过滤 (Stopword Removal):删除常见的、对搜索相关性贡献不大的词（如 “is”, “a”, “the”）。
  • 词干提取 (Stemming):将不同形式的单词还原为词根（如 “coming” 变为 “come”）。

示例：原始文档内容为"A quick Brown fox is running."

经过分析后，可能会生成以下词条：[quick, brown, fox, run]

步骤 2: 构建倒排列表

为每个生成的词条创建一个记录，记录该词条所在的文档 ID以及更多信息（如词频、位置）。

完整的倒排列表 (Full Inverted Index)通常包含以下关键信息：

查询速度的秘诀：在查询时，ES 只需要在排好序的词条字典中查找目标词条，然后直接获取对应的DocID 列表，而无需扫描任何文档内容。这使得查询速度比传统数据库快了几个数量级。

3. 查询过程（数据检索）

当用户发起一个查询（例如：查询包含 “quick fox” 的文档）时：

1. 查询分析：用户输入的查询字符串也被同样的分析器处理，生成查询词条：[quick, fox]。
2. 词条查找：ES 在倒排索引的词条字典中分别查找 “quick” 和 “fox”。
3. DocID 取交集/并集：
   • 查找 “quick” 对应的 DocID 列表 (Posting List A)。
   • 查找 “fox” 对应的 DocID 列表 (Posting List B)。
   • 如果使用AND(bool/must)，则取 A 和 B 的交集，得到最终符合条件的文档 ID 集合。
4. 计算相关性评分 (_score)：使用BM25 算法等评分模型，结合词频 (TF)、逆文档频率 (IDF) 等因素，计算每个匹配文档与查询的相关性分数。
5. 排序与返回：根据计算出的_score对文档进行排序，将得分最高的文档及其内容返回给用户。

4. 倒排索引 vs. 正排索引

在 Elasticsearch 中，倒排索引用于搜索，而正排索引（主要以Doc Values的形式存储）则用于排序、聚合和脚本操作。

倒排索引是 Elasticsearch 成为世界领先的全文搜索引擎的关键。它用空间（额外的索引结构）换取了时间（极快的搜索速度）。