词典

主线位置：磁盘主线的第三步。查询里的一个词先在这里变成 TermInfo（文档数、.idx 和 .pos 里的字节范围），然后才能去读倒排表和位置。前缀、正则、模糊查询则是在词典上跑一个自动机，一次找出一批词。

flowchart TB
  key["词的值字节"] --> sel{"quickwit feature"}
  sel -->|否| fst["FST 查序号"]
  fst --> ord["TermOrdinal"]
  ord --> blk["ord 除以 256 定块"]
  blk --> meta["块头 39 字节"]
  meta --> bits["位解包出差值"]
  bits --> ti["TermInfo"]
  sel -->|是| sst["sstable 索引定块"]
  sst --> scan["块内顺序解码"]
  scan --> ti
  auto["自动机"] --> fst

src/termdict/ 1917 行（含 484 行测试），sstable 在独立的 tantivy-sstable crate（sstable/src/ 5388 行）。FST 来自 tantivy-fst 0.5，是 fst crate 的一个分支。实验同前几页：exp-tantivy/stora-disk（默认 feature）和 exp-tantivy/stora-sst（加 quickwit feature），M2 Max、macOS 27、rustc 1.99.0，release；wiki.json 的 1000 篇文档，一个段。

词典查的是什么

.term 和 .idx 一样按字段分区，每个字段一本词典。键是 Term 的值字节（serialized_value_bytes，不含字段号和类型码），值是 TermInfo：

pub struct TermInfo {
    /// Number of documents in the segment containing the term
    pub doc_freq: u32,
    /// Byte range of the posting list within the postings (`.idx`) file.
    pub postings_range: Range<usize>,
    /// Byte range of the positions of this terms in the positions (`.pos`) file.
    pub positions_range: Range<usize>,
}

键写入时必须严格递增（倒排表也按这个顺序写），所以一个词在字典序里的排名就是它的序号（TermOrdinal）。默认实现把「词 → 序号」和「序号 → TermInfo」拆成两个结构：FST 只存前者，TermInfoStore 只存后者。

文件布局

TermDictionary 是一个包装，内层由 feature 决定：

#[cfg(not(feature = "quickwit"))]
mod fst_termdict;
#[cfg(not(feature = "quickwit"))]
use fst_termdict as termdict;

#[cfg(feature = "quickwit")]
mod sstable_termdict;
#[cfg(feature = "quickwit")]
use sstable_termdict as termdict;

一个字段的 .term 分区，从后往前：

打开时 TermDictionary::open 先切下最后 4 字节比对类型，内层 open 再切 12 字节读版本和长度，把剩下的分成 FST 和 TermInfoStore 两个 FileSlice。两者都 read_bytes，在 mmap 下就是两个视图。

FST：词 → 序号

TermDictionaryBuilder 的 insert_key 把每个键映射到一个自增计数：

    pub fn insert_key(&mut self, key: &[u8]) -> io::Result<()> {
        self.fst_builder
            .insert(key, self.term_ord)
            .map_err(convert_fst_error)?;
        self.term_ord += 1;
        Ok(())
    }

FST（有限状态转换器）是一个共享前缀和后缀的有向无环图，每条边带一个输出值，沿路径把输出加起来就是这个键的值。查找 term_ord 是从根开始按字节走边，步数等于键长，不需要把任何东西载入内存。反方向的 ord_to_term 利用了「输出是序号」这一点：每个节点上选输出不超过剩余序号的最后一条边，减掉、记下字节、往下走，直到剩余为 0 且节点是终态。聚合、按字符串排序时也要把序号换回字符串，但那些调用方拿的是列存（columnar）自带的 sstable 词典；0.27.0 的 src/ 里，倒排索引词典的 ord_to_term 只有测试在调。

term_ord(great) = 8012, ord_to_term -> "great"

TermInfoStore：序号 → TermInfo

TermInfoStore 按 BLOCK_LEN = 256 个词一块。每块有一个定长的块头 TermInfoBlockMeta：

struct TermInfoBlockMeta {
    offset: u64,
    ref_term_info: TermInfo,
    doc_freq_nbits: u8,
    postings_offset_nbits: u8,
    positions_offset_nbits: u8,
}

块头 8 + 28 + 3 = 39 字节：位数据的起点、块内第一个词的完整 TermInfo（TermInfo 定长序列化是 28 字节）、三个位宽。块内其余 255 个词，flush_block 只存三个数：倒排表起点减去块首的起点、位置起点减去块首的起点、doc_freq，用 tantivy-bitpacker 的标量 BitPacker 按块内最大值定的位宽紧挨着打包，最后再补一对「块末尾」的终点。

终点不存。 同一字段的倒排表首尾相接，一个词的终点就是下一个词的起点。deserialize_term_info 读第 i 个词时，同时读第 i + 1 个词的起点当终点，块内最后一个词就读那对补上的终点。

get 是 O(1)：ord / 256 定位块头，ord % 256 为 0 直接返回块头里的 TermInfo，否则按 位宽和 × (ord % 256 - 1) 算出位地址，读一个 8 字节小端字 、移位、掩码。没有任何查找或循环。

实测：词数和字节数

前 125、250、500、1000 篇各建一个单段索引，把每个字段的 .term 分区按上面的布局拆开：

docs  125 body: terms   5306, .term   53980 B = fst   34887 + terminfo  19077 + 16; 10.17 B/term (fst 6.58, terminfo 3.60)
docs  125 url : terms    125, .term     936 B = fst     740 + terminfo    180 + 16; 7.49 B/term (fst 5.92, terminfo 1.44)
docs  125 .term file 58798 B
docs  250 body: terms   8339, .term   84067 B = fst   52943 + terminfo  31108 + 16; 10.08 B/term (fst 6.35, terminfo 3.73)
docs  250 url : terms    250, .term    1691 B = fst    1307 + terminfo    368 + 16; 6.76 B/term (fst 5.23, terminfo 1.47)
docs  250 .term file 93162 B
docs  500 body: terms  12169, .term  122366 B = fst   75582 + terminfo  46768 + 16; 10.06 B/term (fst 6.21, terminfo 3.84)
docs  500 url : terms    500, .term    3097 B = fst    2362 + terminfo    719 + 16; 6.19 B/term (fst 4.72, terminfo 1.44)
docs  500 .term file 139021 B
docs 1000 body: terms  19795, .term  205593 B = fst  125849 + terminfo  79728 + 16; 10.39 B/term (fst 6.36, terminfo 4.03)
docs 1000 url : terms   1000, .term    6118 B = fst    4616 + terminfo   1486 + 16; 6.12 B/term (fst 4.62, terminfo 1.49)
docs 1000 .term file 235399 B

再统计 1000 篇时每个字段的键本身有多长：

url: 1000 terms, raw key bytes 44000 (44.00 B/term), doc_freq==1: 1000
title: 2096 terms, raw key bytes 13202 (6.30 B/term), doc_freq==1: 1740
body: 19795 terms, raw key bytes 141085 (7.13 B/term), doc_freq==1: 12111

• 词数随文档数次线性增长：文档数每翻一倍，body 的词数只乘 1.46 到 1.63；新文档里的词越来越多是已经见过的。而 .term 的字节数几乎和词数成正比，body 稳定在每个词 10 字节上下。
• FST 约 6 字节一个词，比键本身的 7.13 字节小不了多少：英文单词短、彼此共享的前后缀有限，而 FST 还要存每条边的输出。
• TermInfo 约 4 字节一个词，未压缩的 TermInfo 是 28 字节。body 的词有六成只出现在一篇文档里，倒排表和位置都只有几字节，块内差值小，位宽就小。

前缀、正则、模糊：在词典上跑自动机

FST 的 search 接受任何 tantivy_fst::Automaton，和 FST 同步走：自动机在某个前缀上进入死状态，FST 里这个前缀下面的整棵子树都被剪掉。结果按字典序流出，每个词带着序号，再去 TermInfoStore 取 TermInfo。

两类查询用它：

• FuzzyTermQuery::automaton 用 levenshtein_automata 为查询词建一个 Levenshtein DFA（编辑距离 0 到 2、换位算 1 还是 2，共 6 种构建器，各自用 OnceCell 缓存），包成 DfaWrapper。new_prefix 建的是前缀版 DFA。
• RegexQuery 的 specialized_weight 用 tantivy_fst::Regex，正则必须匹配整个词。

两者都交给 AutomatonWeight。它的 scorer 把每个匹配词的倒排表整块读出、塞进一个 BitSet，返回 ConstScorer：命中的文档分数全部相同，不按 BM25 打分。

前缀不走自动机，走范围：PhrasePrefixWeight::phrase_scorer 用 range().ge(prefix).lt(prefix_end(prefix)) 列出候选词，prefix_end 去掉末尾的 0xFF 后把最后一个字节加一。默认最多展开 50 个词（DEFAULT_MAX_EXPANSIONS）。FST 的范围流没有 limit，这个上限在循环里数；sstable 版另外调 stream.limit，注释说是为了少下载词典块。

在 body 的 19795 个词上：

fuzzy graet~1: ["grant", "great"]
regex gr[a-z]*t: 7 terms ["gradient", "grant", "great", "greatest", "grist", "grossardt", "grubert"]
range [grea, greb): ["great", "greater", "greatest", "greatly"]
FuzzyTermQuery graet~1: 38 docs
RegexQuery gr[a-z]*t: 46 docs

graet 到 great 是一次换位（transposition_cost_one = true 时距离 1），到 grant 是一次替换。

parse grea* -> TermQuery(Term(field=2, type=Str, "grea")) -> 0 docs
parse "grea"* -> Err(PhrasePrefixRequiresAtLeastTwoTerms { phrase: "grea", tokenizer: "default" })
parse "the grea"* -> PhrasePrefixQuery { field: Field(2), phrase_terms: [(0, Term(field=2, type=Str, "the"))], prefix: (1, Term(field=2, type=Str, "grea")), max_expansions: 50 } -> 19 docs

sstable 变体

打开 quickwit feature，词典换成 tantivy-sstable 的 Dictionary<TermSSTable>。它是排好序的键值块序列：键做前缀压缩（每个键只存和上一个键不同的后缀），值由 TermInfoValueWriter::serialize_block 写成「块首的两个起点 + 每个词的 doc_freq、倒排表长度、位置长度」，全是 VInt；块的目标大小是 BLOCK_LEN = 4000 字节，另有一个块索引，按每块的「末键或更大的键」定位块（写入时换成介于本块末键和下一块首键之间的一个更短的串）。sstable crate 的 README 说明了它为谁设计：「The benefit compared to the fst crate is locality. Searching a key in the fst crate requires downloading the entire dictionary.」quickwit 把索引放在对象存储上，读一个键只想取一个块。

同样 1000 篇、同样的 schema，两种词典：

## fst
terms 19795, termdict space [("body", 205593), ("title", 23568), ("url", 6118)]
get: min of 7 runs 118.0 ns/term
## sstable
terms 19795, termdict space [("body", 87486), ("title", 8517), ("url", 3181)]
get: min of 7 runs 17010.6 ns/term

get 是对 body 的全部 19795 个词各查一次 TermDictionary::get，取 7 次里最快的一次求平均（当时 uptime 的 1 分钟负载是 12.88，其他写手在并行跑实验）。sstable 版 .term 整个文件 99302 字节，FST 版 235399 字节，小了 58%；查一个词却慢了约 144 倍。Dictionary::get 在块索引里定位块，然后从块头开始逐个解码键、直到找到目标，而 TermInfoValueReader::load 每次都把整块的 TermInfo 解进一个 Vec。README 自己也写着「the performance of a get is very bad」。本地 mmap 的场景下 FST 是对的默认值。

两种格式互相不认：

## sst binary opening fst index
... IoError(Custom { kind: Other, error: "Unsupported dictionary type, compiled tantivy with SSTable, but got Fst" })
## fst binary opening sst index
... IoError(Custom { kind: Other, error: "Unsupported dictionary type, compiled tantivy with Fst, but got SSTable" })

（... 处是 unwrap 的 panic 前缀。）Index::open_in_dir 和建 reader 都成功，错误要到第一次 SegmentReader::inverted_index(field) 打开词典时才出现：feature 开错的程序能打开索引、能拿到 Searcher，第一个查询才失败。

动脑筋答案

docs 1000 url : terms   1000, .term    6118 B = fst    4616 + terminfo   1486 + 16; 6.12 B/term (fst 4.62, terminfo 1.49)

4616 字节，约为键总长的十分之一。1000 个键共享前缀 https://en.wikipedia.org/wiki?curid=（36 字节），FST 里这段只存一次，每个键只剩 8 位左右的数字；数字之间还会共享前几位。英文正文的词短、前后缀分散，FST 几乎省不下字节；URL、路径、ID 这类长而前缀高度重复的键，FST 的压缩效果最明显。

小结

• 每个字段一本词典，键是 Term 的值字节，值是 TermInfo（doc_freq + 倒排表和位置的字节范围）。分区末尾 4 字节标明词典类型（PR #1968，0.20 起）。
• 默认实现：FST 把词映射成字典序序号，TermInfoStore 按 256 个一块、块头 39 字节、块内差值位打包存 TermInfo，终点取下一个词的起点；按序号取值是 O(1)。
• 实测 wiki.json：词数随文档数次线性增长，.term 和词数成正比，body 每词约 10 字节（FST 约 6，TermInfo 约 4）；长而前缀重复的 url 键 FST 只占原长的十分之一。
• 模糊（Levenshtein DFA）和正则在 FST 上和自动机同步遍历，结果并成 BitSet、常数分；前缀走字典序范围，最多展开 50 个词。QueryParser 的 grea* 不是前缀查询。
• quickwit feature 换成 sstable：本次实测体积小 58%，get 慢约 144 倍；为对象存储上的按块读取设计。两种格式互不兼容，错误在第一次打开词典时才出现。