「倒排索引与分词原理」

倒排索引是 Elasticsearch 检索能力的基石。传统数据库用 B+ 树在有序字段上定位记录，而全文检索需要在非结构化的文本里快速找到包含某个词的文档。本文从数据结构、压缩算法、分析器与段机制四个维度拆解倒排索引，讲清一次 match 查询背后的全部细节。

1. 为什么需要倒排索引

1.1 正排索引的困境

在正式介绍倒排索引之前，先看传统关系型数据库的检索方式。以用户表为例，按主键 ID 组织数据，索引从文档到词语建立映射，称为正排索引。

1.2 LIKE 查询为什么慢

-- 无法利用 B+ 树索引，必须全表扫描
SELECT id, title, content FROM article
WHERE content LIKE '%Elasticsearch%';

当 content 字段没有前缀索引时，%Elasticsearch% 会触发全表扫描。如果表有 5000 万行，每行平均 2KB 正文，一次查询就要读取约 100GB 数据，耗时数十秒。倒排索引用空间换时间，把词语映射到文档集合，一次检索只访问词表与少量文档 ID。

1.3 倒排索引的构成

                ┌─────────────────────────────┐
                │  Term Dictionary (词表)      │
                │  elasticsearch ──┐          │
                │  lucene       ──┼──→ Posting│
                │  search       ──┤      List │
                │  tutorial     ──┘          │
                └─────────────────────────────┘
                         │ 指向
                         ▼
                ┌─────────────────────────────┐
                │  Posting List (倒排表)       │
                │  [1, 7, 23, 45, 128]        │
                │  每个元素 = 文档 ID + 词频    │
                └─────────────────────────────┘

Lucene 在写入文档时对每个字段的每个词建立 Term → Posting List 的映射。Posting List 除了文档 ID，通常还携带词频（TF）、词在字段中的位置（Position）与偏移量，供打分与短语查询使用。

1.4 一次查询的路径

{
  "query": {
    "match": { "title": "Elasticsearch tutorial" }
  }
}

上述查询的执行路径为：分词得到 term 集合 → 查 Term Dictionary 找到对应 Posting List → 合并多个词的结果 → 按 BM25 打分 → 返回排序结果。整条路径不触碰原始文档，只操作压缩后的倒排结构，这是 ES 能在海量数据上亚秒级响应的根本原因。

2. 倒排索引的数据结构

2.1 Term Dictionary 与 Term Index

倒排表可以很大，如何快速定位一个词？Lucene 在 Term Dictionary 之上再建一层内存驻留的 FST（有限状态转换器）。

FST 将词典前缀共享，例如 elasticsearch、elastic、elastics 共享 elastics 前缀，相比 HashMap 大幅节省内存。一个 100 万词的词典，FST 通常只需几十 MB，且查询复杂度为 O(词长)，与词典规模无关。

2.2 Posting List 与跳表

Term: elasticsearch
Posting List: [1, 4, 7, 9, 12, 15, 18, 21]

跳表将 Posting List 分成多级索引：
Level 2: [1, 7, 12, 18]
Level 1: [1, 4, 7, 9, 12, 15, 18, 21]

查询 >= 8 的第一个文档：从 Level 2 开始，7 < 8 ≤ 12，
定位到 Level 1 的 9，命中 9。

跳表让两个 Posting List 的求交集（AND）无需扫描全部元素。ES 的 bool 查询对多个 term 做交集时，用跳表跳过不可能命中的区间，复杂度从 O(N+M) 降为 O(N/M) 量级。

2.3 文档 ID 的段内偏移

Lucene 每个段内文档 ID 从 0 开始递增分配，称为 docBase。全局文档 ID = 段内 docId + 段起始偏移，这样 Posting List 内部可以存储紧凑的局部 docId，便于压缩与差量编码。删除文档不会立即物理删除，而是在位图上标记 deleted，合并段时才真正清理，因此频繁 delete 会导致磁盘占用持续上升直到 merge 发生。

3. Posting List 的压缩存储

3.1 Frame of Reference 差值编码

Posting List 是有序递增整数数组，Lucene 用 FOR（Frame of Reference）压缩：先求相邻差值，再用最小字节数存储。

原始数组: [73, 300, 302, 332, 343, 372]
差值数组: [73, 227,   2,  30,  11,  29]

第二帧最大差值为 227，需要 8 位/元素
第三帧最大差值为 30，只需要 5 位/元素

压缩结果约：原始 6 × 16 位 = 96 位
压缩后约：16 + 6 × 8 + 6 × 5 = 94 位

3.2 RLE 与位图切换

当文档 ID 连续时，差值大量为 1，适合 RLE（游程编码）；当文档覆盖稀疏时，FOR 收益有限。Lucene 按密度自动切换编码策略。

ES 7.x 之后的 Lucene 9 对高基数、分布不均匀的 Posting List 会退化为 BitSet 或分块自适应编码，避免最坏情况下的膨胀。理解这些编码，能解释为什么合理的主键设计与紧凑文档结构可以显著降低索引体积。

3.3 压缩收益的实测

curl -s 'http://localhost:9200/article/_stats/indexing,store?pretty' | jq '.indices.article.primaries.store'

实测经验：一篇含 2000 个词的文档，分词后词项约 2500 个（含重复），倒排索引体积通常只有原始 JSON 的 30% 到 50%。因为高频词被字典去重，Posting List 又是差值压缩，正文里的重复措辞几乎不占空间。

4. 分词与分析器

4.1 Analyzer 的三段流水线

原始文本
   │
   ▼
┌─────────────────────┐
│ Char Filter  字符过滤│  → 去除 HTML 标签、转换全角半角
└─────────────────────┘
   │
   ▼
┌─────────────────────┐
│ Tokenizer   分词器   │  → 按空格/规则切出词元
└─────────────────────┘
   │
   ▼
┌─────────────────────┐
│ Token Filter 词元过滤│  → 小写化、停用词、同义词、词干化
└─────────────────────┘
   │
   ▼
输出 token 流进入倒排索引

ES 内置 standard、keyword、whitespace、pattern、path_hierarchy 等分词器。生产环境最常见的组合是 standard tokenizer + lowercase + stop filter + synonym filter。

4.2 分词结果预览

curl -X POST 'http://localhost:9200/_analyze?pretty' \
  -H 'Content-Type: application/json' \
  -d '{
    "analyzer": "standard",
    "text": "Elasticsearch 8.0 Search Engine Tutorials"
  }'

{
  "tokens": [
    { "token": "elasticsearch", "position": 0 },
    { "token": "8.0",           "position": 1 },
    { "token": "search",        "position": 2 },
    { "token": "engine",        "position": 3 },
    { "token": "tutorials",     "position": 4 }
  ]
}

可见 standard 分析器把大写转小写、按标点与空白切分。English 分析器还会额外做词干化（tutorials → tutorial），提高召回。

4.3 中文分词与 IK

中文没有空格边界，需要词典或机器学习分词。主流方案是 IK 分词器，支持最粗粒度与智能分词两种模式。

# 安装 IK 插件
bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis-ik/releases/download/v8.0.0/elasticsearch-analysis-ik-8.0.0.zip

{
  "settings": {
    "analysis": {
      "analyzer": {
        "cn_ik": {
          "type": "ik_max_word",
          "stopwords": "_chinese_"
        }
      }
    }
  }
}

IK 的 ik_max_word 会穷举可能的切分方式（最细粒度），召回高但索引膨胀；ik_smart 只保留最合理切分，索引小但可能漏召回。中文检索建议 search 阶段用 ik_smart，index 阶段用 ik_max_word，配合 multi-fields 实现不同精度的匹配。

4.4 自定义分词器的坑

{
  "settings": {
    "analysis": {
      "filter": {
        "my_synonym": {
          "type": "synonym",
          "synonyms": ["电脑,计算机,PC", "手机,手机设备 => 手机"]
        }
      },
      "analyzer": {
        "syno_analyzer": {
          "type": "custom",
          "tokenizer": "ik_max_word",
          "filter": ["lowercase", "my_synonym"]
        }
      }
    }
  }
}

同义词过滤器必须放在索引与查询两侧同时生效，否则搜索词与被搜索词词形不一致时召回率异常。生产环境建议只对查询侧使用同义词，索引侧保持原词，避免索引歧义导致后续无法精确统计词频。

5. 索引段与近实时可见性

5.1 Segment 的不可变性

Lucene 索引由多个不可变的段（Segment）构成。写入请求先进入内存 buffer，refresh 之后生成一个新段。段一旦落盘就不再修改，更新文档本质是写新段 + 旧文档标记删除。

内存 buffer（默认 1MB）
   │  refresh（默认 1s）
   ▼
内存段（in-memory segment，可被查询）
   │  flush（translog 落盘 + fsync）
   ▼
磁盘段 ── merge ──→ 更大的段 → 删除旧段

5.2 近实时 NRT 的含义

ES 是近实时而非实时的，因为 refresh 间隔默认 1 秒。写入后最多 1 秒才可被搜索到，这是权衡：refresh 越频繁，段越多，查询与 merge 开销越大。

5.3 调整 refresh 间隔

curl -X PUT 'http://localhost:9200/log_index/_settings?pretty' \
  -H 'Content-Type: application/json' \
  -d '{
    "index": {
      "refresh_interval": "30s",
      "translog.durability": "async"
    }
  }'

日志与监控类场景可接受 30 秒可见性，把 refresh 拉长能显著降低段合并压力。而电商搜索需要尽快可见，refresh_interval 保持 1 秒。调优时需要理解代价：不可变段数量上升，merge 线程抢占 IO。

6. 查询如何命中倒排索引

6.1 Term 查询的执行

{
  "query": {
    "term": { "status": "active" }
  }
}

term 查询不做分词，直接拿 active 到 Term Dictionary 查找。执行步骤为：查 Term Index（FST）定位 → 读取 Term Dictionary 块 → 解压 Posting List → 按位图过滤已删除文档 → 构造命中集。

6.2 Match 查询的差异

{
  "query": {
    "match": { "title": "Elasticsearch tutorial" }
  }
}

match 查询先把查询串分词，再对每个词执行 term 查询，最后合并打分。正因如此，index 阶段和 search 阶段必须使用一致的 analyzer，否则分词结果不同，导致词命不中。

6.3 多词合并与短语查询

curl -s 'http://localhost:9200/article/_search?pretty' \
  -H 'Content-Type: application/json' \
  -d '{
    "query": {
      "match_phrase": { "title": "Elasticsearch tutorial" }
    }
  }'

match_phrase 会利用 Posting List 中存储的 Position 信息，要求两个词相邻且顺序一致。Position 数组是倒排索引中额外存储的位置信息，是短语查询与邻近度查询的数据基础，代价是索引体积增加约 20% 到 30%。

7. 倒排索引的局限与工程权衡

7.1 覆盖查询与空匹配

倒排索引擅长命中查询，但难以回答统计类问题，例如统计所有文档总数，需要遍历全部 Posting List 或用 doc values 聚合。纯倒排结构也没有数值范围的高效定位能力，因此 ES 对数值与日期字段额外构建 BKD 树（基于 B+ 树思想的 kd-tree）。

7.2 深分页与代价

倒排索引返回的是文档 ID 集合，from + size 分页需要在所有分片上取全量候选再全局排序，代价随 from 线性增长。生产环境深分页应当使用 search_after 或 scroll，相关内容在《Query DSL 与相关性打分》一文中有详细对比。

7.3 前缀查询的开销

{
  "query": {
    "prefix": { "code": "elastic-" }
  }
}

prefix 查询无法直接走 Posting List，需要扫描 Term Dictionary 中所有以 elastic- 开头的词。高基数前缀会导致性能下降，建议改用 ngram 分析器或 wildcard 索引字段。倒排索引是强大的检索结构，但每一类查询都要理解其底层遍历方式，才能做出合理的索引设计。

8. 总结

倒排索引把全文检索从全表扫描变成词典查找，这是 Elasticsearch 分布式检索能力的起点。理解词表、倒排表、压缩与分段机制之后，才能在下游的 Query DSL、集群分片与性能调优中做出正确决策，相关内容可继续阅读同专题的《Query DSL 与相关性打分》《集群分片与高可用架构》《性能调优与缓存策略》与《数据建模与 Mapping 设计》。

延伸阅读

• Query DSL 与相关性打分
• 集群分片与高可用架构
• 性能调优与缓存策略
• 数据建模与 Mapping 设计
• 部署运维与备份恢复