倒排索引

问题

什么是倒排索引（Inverted Index）？它为什么能让全文搜索这么快？TF-IDF 和 BM25 是什么？

答案

正排索引 vs 倒排索引

正排索引（Forward Index）

关系型数据库使用的就是正排索引 —— 从文档到内容的映射：

文档 ID	内容
doc1	"Elasticsearch 是分布式搜索引擎"
doc2	"MySQL 是关系型数据库"
doc3	"Elasticsearch 支持全文搜索"

问题：查找包含「搜索」的文档，需要 逐个扫描 所有文档内容 → $O(n)$。

倒排索引（Inverted Index）

倒排索引反转了映射方向 —— 从词项到文档的映射：

词项（Term）	文档列表（Posting List）
elasticsearch	[doc1, doc3]
分布式	[doc1]
搜索引擎	[doc1]
搜索	[doc3]
mysql	[doc2]
关系型	[doc2]
数据库	[doc2]
全文	[doc3]

优势：查找包含「搜索」的文档，直接定位到 [doc3] → 接近 $O(1)$。

倒排索引的结构

一个完整的倒排索引由三部分组成：

1. Term Dictionary（词项字典）

所有不重复的词项组成的有序集合。ES 使用 FST（Finite State Transducer，有限状态转换器） 存储在内存中，实现前缀压缩和高效查找。

2. Term Index（词项索引）

词项字典可能很大，无法全部放入内存。Term Index 是词项字典的索引（类似书的目录），使用 FST 压缩存储在内存中，帮助快速定位 Term Dictionary 在磁盘上的位置。

3. Posting List（倒排列表）

每个词项对应的文档信息列表，包含：

信息	说明	用途
Doc ID	文档编号	定位文档
TF	词频（Term Frequency）	相关性算分
Position	词在文档中的位置	短语查询（match_phrase）
Offset	词的字符偏移量	高亮显示

Posting List 使用 FOR（Frame of Reference） 压缩和 Roaring Bitmap 进行高效存储和交集/并集运算。

搜索流程

TF-IDF 算法

TF-IDF 是经典的文本相关性算分算法（ES 5.x 之前默认使用）：

$$\text{TF-IDF}(t, d) = TF(t, d) \times IDF(t)$$

TF — 词频（Term Frequency）

词项 $t$ 在文档 $d$ 中出现的频率。出现越多，说明文档与该词越相关：

$$TF(t, d) = \sqrt{f_{t,d}}$$

其中 $f_{t,d}$ 是词 $t$ 在文档 $d$ 中出现的次数。

IDF — 逆文档频率（Inverse Document Frequency）

如果一个词在很多文档中都出现（如「的」「是」），说明它区分度低，权重应该低：

$$IDF(t) = \log\left(\frac{N}{df_t + 1}\right) + 1$$

其中 $N$ 是总文档数，$df_t$ 是包含词 $t$ 的文档数。

示例

假设搜索「Elasticsearch 教程」，有 10000 个文档：

文档	"elasticsearch" 出现次数	"教程" 出现次数
doc1	5	3
doc2	1	10

• elasticsearch 出现在 200 个文档中 → IDF 较高（区分度好）
• 教程 出现在 5000 个文档中 → IDF 较低（太常见）

doc1 中 elasticsearch 出现更多次，且 elasticsearch 的 IDF 更高，所以 doc1 可能排名更靠前。

BM25 算法

BM25（Best Matching 25） 是 ES 5.x 之后的默认算分算法，是 TF-IDF 的改进版本：

$$\text{BM25}(t, d) = IDF(t) \cdot \frac{f_{t,d} \cdot (k_1 + 1)}{f_{t,d} + k_1 \cdot (1 - b + b \cdot \frac{|d|}{avgdl})}$$

参数	默认值	含义
$k_1$	1.2	控制 TF 的饱和度（词频增长到一定程度后收益递减）
$b$	0.75	控制文档长度的归一化程度
$\|d\|$	—	当前文档长度
$avgdl$	—	所有文档的平均长度

BM25 vs TF-IDF 的关键改进

维度	TF-IDF	BM25
TF 饱和	TF 无上限，出现 100 次比 10 次高很多	TF 有饱和度，出现 100 次和 10 次差别不大
文档长度	不考虑	长文档中出现一个词不如短文档有意义
参数可调	无	$k_1$ 和 $b$ 可根据场景调整
效果	基础	更符合实际搜索直觉

BM25 的直觉理解

• 一篇论文提到「机器学习」100 次 vs 5 次，BM25 认为差别不大（都很相关）
• 一篇 100 字的摘要提到「机器学习」5 次 vs 一篇 10000 字的文章提到 5 次，BM25 认为短摘要更相关（密度更高）

Segment（段）与 Lucene 索引

ES 的每个分片底层是一个 Lucene 索引，由多个 Segment（段） 组成。每个 Segment 是一个独立的倒排索引，不可变。

写入流程

步骤	操作	数据安全	可搜索
1. 写入	进入 Memory Buffer + Translog	Translog 持久化	❌
2. Refresh	Buffer → 新 Segment（OS Cache）	Translog 保护	✅（近实时）
3. Flush	Segment → 磁盘，清空 Translog	磁盘持久化	✅

为什么是「近实时」？

默认 refresh_interval 为 1 秒，即文档写入后最多 1 秒可搜索。这就是 ES 被称为「近实时」而非「实时」的原因。可以手动调用 _refresh 立即刷新，但频繁刷新会影响性能。

Segment Merge（段合并）

随着 refresh 产生大量小 Segment，ES 会在后台自动合并（类似 LSM-Tree 的 Compaction）：

• 合并多个小 Segment 为一个大 Segment
• 物理删除已标记删除的文档（删除操作只是标记，不实际删除）
• 减少 Segment 数量，提升搜索性能

---

常见面试问题

Q1: 为什么 ES 搜索比 MySQL LIKE '%keyword%' 快？

答案：

• MySQL LIKE '%keyword%'：无法使用 B+ 树索引（前缀模糊），必须全表扫描匹配中每个文本字段。时间复杂度 $O(n \times m)$（n 为行数，m 为文本长度）
• ES 倒排索引：预先将文本分词建立「词 → 文档」的映射。搜索时直接通过词项字典定位到包含该词的文档列表，时间复杂度接近 $O(1)$

本质区别：MySQL 是在 查询时 做文本匹配，ES 是在 索引时 就完成了分词和映射。

Q2: ES 的文档删除是怎么实现的？

答案：

由于 Segment 是 不可变 的，ES 不能直接修改 Segment 中的数据：

• 删除：在 .del 文件中标记文档已删除。搜索时过滤掉这些文档
• 更新：标记旧文档删除 + 写入新版本文档
• 物理删除：在 Segment Merge 时，真正丢弃已标记删除的文档

Q3: 什么是 Translog？为什么需要它？

答案：

Translog（事务日志）类似 MySQL 的 redo log。写入操作先追加到 Translog，确保数据安全。即使进程崩溃，也能从 Translog 恢复未 flush 的数据。

• 每次写操作都追加到 Translog（默认每 5 秒 fsync 到磁盘，或可配置为每次请求都 fsync）
• Flush 时将所有 Segment 持久化到磁盘，然后清空 Translog

Q4: 如何提高 ES 的写入性能？

答案：

1. 增大 refresh_interval：从 1s 改为 30s 甚至 -1（禁用自动 refresh），减少 Segment 生成频率
2. 批量写入：使用 _bulk API 批量索引，减少网络往返
3. 减少副本数：写入时设为 0 副本，写完后恢复
4. 增大 Translog flush 间隔：index.translog.durability: async
5. 合理设置 Mapping：不需要搜索的字段设为 index: false

Q5: BM25 的 k1 和 b 参数如何影响评分？

答案：

• $k_1$（默认 1.2）：控制 TF 饱和速度。值越大，词频对评分的影响越大（高频更有利）；值越小，词频的影响越早趋于饱和
• $b$（默认 0.75）：控制文档长度归一化。值为 1 时完全按长度归一化（长文档惩罚大）；值为 0 时不考虑文档长度

// 自定义 BM25 参数
PUT /my_index
{
  "settings": {
    "similarity": {
      "custom_bm25": {
        "type": "BM25",
        "k1": 1.5,
        "b": 0.5
      }
    }
  }
}

相关链接

• Elasticsearch 倒排索引
• BM25 算法详解
• Lucene Segment 原理