Elasticsearch 倒排索引原理

候选人小林在面试时被问到："ES 的全文搜索为什么这么快？底层靠什么实现的？"

小林说："因为 ES 用了倒排索引。"

面试官追问："倒排索引的数据结构是什么样的？"

小林说："就是...文档和词的对应关系..."

面试官继续追问："那 Posting List 怎么存的？为什么 ES 的倒排索引能存几十亿文档还不爆内存？"

小林卡住了。

面试官又问："FST 是什么？Term Index 为什么能加速查询？"

小林彻底答不上来。

【面试官心理】这道题我是在探测候选人对搜索引擎核心数据结构的理解深度。知道"倒排索引"这个词的占 90%，能说出 Posting List 压缩算法的占 20%，能讲清楚 FST 的占 5%。能答到最后的，基本都有搜索引擎或者底层存储的开发经验。

一、正排索引 vs 倒排索引 🔴

1.1 直观类比

【直观类比】想象你要在一本书里找"HashMap"这个词出现了几次：

正排索引：翻到每一页，数这一页有没有 HashMap（逐页扫描）
倒排索引：先查书的索引目录，找到"HashMap"这个词条，上面写着"第 3, 15, 87, 203...页"（直接定位）

倒排索引的查询复杂度从 O(N) 降到了 O(1)（精确匹配）或者 O(log M)（范围查询，M 为词条数量）。

1.2 数据结构对比

正排索引（Forward Index）：

doc_1 → [term_1, term_2, term_3, term_1, term_5]
doc_2 → [term_2, term_4, term_1, term_6]
doc_3 → [term_1, term_3, term_7]

倒排索引（Inverted Index）：

term_1 → [doc_1, doc_2, doc_3]        # Posting List
term_2 → [doc_1, doc_2]
term_3 → [doc_1, doc_3]
term_4 → [doc_2]
term_5 → [doc_1]
term_6 → [doc_2]
term_7 → [doc_3]

1.3 追问链

第一层：概念理解 面试官问："倒排索引和正排索引的区别是什么？" 候选人答："文档到词的映射 vs 词到文档的映射..." 考察点：基本概念

第二层：数据结构 面试官追问："Term Dictionary、Term Index、Posting List 分别是什么？" 候选人答：...（P6 分水岭）考察点：底层数据结构理解

第三层：压缩算法 面试官追问："几十亿文档的 Posting List 怎么存？有哪些压缩算法？" 候选人答：...（P7 区分点）考察点：存储优化、工程实践

第四层：查询流程 面试官追问："ES 收到一个 match 查询，底层是怎么找到目标文档的？" 候选人答：... 考察点：全链路理解

二、倒排索引核心组件 🟡

2.1 三大组件

Lucene 的倒排索引由三个核心组件构成：

倒排索引
  ├── Term Dictionary（词字典）
  │     ├── 按字母顺序排列的所有词条
  │     └── 支持二分查找定位词条
  │
  ├── Term Index（词索引）
  │     ├── FST（Finite State Transducer，有限状态传感器）
  │     └── 用极小空间加速定位 Term Dictionary
  │
  └── Posting List（倒排表）
        ├── 每个词条对应的 DocID 列表
        ├── 支持跳表（Skip List）加速合并
        └── 支持压缩（FOR / Roaring Bitmap）

2.2 Term Dictionary 与 Term Index

Term Dictionary 就是把所有词条按字典序排列，支持二分查找。但问题是：如果词条有 10 亿个，二分查找需要 30 次 IO（log2(1e9) ≈ 30）。

Term Index 用 FST 在内存中构建一个前缀树，类似 Trie 树，但更紧凑：

查询 "inter"
FST 路径: in → ter
        ↓
直接跳转到 Term Dictionary 中 "inter" 开头的位置
IO 次数: 1 次

FST 的特点是：

空间占用极小：相同前缀共享节点，比 Trie 节省 50%~80% 空间
查询极快：只需沿着 FST 走完查询词的路径，就能定位到 Term Dictionary 的位置

📖 点击展开：FST 的构建过程

FST（Finite State Transducer）在 Lucene 中用于将词条映射到任意值（比如文档频率）。

构建过程：

将所有 Term 按字典序排序
从第一个 Term 开始，逐个插入 FST 节点
相同前缀合并，不同后缀作为新路径
每个终止节点存储一个"输出值"（如 postings 指针偏移量）

FST 的查询时间复杂度是 O(query_length)，与数据规模无关。

三、Posting List 压缩算法 🔴

3.1 Frame of Reference（FOR）

这是 ES 倒排索引最核心的压缩技术之一，面试中被追问的频率极高。

核心思想：相邻 docID 之间的差值（delta）比 docID 本身小得多，用差值存储可以大幅节省空间。

原始 docID 列表: [103, 2001, 5003, 7504, 12000, 25000, 50003]
差值编码:       [103, 1898, 3002, 2501, 4496,  13000, 25003]

103 → 1898 的差值，最大需要 12 bit（log2(25003) ≈ 15），而不是存储原始 docID 需要的 15 bit。

但这里还有优化空间：FOR 将差值按固定 bit 数（block = 128 个文档）分组，每组使用统一的 bit 宽度：

// FOR 压缩示意
int[] deltas = [103, 1898, 3002, 2501, ...]; // 128个差值
int maxDelta = max(deltas);                  // 比如 25003
int bitsNeeded = ceil(log2(maxDelta));       // 比如 15 bits
// 用 15 bits 存储每个差值，总共 128 * 15 / 8 = 240 bytes
// 原始存储需要 128 * 4 = 512 bytes
// 压缩率: 50%

3.2 Roaring Bitmap

ES 在处理"哪些文档匹配了这个 filter"时，使用 Roaring Bitmap 而不是 Posting List。它将 docID 按 65536（2^16）为区间分块：

docID 范围 0~65535:   Block 0 → Bitmap [0,0,1,1,0,1,...]（65536 bits = 8KB）
docID 范围 65536~131071: Block 1 → Bitmap [...]
...

为什么不用连续数组？

如果某个词只出现在 docID 1 和 1亿，那么需要存储 1亿个空位
Bitmap 用 2^16 个 bit（8KB）就能覆盖这个区间的所有文档，无论稀疏还是稠密

为什么不用 Roaring Bitmap 做所有 Posting List？

稠密 Posting List（如停用词"the"出现在 80% 文档中）用 Bitmap 更省空间
稀疏 Posting List（如长尾词只出现在 3 个文档中）用 FOR 压缩更省空间
ES 的策略：混合使用，小数据量用数组，大数据量用 Bitmap

💡

ES 7.x 的 postings_format 默认使用 PLiB(compressed_lz4)，底层是 FOR + Roaring Bitmap 的组合。Lucene 的工程师在 2014 年做过实验：对于 10 亿文档的索引，这套压缩方案可以将 Posting List 空间从 80GB 压缩到 12GB。

四、跳表加速合并 🟡

4.1 布尔查询的 Posting List 合并

当执行 must 查询时，ES 需要合并多个 Posting List：

Posting A: [1, 3, 5, 7, 9, 11, 13, ...]
Posting B: [2, 3, 5, 8, 9, 12, 13, ...]
交集:      [3, 5, 9, 13, ...]

朴素算法：遍历 A 的每个元素，在 B 中二分查找。复杂度 O(N log M)。

跳表算法：在 Posting List 上构建多层跳表索引：

Level 1: [1, 5, 9, 13, ...]  ← 每隔 4 个元素一跳
Level 0: [1, 3, 5, 7, 9, 11, 13, ...]  ← 每个元素一跳

合并时，先在 Level 1 上大步跳，找到大致位置后，
再在 Level 0 上精确查找

复杂度降为 O(N + M)，在大数据量下性能提升显著。

五、错误示范

候选人原话："倒排索引就是记录每个文档里有哪些词，用链表存起来。"

问题诊断：

只理解了表层结构，不知道 Term Dictionary / Term Index / Posting List 三层分离
不知道压缩算法，不知道 Lucene 做了多少工程优化
完全不了解 FST 这个高级数据结构

面试官内心 OS："这个候选人知道倒排索引这个词，但肯定没看过 Lucene 源码。他不知道 Lucene 的倒排索引是经过 20 年工程打磨的数据结构，从 FST 到 FOR 压缩到 Roaring Bitmap，每一层都有大量的论文和实验支撑。"

六、生产避坑

6.1 分词粒度翻车

线上后果：搜索"苹果手机"搜不到"苹果 iPhone"，因为分词器把"苹果"和"iPhone"分成两个词条。

根因：使用了 standard 分词器，对英文做了小写化和单词分割，但中文和英文混合词处理不佳。

解决方案：

配置 IK 分词器的 ik_max_word 模式穷举所有分词组合
或者自定义 synonyms 同义词表

6.2 冷数据查询延迟飙升

线上后果：3 个月前的订单数据查询延迟从 50ms 飙升到 2s，但数据量只有当前月份的 2 倍。

根因：历史数据的 segment 数太多（累计 N 个月的小 segment），查询时要遍历大量 segment。

排查：

GET orders_2024_*/_segments?pretty

解决方案：对冷数据执行 forcemerge：

POST /orders_2024_01/_forcemerge?max_num_segments=1

将一个月的多个小 segment 合并成一个大 segment，查询性能可提升 10~50 倍。

七、工程选型

场景	分词策略	压缩策略	特殊配置
高频搜索	`ik_smart`	默认 PLiB	开启 filter cache
长尾词搜索	`ik_max_word`	默认 PLiB	配置同义词
日志分析	`standard` + lowercase	禁用部分压缩	`index.codec: best_speed`
精确匹配	`keyword` 分词	禁用压缩	使用 `_id` 路由

【面试官心理】这道题能答到 FST 和 FOR 压缩的候选人，说明他对 Lucene 底层有过深入研究。这种候选人在 P7 层面非常有竞争力——因为 ES 的核心就是 Lucene，能深入到底层数据结构的候选人凤毛麟角。

Elasticsearch 倒排索引原理#