pengtao-tech

倒排索引的基本原理

8分钟阅读

倒排索引的基本原理

一句话速记

倒排索引（Inverted Index）= 词项 → 文档列表的映射。与正排索引（文档 → 词项列表）相反——正排是”知道文档找词”，倒排是”知道词找文档”。ES 的全文搜索速度之所以快，核心就是倒排索引 + Posting List 的跳表/位图压缩，使得关键词查找和结果求交集都是亚线性时间。

通俗解释

类比：

正排索引（书的目录）：
  书本 A → [机器学习, Python, 神经网络, ...]
  书本 B → [深度学习, TensorFlow, ...]

倒排索引（书的索引页/关键词索引）：
  机器学习 → [书本A, 书本C, 书本F]
  Python   → [书本A, 书本D, 书本G]
  深度学习  → [书本B, 书本C]

搜索"机器学习"：
  直接查倒排索引 → 找到 [A, C, F] → O(1) 查找 + O(k) 返回
  不需要扫描所有书（O(n)）

关键细节

1）倒排索引的完整结构

Term Dictionary（词项字典）：
  所有出现过的词项，按字典序排列
  数据结构：FST（有限状态转换机），支持前缀/后缀搜索，内存极小
  
  machine → [offset in Posting List]
  learning → [offset in Posting List]
  python → [offset in Posting List]

Posting List（倒排列表）：
  每个词项 → 文档 ID 列表（+ 附加信息）
  
  "machine": [doc1, doc3, doc7, doc12, ...]
  
  每个条目（Posting）包含：
    - doc_id：文档 ID
    - term_frequency（TF）：词项在该文档中出现的次数（用于相关性评分）
    - position：词项在文档中的位置（用于短语查询）
    - offset：词项在原文中的字符偏移（用于高亮）

Doc Values（列式存储）：
  Posting List 的"反面"——按字段值的正排存储
  用于排序（sort）、聚合（agg）、脚本计算
  不走倒排索引

2）分析器（Analyzer）流程

原始文本 → 分析器（Analyzer）→ 词项列表 → 写入倒排索引

分析器三步：
  1. Character Filter：字符预处理（去除 HTML 标签、替换特殊字符）
  2. Tokenizer：分词（按空格分/按 IK 中文分词）
  3. Token Filter：词项处理（小写化、去停用词、词根化）

示例：
  输入："Machine Learning with Python"
  → Tokenizer → [Machine, Learning, with, Python]
  → Lowercase Filter → [machine, learning, with, python]
  → Stop Word Filter → [machine, learning, python]  （去掉 "with"）
  → 写入倒排索引：machine→[doc1], learning→[doc1], python→[doc1]

中文搜索：
  IK Analyzer（ik_max_word / ik_smart）
  "机器学习" → [机器, 学习] 或 [机器学习, 机器, 学习]（取决于分词粒度）

3）Posting List 的压缩（高性能的关键）

Frame of Reference（FOR）压缩：

原始文档 ID 列表（升序）：
[1, 3, 5, 10, 50, 51, 52, 100, ...]

Delta 编码：只存差值
[1, 2, 2, 5, 40, 1, 1, 48, ...]  ← 差值通常很小，用少量 bit 存储

分块压缩（Frame of Reference）：
每 256 个 delta 为一块
块内 delta 最大值决定所需 bit 数
→ 高度压缩，节省 60-90% 空间

Roaring Bitmap（稠密数据）：

当文档 ID 分布稠密时（如常见词"的"匹配了 60% 文档）
使用 Roaring Bitmap（结合 Array 和 Bitmap 的优化位图）
→ 求交集（AND）超快，SIMD 指令加速

跳表（Skip List）—— 快速求交集：

查询："机器学习" AND "Python"（必须同时包含两个词）

机器学习的 Posting List：[1, 3, 7, 12, 50, 100, 300, ...]
Python 的 Posting List：  [1, 5, 50, 99, 100, ...]

朴素求交集：O(m+n)，逐一比较
跳表加速：
  每隔 N 个元素存一个跳点（如每 16 个存一个）
  "机器学习"当前=3，"Python"当前=5 → 跳到 50 → "机器学习"跳到 50 → 匹配
  跳跃时直接越过大段不匹配的区域
  → O(m/N + n/N) 比较次数，实际快很多

4）ES vs MySQL 的搜索对比

场景：搜索 "机器学习"

MySQL LIKE:
  SELECT * FROM articles WHERE content LIKE '%机器学习%'
  → 全表扫描，无法使用索引（前缀通配符）
  → 10w 篇文章 = 10w 次字符串匹配
  → O(n) 时间，n=文章数

ES 倒排索引:
  → 查词项字典：O(logN)（FST）
  → 读取 Posting List：直接定位到 Offset
  → 返回文档 ID 列表：O(k)，k=匹配文档数
  → 总时间：O(logN + k)，与总文档数 n 几乎无关

5）Segment 的不可变性

Lucene（ES 底层）的 Segment 文件：
  - 一旦写入，不可修改（Immutable）
  - 删除：标记删除（在 .del 文件中标记），不实际删除
  - 更新：删除旧版本 + 新增新版本

为什么不可变：
  - 并发读无需加锁（不可变对象天然线程安全）
  - 可以被 OS Page Cache 缓存（长期有效）
  - 简化崩溃恢复（不需要 WAL）

Segment 合并（Merge）：
  多个小 Segment 定期合并为大 Segment
  合并时真正删除被标记删除的文档
  合并后的大 Segment 替换小 Segment（原子切换）
  → 释放磁盘空间，提高查询性能

延伸追问

  • Q：ES 的近实时（Near Real-Time）是怎么实现的？ → 数据写入时先进 In-memory Buffer，每隔 1 秒（refresh_interval）将 Buffer 里的数据写入新的 Segment 并打开（Segment 在 Page Cache 中，无需 fsync），此时数据可被搜索到——这就是”近实时”（1 秒延迟）。真正的 fsync（flush）每隔 30 分钟或 translog 达到阈值时发生。
  • Q：Term Query 和 Match Query 有什么区别？ → term query：精确词项查找，不经过分析器（不分词），适合关键字字段（keyword 类型）；match query：先经过分析器分词，然后查找，适合全文字段（text 类型）。搜索”机器学习”：term 查找整个词项”机器学习”；match 先分词为[“机器”,“学习”]再分别查找，支持模糊匹配。
  • Q：为什么 ES 的 text 字段不能排序和聚合？ → text 类型字段会被分词存入倒排索引，但不存 Doc Values（列式存储）。排序/聚合需要 Doc Values（按字段值遍历所有文档的值），text 字段没有 Doc Values → 无法排序聚合。解决：用 text + keyword 的多字段（multi-field），keyword 子字段存完整值 + Doc Values。

我的记法

  • 倒排索引 = 词项 → 文档 ID 列表（反向映射）
  • 结构：Term Dictionary（FST）+ Posting List（TF + position + offset）
  • 快的原因：词项查找 O(logN)，不扫描全表
  • AND 求交集快：跳表 + 位图，跳过大量不匹配区域
  • Segment 不可变 → 无锁并发读，Page Cache 友好
  • 一句话：「倒排 = 词找文档，跳表 + 位图让 AND 交集飞快」

状态

  • 已背速记
  • 能解释分析器的三步
  • 能说 Segment 不可变性的好处

关系图谱