ES倒排索引的原理

倒排索引（Inverted Index）是 ES 实现全文搜索的核心结构，它的原理是：将“文档 → 词”的关系倒过来存储为“词 → 文档列表”。

---

你可以从以下几个方面来讲，结构清晰、面试官也容易认可：

1. 文本分词（Tokenize）
   文档在写入 ES 时首先会通过 Analyzer（分析器）进行处理，包括：

   • 分词（把文本拆分成一个个词项）
   • 小写化
   • 停用词过滤
     处理后的每个词叫 Term。

2. 建立倒排表（Posting List）
   ES 将 “Term” 作为 key，把所有包含该 Term 的文档信息存成一个列表，叫 倒排列表。
   列表中通常包含：

   • 文档 ID
   • 词频（TF）
   • 词出现位置
   • 词出现的偏移量（用于高亮）

   示例：
   term = "search"
   posting list = [doc1, doc5, doc9...]

3. 索引结构（Inverted Index）
   所有 term → posting lists 就组成倒排索引，这样查找一个词变成了：
   O(1) 找 term，O(n) 读取 posting list
   不需要扫描所有文档。

4. 搜索过程
   例如查 “分布式 搜索”：

   • 先找到 term1 的 posting list
   • 再找到 term2 的 posting list
   • 对两个 posting list 做交集/并集
   • 按 TF-IDF/BM25 排序
   • 返回结果

5. 优势

   • 查询速度极快
   • 天然支持全文检索
   • 支持复杂查询（短语、前缀、模糊等）

ES 倒排索引的数据结构

一、倒排索引由两部分核心结构组成：Term Dictionary + Posting List

1. Term Dictionary（词典）
   本质是一个按字典序排序的所有 term 的集合。
   常用的数据结构是：

   • FST（有限状态机）
   • 或 B+Tree（用于磁盘索引查找）

   作用：快速找到某个 term 所对应的倒排列表的位置。

2. Posting List（倒排列表）
   对应每个 term 的文档记录链表，包含：

   • docID（文档 ID）
   • TF（词频）
   • 位置信息（position）
   • 偏移量（offset，用于高亮）
   • payload（可能存额外信息）

   Posting List 是压缩存储的（如 VInt、FST 压缩、跳表等）。

---

二、倒排列表内部的数据结构

一个 term 的倒排列表典型结构如下（文字描述版）：

• Term: "search"
  • Doc1
    词频: 3
    出现位置: 5, 18, 57
  • Doc5
    词频: 1
    出现位置: 12
  • Doc9
    词频: 2
    出现位置: 8, 44

倒排列表 docID 是严格递增存储，并且使用 跳表（skip list） 加速大范围跳跃。

---

三、为什么需要跳表（Skip List）？

Posting List 可能非常大，为了避免逐个 docID 扫描，ES 使用跳表节点，包含：

• 跳跃到下一个 doc 块的指针
• 当前块的最大 docID
• 便于快速求交集、并集、短语匹配

这提升搜索性能。

---

四、倒排索引存储是“段式（segment）”

每次写入 ES，实际是：

• 文档写入一个新 segment
• segment 内包含自己的 Term Dictionary + Posting Lists
• 后台合并时把多个 segment 合为一个更大的 segment

好处：写入不需要锁整库，查询合并多个 segment 结果即可。

---

五、总结版（你可以用来背）

倒排索引的数据结构是：
Term Dictionary（FST 存储）负责快速查 term → Posting List 地址；
Posting List 记录每个 term 出现在哪些文档、出现次数、位置等，并通过跳表加速查询；
所有倒排结构以 segment 为单位存储。

ES 的底层索引机制的“深度版本”

==================================== 一、ES 底层不是自己造轮子，而是完全基于 Lucene

Elasticsearch 所有搜索、索引、倒排结构全部由 Lucene 完成。
ES 做的只是：

• 分布式（shard、replica）
• 文档路由
• REST API
• 元数据管理

底层全部是 Lucene 的 Segment + Inverted Index。

因此下面所有内容都是 Lucene 内部结构，即 ES 的真实底层。

---

二、最核心概念：Segment（段）

Segment 是 ES 索引的最小存储单元，底层就是一堆不可变文件。

每次写入 ES：

• 文档先写入内存 buffer
• 达到阈值后 flush 出一个新的 segment
• segment 永不修改，只能合并为更大的 segment

所以 ES 索引目录中，会看到一堆文件，比如：

• _0.si
• _0.cfs
• _1.si
• _1.cfs
  ……

每个 segment 内部包含：

1. 倒排索引（inverted index）
2. 正排索引（stored fields）
3. DocValues（列式存储）
4. posting list + skip list
5. Term Dictionary（FST）
6. norms、positions、payloads
7. live docs（删除标记）

下面逐个解释底层数据结构。

==================================== 三、倒排索引结构（Inverted Index）

倒排索引由 两大核心结构组成：

1. Term Dictionary（词典）
2. Posting List（倒排列表）

---

1. Term Dictionary（词典）——FST 存储

---

Lucene 中的所有 term（按字典序排序）存储在一种压缩自动机结构：
FST（Finite State Transducer）有限状态机

特点：

• 按字典序压缩相邻词（pre、prefix、preload 省空间）
• 能非常快地做前缀查找、模糊匹配
• 每个 term 对应一个指针（offset） → posting list 文件中位置

你可以理解为：

Term → （FST） → posting list 文件 offset

---

1. Posting List（倒排列表）

---

每个 term 的倒排列表中保存：

• docID（压缩存储）
• TF（term frequency）
• position（词在文档中的位置）
• offset（偏移量，用于高亮）
• payload（额外自定义内容）

倒排列表存储在 .doc, .pos, .pay 文件中（或 cfs 合并包中）。

压缩方式：

• docID 使用 delta + varint 编码
• position 同样 delta + varint
• 均是紧凑的序列

---

1. Skip List（跳表）

---

当 posting list 很大时（比如几百万文档），按序遍历太慢，Lucene 在倒排列表中构建三级跳表：

• 第三级：超大跨度
• 第二级：中等跨度
• 第一级：小跨度

结构类似：
每隔 n 个 docID 建一个跳点，记录：

• docID
• 对应的字节偏移
• 对应的 position offset
• payload offset

这样做：交集查询不需要扫描全列表，而是跳跃式查找。

==================================== 四、Term 元信息（norms、frequency、positions）

Lucene 为每个字段存储一些 scoring 信息：

1. norms
   存储：

   • 字段长度
   • boost 值（默认 1）
     用于 BM25 评分。

2. frequency（TF）
   一个 term 在一个 doc 中出现次数。

3. positions
   term 在文档中出现的位置。
   用于：

   • phrase query
   • proximity query

4. offsets
   term 在文本中的字符偏移，用于高亮。

==================================== 五、Stored Fields（正排存储）

倒排索引用于 “term → doc”，
正排用于 “doc → 原始字段”。

例如用户查询时返回原始 JSON，需要从 stored fields 中取。

底层数据结构：

• 按 docID 顺序存储
• 每个 doc 一个 block
• 默认使用 LZ4、ZSTD 压缩

文件：*.fdt（data） 和 *.fdx（index）

==================================== 六、DocValues（列存储，用于聚合、排序）

DocValues 是 Lucene 的 “列式存储”，本质是按列存：

• column1：所有 doc 的某字段值
• column2：所有 doc 的某字段值
  ……

存储格式：

• numeric：定长数组
• sorted：两个文件（value 列表、doc → ordinal 映射）
• sorted set：多值字段
• binary：字节序列

你可以把 DocValues 看成 Lucene 的 “列式数据库”。

聚合、排序都依赖 DocValues，不依赖倒排索引。

==================================== 七、Live Docs（删除标记）

Lucene 不会真正删除文档，只会：

• 在一个 bitmap 中标记删除
• 叫 live docs（.liv 文件）

当 segment merge 时才真正删除。

==================================== 八、Segment Merge（段合并）

因为 segment 不可变，每次删除、更新都会产生：

• 新 segment
• 老 segment 中 doc 标记为 deleted

后台 merge scheduler 会合并多个 segment：

merge 做的事：

1. 合并倒排索引
2. 合并正排
3. 合并 docvalues
4. 去掉 live docs 中删除的文档
5. 生成新的大 segment

合并使用 归并算法：

• 多个倒排一起按 term 顺序归并
• docID 重新排序
• 跳表重新生成

==================================== 九、整个查询过程的数据结构流程

例如搜索 "apple phone"：

1. 从 segment 读取 FST
2. 查 term "apple" → offset
3. 读取 posting list（压缩格式 + 跳表）
4. 查 term "phone" → offset
5. 读取 posting list
6. posting list 求交集（使用跳表加速）
7. 读取 norms、docvalues 计算 BM25
8. 从 stored fields 返回原始文档

==================================== 十、如果你要最简总结（核心原理浓缩）

• ES 底层就是 Lucene
• Lucene 的最基本单元是 segment
• segment 里是 FST + PostingList + SkipList + 正排 + DocValues
• 倒排索引是：
  term → (docID, positions, offsets...)
• 正排存原始 JSON
• DocValues 是列存，用于排序聚合
• 数据不可变，靠 merge 合并回收删除数据

为什么倒排索引能让搜索这么快？它到底快在什么地方？

==================================== 一、核心本质：把“查文档”变成“查词典”

传统搜索方法（比如数据库 LIKE %keyword%）：

• 需要扫描所有文档
• 每个文档都要逐字匹配
• 时间复杂度接近 O(N × 文档长度)

倒排索引的结构是：

term → posting list（包含所有文档 ID）

也就是说，只要能快速找到 term，接下来就能直接拿到所有相关文档。

本质变成：

查词 → 不查文档

而 term 的数量永远远小于文档内容数量。

---

二、真正让它“快”的四个关键技术

这是重点。

==================================== 关键点 1：Term Dictionary（FST）让查词是 O(1) 级速度

为了存储全部词项，Lucene 使用：

FST（有限状态自动机）

FST 特点：

• 以字典序压缩类似前缀（apple、app、apply）
• 查找 term 是按状态机跳转，不是逐字扫描
• 查一个词基本是常数时间（接近 O(1)）

传统数据库必须做字符串匹配，而 Lucene 直接：

term 进 FST → offset → posting list

因此一旦词找到，就立刻找到相关文档的位置。

---

关键点 2：Posting List（倒排列表）按 docID 排序 + 压缩 + 顺序读

posting list 有如下特点：

• 按 docID 从小到大排序
• 连续存储
• 使用 delta + varint 超高压缩
• 顺序读（磁盘/CPU 最友好）

为什么排序和顺序读很关键？

因为 CPU、磁盘都对顺序访问非常友好，高效到不需要随机磁盘 I/O。

例如：

docIDs: 100, 105, 130, 140...
存储成：

delta: 100, 5, 25, 10...

每个 delta 用 varint 编码可能只占 1 个字节！

这意味着一个 posting list 可能上百万文档却只有几 MB。

基本都能放进操作系统 PageCache，访问速度接近内存速度。

---

关键点 3：跳表（Skip List）让 posting list 交集速度极快

例如查询：
apple AND phone

需要求两个 posting list 的交集，交集操作通常复杂度高。
但 Lucene 对每个 posting list 都构建了多层 Skip List：

• 1 层：小间隔跳
• 2 层：大间隔跳
• 3 层：超大间隔跳

查找过程类似：

小 → 中 → 大跳，不过只按 docID 跳

所以：

上百万文档的 posting list 求交集，往往只需要几十到几百个跳跃。

这就是为何 Lucene 能在毫秒级执行复杂查询。

---

关键点 4：倒排索引是不可变结构 → 极致的读优化

倒排索引（segment）是 只读文件，不可修改。

优点：

• 数据结构可以为读性能完全优化
• 不需要加锁
• 可全部放入内存或 OS 缓存中
• 访问路径非常简单（纯字节读取）

相比传统数据库的 B+ 树：

• B+ 树每次更新都需要修改节点、重新平衡
• 读路径需要多层跳转
• 必须加各种锁

Lucene 完全避开了这些问题。

==================================== 三、把这一切综合起来，就出现“搜索极快”的效果

当你搜索 "apple mobile" 时，Lucene 的执行流程是：

1. FST 中找到 apple → O(1)
2. 读取 apple 的 posting list（顺序读 + 内存 cache）
3. 找到 mobile → O(1)
4. 读取 mobile 的 posting list
5. 使用跳表求交集
6. 用 DocValues / norms 做排序
7. 返回 topN

整个流程中：

• 没有扫描文档
• 没有字符串匹配
• 没有复杂锁
• 没有随机磁盘 I/O
• posting list 大部分在内存中
• 数据结构完全为搜索优化

整个查询只需要几毫秒，是可以理解的。

==================================== 四、一句直白总结（你可以拿来和别人讲）

倒排索引之所以快，是因为：

把文档内容预先切成词，并倒过来建索引，使得搜索只需要查词而不查文档；通过 FST、压缩、顺序读、跳表等结构把查词和求交集都变成近似 O(1) 的操作。