倒排索引原理#

一句话答案#

倒排索引将「词项 → 包含该词的文档列表」建立映射，本质是从内容到文档 ID 的反向查找结构；由词典（Term Dictionary，B+树/FST）+ 倒排列表（Posting List，doc_id + 词频 + 位置）组成，是全文检索的核心数据结构。

核心要点

正排 vs 倒排#

正排索引（Forward Index）：
  Doc1 → "Java 并发 线程池 原理"
  Doc2 → "线程池 参数 拒绝策略"
  Doc3 → "Java 集合 HashMap"

倒排索引（Inverted Index）：
  "Java"    → [Doc1, Doc3]
  "线程池"   → [Doc1, Doc2]
  "并发"    → [Doc1]
  "HashMap" → [Doc3]
  "拒绝策略" → [Doc2]

plaintext

倒排索引结构#

┌─────────────────────────────────────────────────┐
│  Term Dictionary (词典)                          │
│  ┌──────────┬──────────────────────────────────┐│
│  │   Term   │       Posting List               ││
│  ├──────────┼──────────────────────────────────┤│
│  │  Java    │ → [(Doc1, tf=1, pos=[0]),        ││
│  │          │      (Doc3, tf=1, pos=[0])]      ││
│  ├──────────┼──────────────────────────────────┤│
│  │  线程池   │ → [(Doc1, tf=1, pos=[2]),        ││
│  │          │      (Doc2, tf=1, pos=[0])]      ││
│  └──────────┴──────────────────────────────────┘│
└─────────────────────────────────────────────────┘

Posting List 每项包含：
- doc_id: 文档编号
- tf (term frequency): 该词在文档中出现次数
- position: 词在文档中的位置（用于短语查询）
- offset: 原文中的字符偏移（用于高亮）

plaintext

Term Dictionary 的实现#

问题：词项可能有百万级，如何快速定位？

方案1: B+ 树（传统数据库索引方式）
  - 优点：支持范围查询
  - 缺点：内存占用大

方案2: FST (Finite State Transducer) — Lucene 实际采用
  - 本质：共享前缀和后缀的有限状态机
  - 优点：极度压缩（比 HashMap 小 10 倍），支持前缀查询
  - 缺点：构建后不可变，需要全量重建

Term Index (内存) → Term Dictionary (磁盘) → Posting List (磁盘)
  FST 前缀树        按 block 存储              压缩存储

plaintext

Posting List 压缩#

原始: [1, 3, 5, 8, 12, 15, 20]

1. Delta Encoding (差值编码):
   [1, 2, 2, 3, 4, 3, 5]  ← 存差值，数字变小

2. Variable Byte Encoding / FOR (Frame of Reference):
   小数字用更少的位数表示

3. Roaring Bitmap（高基数场景）:
   - 将 doc_id 分为高 16 位（桶编号）+ 低 16 位（桶内偏移）
   - 桶内 <4096 个元素用排序数组
   - 桶内 ≥4096 个元素用 Bitmap

plaintext

查询过程#

查询 "Java AND 线程池"：
1. 在 Term Dictionary 找到 "Java" → Posting List A = [Doc1, Doc3]
2. 在 Term Dictionary 找到 "线程池" → Posting List B = [Doc1, Doc2]
3. 求交集: A ∩ B = [Doc1]  ← Skip List 加速
4. 计算相关性分数 (BM25)
5. 返回 Doc1

plaintext

与 MySQL B+树索引对比#

维度	B+树索引	倒排索引
适合场景	精确匹配、范围查询	全文搜索、模糊匹配
查找方式	按值查找行	按词项查找文档列表
匹配能力	=, >, <, BETWEEN	分词后匹配、AND/OR 组合
更新成本	低（就地更新）	高（追加新 Segment）
实时性	实时	近实时（refresh 延迟）

面试回答（2分钟版）

倒排索引是全文检索的核心，本质是从词项到文档列表的反向映射。结构分两部分：Term Dictionary 存所有词项，Lucene 用 FST（有限状态转换器）实现，极度压缩且支持前缀查询；Posting List 存每个词项对应的文档 ID 列表，还包含词频和位置信息用于相关性评分和短语匹配。Posting List 通过 Delta Encoding 和 Roaring Bitmap 压缩存储。查询时先在 Term Dictionary 定位词项，取出各自的 Posting List，再用 Skip List 快速求交集/并集。和 B+树的区别是：B+树适合精确匹配和范围查询（WHERE id=1），倒排索引适合分词后的全文匹配（搜索”Java 线程池”能匹配到包含这两个词的所有文档）。缺点是更新成本高——ES 不能就地修改，只能标记删除后追加新文档。

追问与易错

追问方向：

“FST 和 HashMap/B+树的区别？”→ FST 共享前后缀极度压缩，但不可变；HashMap 快但占内存大
“Posting List 怎么求交集？”→ Skip List 跳跃查找，时间复杂度 O(n+m) 优化到 O(n*log(m))
“为什么 ES 删除不是真删？”→ Segment 不可变，标记删除后在 merge 时物理清除
“倒排索引能做范围查询吗？”→ 数值类型用 BKD-Tree（类似 KD-Tree），不走倒排

易错点：

❌ “倒排索引和 B+树功能一样”——完全不同的数据结构，解决不同问题
❌ “所有字段都走倒排索引”——keyword 类型用精确匹配（类似 HashMap），数值用 BKD-Tree
❌ “倒排索引支持实时更新”——Segment 不可变，写入有延迟