【全文检索引擎】词项词典 FST：前缀压缩与 TermsEnum

分析链 产出的每个 term 必须先写入段内 词典（lexicon），查询才能在 \(O(\text{term length})\) 量级定位到对应 postings 指针。Lucene 9.x/10.x 默认用 有限状态转换器（Finite State Transducer, FST） 存放按字典序排序的 Terms，在共享前缀（与部分后缀结构）下获得远小于「纯 HashMap + 字符串堆」的内存占用，并支持 TermsEnum 顺序扫描与 seek 定位——这是 Zobel & Moffat 所述「词典必须支持快速查找与遍历」在 JVM 工程里的主实现（ACM Computing Surveys, 2006）。

本文是系列第 4 篇，回答：

1. FST 在段文件中扮演什么角色，与 postings 文件如何衔接？
2. 为何生产环境常假设「词典可常驻内存」？
3. TermsEnum 提供哪些迭代语义，与 PG GIN Entry Tree 差在哪？

版本锚定：Apache Lucene 9.x/10.x org.apache.lucene.util.fst、Fields、Terms、TermsEnum 官方 Javadoc 与 Codec 设计说明。FST 理论可回溯至 Mihov 等关于最小化自动机的经典工作；Lucene 实现以当前源码为准。

一、最小故事：查询词如何找到 postings 入口

查询 title:lucene（已分析为 term lucene）在单个 Segment 上的第一步不是扫 postings，而是：

1. 打开字段 title 的 Terms。
2. 在 FST 上 seek 到 lucene。
3. 读取该 term 的 元数据（指向 postings 文件的字节偏移、doc count、总 freq 等）。
4. 按偏移解码 postings 列表。

若 seek 失败（term 不存在），该子句在此段上无命中，Boolean 查询走空迭代器（第 9 篇）。

sequenceDiagram
  participant Q as Query term
  participant TE as TermsEnum
  participant FST as Terms FST
  participant P as Postings file
  Q->>TE: seekExact(lucene)
  TE->>FST: follow arcs
  FST-->>TE: output state + metadata
  TE->>P: decode postings at offset

二、词典在段内的位置

一个 Segment 对每个 indexed 字段维护独立倒排域。逻辑结构（与 storage/29 示意图一致，但文件化）：

flowchart TB
  field["Field: title"]
  fst["Terms FST<br/>sorted byte terms"]
  meta["Term metadata<br/>docFreq, totalTermFreq, pointer"]
  post["Postings .doc / .pos / ..."]
  field --> fst
  fst --> meta --> post

Elasticsearch 分片内同一套布局；集群层额外有 translog 与段合并调度（第 11–12 篇）。

三、FST 与前缀压缩直觉

3.1 为何不用 HashMap

设字段词典有 \(T\) 个 term，平均字节长 \(\bar{L}\)。朴素 HashMap 需存储每个 term 的完整字节串 + 哈希表开销。高基数文本字段（日志 message、URL 碎片）下，仅词典就可能占满内存。

FST 将 排序后的 term 序列 编为一台共享前缀的自动机：相邻 term 如 lucene、lucene segment 共享 lucene 路径。输出标签可挂载 该 term 的 postings 元数据。遍历自动机等价于按字典序枚举 term。

3.2 内存映射假设

Lucene IndexSearcher 打开 DirectoryReader 时，FST 字节通常通过 mmap 映射（取决于 Directory 实现与 OS）。因此：

• 查询热路径是内存带宽 + CPU 解码，而非随机磁盘 seek。
• 段数过多时，每个段一份 FST 叠加，仍可能挤压堆外内存——architecture/42 讲的「分片过多」在库层体现为 per-segment 词典重复（第 8、17 篇）。

3.3 与经典综述的关系

Zobel & Moffat 讨论 front-coding、二分搜索词典等压缩方案。FST 可视为 前向压缩 + 有限状态机 的工程化变体，并支持 增量构建（Builder API）与 持久化到 .tim 等文件（具体扩展名随 PostingsFormat / codec 版本而变，以 Lucene 9.x Lucene90 系列 codec 文档为准）。

flowchart LR
  sorted["Sorted terms<br/>from flush"]
  bld["FST Builder"]
  bytes["On-disk FST bytes"]
  mmap["mmap at search time"]
  sorted --> bld --> bytes --> mmap

四、TermsEnum：遍历与 seek API

TermsEnum（A 级：Lucene Javadoc）是词典上的迭代器，核心方法包括：

查询优化常用：

• seek 多子句：Boolean MUST 子句在各自 TermsEnum 上前进，做 galloping / 跳跃相交（第 5、9 篇）。
• 前缀与范围：AutomatonQuery 在 FST 上跑自动机，避免展开爆炸前缀列表。
• 通配符代价：短前缀 wildcard 可能导致大量 term 展开——这是词典遍历代价，不是 FST 失效。

flowchart TB
  subgraph enumOps ["TermsEnum operations"]
    seek["seekExact / seekCeil"]
    walk["next() scan"]
    pe["postings()"]
  end
  seek --> pe
  walk --> pe

五、与 PostgreSQL GIN Entry Tree 的一句对照

PG GIN 的 Entry Tree 是「键值 → posting 存储位置」的 B-Tree，页模型与堆表 TID 对齐；Lucene 的 Terms FST 是「排序 term 字节 → postings 指针」的 自动机，与 Segment 不可变文件绑定。

二者都是 倒排词典，但 存储引擎假设不同：PG 优化缓冲池内 B-Tree 与 WAL；Lucene 优化不可变段 + mmap + 合并。

六、多字段与 Unicode

• 按 field 分域：title:lucene 与 body:lucene 是不同 FST，避免 field 名混入 term 字节。
• Unicode：term 以 UTF-8 bytes 排序；Analyzer 负责大小写折叠（通常 lowercase filter），词典不存显示用原文。
• 极短高基数字段（UUID keyword）：FST 压缩率下降，词典趋近「每 term 独立路径」——mapping 设计应限制不必要的 text 分析（第 14 篇）。

七、源码锚点（只读核对）

Lucene 源码路径（版本随发行版标签，核对时用 9.x/10.x tag）：

• org/apache/lucene/util/fst/FST.java — 自动机结构与 arc 编码
• org/apache/lucene/codecs/lucene90/blocktree/FieldReader.java — 块树 + FST 组合（现代 codec 常用 block tree terms dictionary，叶块内仍依赖 FST/索引结构；实现细节以所用 PostingsFormat 为准）

工程间隙：教程常简称为「FST 词典」；实际 codec 可能是 BlockTreeTermsDictionary 外包 FST 索引叶块。对读者而言，语义不变：sorted terms → seek → postings pointer。

八、BlockTree 词典：FST 之上的工程包装

现代 Lucene codec（如 Lucene90PostingsFormat）在磁盘上常呈现 BlockTreeTermsDictionary 布局，而非「单个巨型 FST 覆盖全部 term」的教科书图景（A 级：对应 org.apache.lucene.codecs.lucene90.blocktree 包）：

查询 seekExact 时，先在根结构上定位块，再在块内二分或扫描。好处是 构建期可流式写入，避免单机构建百万级 term 时峰值内存过高；语义上仍是「sorted terms → pointer」，与第 5 篇 postings 文件衔接。

flowchart TB
  root["Root index FST-like"]
  b1["Block prefix: lu"]
  b2["Block prefix: se"]
  leaf["Leaf terms + meta"]
  root --> b1 --> leaf
  root --> b2

Elasticsearch 升级 Lucene major 时若 codec 名变化，旧段仍携带旧 PostingsFormat 名——读取依赖节点内置旧 codec 模块，这是 词典 + postings 字节布局与版本绑定 的服务层表现。

九、复现：观察段内词典文件（步骤）

无本机输出；单节点 ES 8.x 写入若干文档后，可在 path.data 下找到分片 Lucene 目录。典型可见（文件名随 Lucene 版本略有差异）：

_0.si          # segment info
_0.fnm         # field names
_0.tim         # terms dictionary (block tree)
_0.tip         # terms index
_0.doc / _0.pos # postings

对照 Lucene CheckIndex 工具或 lucene-checkindex 可打印每字段 term 数与词典健康度——用于验证「analyzer 变更后新段 term 统计是否异常」，而非猜测 FST 损坏。

十、学术与开放问题

Mihov（1993 及后续）与 Watson（1995）一类工作说明：最小化确定性有限自动机可在有限内存表示大词典。Lucene FST 在此基础上增加 输出标签 与 可持久化字节布局，服务 JVM 堆外映射。

开放问题：

1. 段合并时词典重复：合并后 term 空间合一，但合并前多段 FST 重复占用内存——TieredMergePolicy 的取舍（第 8 篇）。
2. ** learned 词典 / 压缩**：研究界探索 learned index 是否替代 FST（第 18 篇边界）；生产 Lucene 仍以 FST/BlockTree 为默认，peer-reviewed 替代方案未成为 ES 默认路径。
3. 超大唯一 term 集（安全日志 hash）：FST 构建时间与 mmap 工作集是否成为瓶颈，需结合 workload 实测——本站无集群数据时不给排名。

10.1 常见误解

1. 「FST 存 postings」。FST 存 term 与指向 postings 的元数据；docID 列表在 postings 文件。
2. 「词典在堆里」。现代路径优先 mmap 字节块；堆内主要是 reader 对象壳。
3. 「GIN 与 Lucene 词典可互换理解」。键模型与更新路径不同，只能类比「都是 term→倒排入口」。

十一、小结

三句话小结

1. Terms FST 是段内排序词典的压缩自动机，查询第一步 seek term，第二步读 postings。
2. TermsEnum 统一了精确查找、字典序扫描与统计量读取，是 Boolean 相交的入口 API。
3. 与 PG GIN Entry Tree 同属倒排词典，但 Lucene 绑定不可变段与 mmap，而非 B-Tree 页 WAL。

参考资料

核心论文 / 书籍

1. Zobel, J. & Moffat, A., Inverted Files for Text Search Engines, ACM Computing Surveys 38(2), 2006（词典压缩与查找）。
2. Mihov, S., Subword Trees: A Storage Scheme for Efficient Representation of Sets of Words, 1993（子词树 / 自动机词典脉络）。

规范 / 源码

3. Apache Lucene 9.x/10.x, org.apache.lucene.util.fst Javadoc、Terms、TermsEnum。
4. Apache Lucene, Lucene90PostingsFormat / BlockTree terms dictionary 设计说明（随版本查阅）。

站内

5. Analyzer、Postings codec、PG GIN Entry Tree。

上一篇：分析链 Analyzer ｜ 下一篇：Postings 与 codec ｜ 系列目录