倒排索引与Elasticsearch核心原理：从TF-IDF到BM25的检索引擎架构

引言：为什么需要搜索引擎

传统数据库的 B+ 树索引擅长精确匹配和范围查询，但在面对全文检索场景时性能急剧下降。当用户搜索"分布式系统的 CAP 定理"时，数据库需要对每行文本执行 LIKE '%分布式%' AND LIKE '%CAP%'，这种全表扫描在大数据量下是不可接受的。倒排索引（Inverted Index）是搜索引擎的核心数据结构，它重新定义了文本检索的方式。

一、正排索引 vs 倒排索引

1.1 正排索引（Forward Index）

正排索引是「文档 → 词项」的映射关系，类似书籍的目录：

文档1: "Rust 是一门系统编程语言"
文档2: "Go 适合构建分布式系统"
文档3: "Rust 和 Go 都是现代编程语言"

正排索引:
Doc1 → ["Rust", "是", "一门", "系统", "编程", "语言"]
Doc2 → ["Go", "适合", "构建", "分布式", "系统"]
Doc3 → ["Rust", "和", "Go", "都", "是", "现代", "编程", "语言"]

1.2 倒排索引（Inverted Index）

倒排索引反转了映射关系：「词项 → 文档列表」，类似书籍的索引页：

倒排索引（Posting List）:
"Rust"     → [Doc1, Doc3]
"Go"       → [Doc2, Doc3]
"系统"    → [Doc1, Doc2]
"编程"    → [Doc1, Doc3]
"语言"    → [Doc1, Doc3]
"分布式"  → [Doc2]
"现代"    → [Doc3]
"构建"    → [Doc2]
"适合"    → [Doc2]
"和"      → [Doc3]
"是"      → [Doc1, Doc3]
"都"      → [Doc3]
"一门"    → [Doc1]
"构建"    → [Doc2]

搜索 "Rust 编程"：在倒排索引中找到 "Rust" 和 "编程" 的文档列表，取交集，立即返回 Doc1 + Doc3。时间复杂度为 O(查询词数)，与文档总量无关。

二、倒排索引的物理结构优化

2.1 Posting List 压缩

当文档数以亿计时，每条 Posting List 可能包含数百万个文档 ID，直接存储 int64 极为浪费。常用的压缩策略：

• Delta Encoding：只存储相邻文档ID的差值（Golomb 编码）
  原始: [1, 5, 9, 100, 105, 110] → Delta: [1, 4, 4, 91, 5, 5]
• 变长编码（VInt）：小数字用少字节，大数字用多字节
• FOR（Frame of Reference）：按块压缩，每块内使用 delta encoding
• PForDelta：90% 的值用固定位存储，异常值单独处理

2.2 跳表（Skip List）加速交集

当需要计算多个 Posting List 的交集（AND 操作）时，在较短的列表中逐项二分搜索效率太低。跳表在每个 Posting List 中预先存储 checkpoint，跳过不可能匹配的区域：

Posting List: [1, 5, 9, 15, 20, 25, 30, 40, 50, 60, 80, 100]
                    ↑       ↑              ↑               ↑
                checkpoint(跳跃点)

当查找目标 42 时：
1. 在跳跃点找到 30 < 42 < 50
2. 线性扫描 30 → 40 → 50（找到了）

跳表可以将交集操作从 O(N+M) 优化到 O(min(N,M) * log(max/min))

2.3 词典压缩（FST）

Elasticsearch/Lucene 使用 FST（Finite State Transducer）压缩词典，类似于一个前缀树 + 后缀共享的自动机。百万级词汇表只需几 MB 内存存储：

FST 示例（词项: 文档频率）
c → a → r → (id:1, df:100)
         → t → (id:2, df:50)
  → o → d → e → (id:3, df:80)
            → (common prefix shared!)

FST 大小: ~5MB for 200万词项（原始需要约50MB）

三、Elasticsearch 索引架构

3.1 分片与路由

索引 (blog-posts)
├── Shard 0 (主分片) + Replica 0 (副本)
│   → 文档 hash(_routing) % num_primary_shards == 0
├── Shard 1 (主分片) + Replica 1 (副本)  
│   → 文档 hash(_routing) % num_primary_shards == 1
├── Shard 2 (主分片) + Replica 2 (副本)
│   → 文档 hash(_routing) % num_primary_shards == 2
└── 每个 Shard 是一个独立的 Lucene 索引

3.2 段（Segment）与不可变性

Lucene 中的核心设计是段（Segment）——一个不可变的倒排索引文件集合。写入操作不修改已有段，而是：

1. 写入内存缓冲区（In-Memory Buffer）
2. 定期 Refresh（默认1秒）：将内存数据转为新的段，此时可搜索但尚未刷盘
3. Flush：将内存中的段写入磁盘，清空事务日志
4. Merge：后台合并小段为大段，减少段数量

这种不可变性使得 Elasticsearch 不需要加锁，支持高并发读取。

3.3 写入路径详解

1. 请求 → 协调节点（接收）
2. 根据 _id 哈希路由到主分片
3. 写入主分片:
   a. 先写入 Transaction Log (Translog) - 顺序写盘
   b. 再写入 Memory Buffer - 内存操作
4. 同步复制到副本分片（Java Concurrent Write）
5. 确认写入完成

// Translog 保证不丢数据：
// 即使断电，重启后从 Translog 重放恢复

四、评分模型演进

4.1 TF-IDF（经典）

score(q,d) = Σ tf(t in d) * idf(t)² * boost(t) * norm(t,d)

tf(t,d): 词频 - 文档中包含查询词的频率
idf(t): 逆文档频率 - log(N/df(t))，稀有词权重高
norm: 字段长度归一化 - 短文档中命中权重更高

4.2 BM25（ Elasticsearch 5.0+ 默认）

BM25 是 TF-IDF 的改进版，解决了 TF 无限增长的问题，并引入可调参数：

BM25(q,d) = Σ idf(t) * [tf(t,d) * (k1 + 1)] / [tf(t,d) + k1 * (1 - b + b * |d|/avgdl)]

k1: 词频饱和度（默认1.2），控制加分速度上限
b: 字段长度归一化因子（默认0.75）

五、实战：Elasticsearch 查询 DSL

// 复合查询：搜索包含 Rust 和 编程 的文章
// 标题匹配加权3倍，标签匹配加权2倍，最低得分过滤
GET /blog-posts/_search
{
  "query": {
    "bool": {
      "must": [
        { "multi_match": {
            "query": "Rust 编程 并发",
            "fields": ["title^3", "tags^2", "content"],
            "type": "best_fields",
            "fuzziness": "AUTO"
        }}
      ],
      "filter": [
        { "range": { "publish_date": { "gte": "2024-01-01" }}},
        { "term": { "status": "published" }}
      ],
      "should": [
        { "match_phrase": { "title": { "query": "Rust编程", "boost": 5 }}}
      ]
    }
  },
  "highlight": {
    "fields": { "content": { "fragment_size": 200 }}
  },
  "sort": [
    { "_score": { "order": "desc" }},
    { "created_at": { "order": "desc" }}
  ],
  "aggs": {
    "tags_count": { "terms": { "field": "tags" }},
    "by_month": { "date_histogram": { "field": "publish_date", "calendar_interval": "month" }}
  }
}

六、总结

倒排索引是信息检索领域最成功的数据结构之一。从简单的词项到文档映射，到 FST 压缩的词典、跳表加速的交集、不可变段的设计，Elasticsearch/Lucene 在工程上做了大量精细优化。理解这些核心原理，不仅能帮助调优搜索性能，也是构建大规模检索系统的必备知识。