Rust in Everything
基于 tantivy 0.27.0

倒排表

主线位置：磁盘主线的第四步。词典把一个词查成 TermInfo，其中 postings_range 是 .idx 里一段字节；这一页讲这段字节怎么写出来、怎么读回去。查询主线里每个 TermScorer 底下都是一个 SegmentPostings，seek 和 block-max 剪枝都发生在这里。

flowchart TB
  ti["TermInfo"] --> slice[".idx 字段分区"]
  slice --> tot["total_num_tokens u64"]
  slice --> rng["postings_range"]
  rng --> sk{"doc_freq 至少 128"}
  sk -->|是| skip["VInt 长度加跳表条目"]
  sk -->|否| tail["vint 尾块"]
  skip --> blk["128 个一块"]
  blk --> docs["doc 块 严格差分"]
  blk --> tfs["词频块 减一"]
  blk --> tail
  skip --> reader["SkipReader"]
  reader --> seek["seek 选块"]
  seek --> kary["块内 8 路查找"]

src/postings/ 共 4999 行（含测试和索引时的 postings_writer、recorder，后两者见 SegmentWriter 与内存池）。实验在 exp-tantivy/stora-disk（M2 Max、macOS 27、rustc 1.99.0，release），索引同 Directory 一页：wiki.json 的 1000 篇文档、一个段，body 是 TEXT（带词频和位置）。实验程序不用 tantivy 的读路径，而是自己从 .idx 里切出字节、解析跳表、用 bitpacking crate 解码，再和 tantivy 的 BlockSegmentPostings 对账。

.idx 里一个字段的样子

.idx 按字段分区（CompositeFile，分区表见 Directory）。每个字段那一段由 FieldSerializer::create 开头写 8 字节的 total_num_tokens，即这个字段在本段里的总词数，BM25 的平均字段长度由它和文档数算出（BM25）。InvertedIndexReader::new 读掉这 8 字节，剩下的部分才是 postings_range 的坐标系。

之后是各个词的倒排表首尾相接，按词的字典序排列。一个词的倒排表：

部分何时有内容
跳表长度doc_freq >= 128VInt
跳表同上每个满块一条，5、8 或 12 字节
满块每 128 个文档一个doc id 块，后面紧跟词频块（如果记了词频）
尾块doc_freq % 128 != 0doc id 差分的 vint，再是词频的 vint

块大小 COMPRESSION_BLOCK_SIZE 就是 BitPacker4x::BLOCK_LEN，128。

写：PostingsSerializer

PostingsSerializer 攒满一个 Block（两个 [u32; 128]）就调 write_block：

    fn write_block(&mut self) {
        {
            // encode the doc ids
            let (num_bits, block_encoded): (u8, &[u8]) = self
                .block_encoder
                .compress_block_sorted(self.block.doc_ids(), self.last_doc_id_encoded);
            self.last_doc_id_encoded = self.block.last_doc();
            self.skip_write
                .write_doc(self.last_doc_id_encoded, num_bits);
            // last el block 0, offset block 1,
            self.postings_write.extend(block_encoded);
        }
        if self.term_has_freq {
            // encode the term frequencies
            let (num_bits, block_encoded): (u8, &[u8]) = self
                .block_encoder
                .compress_block_unsorted(self.block.term_freqs(), true);
            self.postings_write.extend(block_encoded);
            self.skip_write.write_term_freq(num_bits);
            if self.mode.has_positions() {
                // We serialize the sum of term freqs within the skip information
                // in order to navigate through positions.
                let sum_freq = self.block.term_freqs().iter().cloned().sum();
                self.skip_write.write_total_term_freq(sum_freq);
            }
            // ...
            let (fieldnorm_id, term_freq) = blockwand_params;
            self.skip_write.write_blockwand_max(fieldnorm_id, term_freq);
        }
        self.block.clear();
    }
  • doc id：compress_block_sorted 以上一块的最后一个 doc id 为起点，调 bitpacking 的 compress_strictly_sorted。「严格」差分存的是 doc[i] - doc[i-1] - 1：doc id 严格递增，差至少是 1，减掉这个 1 能省下一位。第一块没有前一块，起点 0 转成 None，第一个值按原值编码，这样 doc 0 也能表示。
  • 词频：compress_block_unsorted 的第二个参数 true 表示「减一编码」，词频至少是 1。
  • 跳表条目：块写完立刻往 SkipSerializer 里追加这块的最后一个 doc id、两个 bit 宽度、词频和（只在有位置时）、block-max。

一个词结束时 close_term 把剩下不满 128 的部分用 vint 写出（doc id 仍以上一块末尾为起点做差分，词频不减一），然后先写跳表、再写块数据：块数据一直攒在内存的 postings_write 里，跳表长度要等所有块写完才知道。

BitPacker4x

倒排表和位置用的是外部的 bitpacking crate（0.9.3，只开 bitpacker4x feature），不是工作区里的 tantivy-bitpacker。后者是另一个标量实现，词典的 TermInfoStore 和列存用它。

BitPacker4x 一次处理 128 个 u32：4 条 32 位通道，每条 32 个值，第 i 个值落在第 i % 4 条通道。一块里所有值共用一个 bit 宽度 num_bits（0 到 32），压缩后正好 num_bits * 128 / 8 = num_bits * 16 字节（compressed_block_size）。块长只由 bit 宽度决定，所以跳表里不用存字节偏移，读者把前面各块的 (doc_bits + tf_bits) * 16 累加就知道下一块在哪。bitpacking 0.9.3 在 x86_64 上用 SSE3，在小端 aarch64 上用 NEON，都检测不到时退回标量实现；M2 上走 NEON。

跳表条目

每个满块一条，长度取决于字段的 IndexRecordOption（read_block_info）：

字节Basic（5）WithFreqs（8）WithFreqsAndPositions（12）
0..4块内最后一个 doc id（u32）同左同左
4doc bit 宽度同左同左
5词频 bit 宽度词频 bit 宽度
6..10块内词频之和（u32）
之后 2 字节block-max：fieldnorm id、词频同左

doc bit 宽度那个字节由 encode_bitwidth 编码：低 5 位是宽度，第 6 位（1 << 6）表示这块用了严格差分。读的时候 decode_bitwidth 把这一位拆出来，交给 decode_bitpacked_block：同一个布尔值既决定 doc id 用 decompress_strictly_sorted 还是 decompress_sorted，也决定词频要不要加回 1。

block-max 存的不是分数，而是这块里让 BM25 的词频部分最大的那个 (fieldnorm_id, term_freq)，词频达到 255 时存 255，读回来当作 u32::MAX。只存这两个字节，分数在查询时由当前的 Bm25Weight 算（SkipReader::block_max_score），因此和 idf、boost 无关，写一次就够。

📝NOTE
冷知识：「减一」是 0.22 才加上的

PR #2185（「encode some part of posting list as -1 instead of direct values」，首次进入 0.22.0）之前，doc id 块是普通差分，跳表里那个字节就是宽度本身，词频块按原值打包。这个 PR 做了三件事，提交说明里写的是「add support for delta-1 encoding posting list」「encode term frequency minus one」「don't emit tf for json integer terms」。为了让老索引还能读，宽度字节借了一位当标记：encode_bitwidth 的注释写着「is delta-1 encoded. 0 if not, 1, if yes」，BlockDecoder::uncompress_block_sorted 的注释写着「Older version of tantivy never use strict deltas, newer versions always use them」。当时 bitpacking crate 还没有 strictly_sorted 系列函数，Cargo.toml 临时改成从 git 拉 quickwit-oss/bitpacking 的一个修订版本。对一个出现在每篇文档里的词，差分全是 1，减一后全是 0，整块占 0 字节（见下面的动脑筋）。

实测：the 的倒排表

body 字段里 the 出现在 849 篇文档里：

term "the": doc_freq 849, postings 166390..167521 (1131 B), positions 199598..209685 (10087 B)
  field total_num_tokens 171650
  skip data: vint header 1 B, 72 B = 6 x 12 B
  block 0: last_doc  150 doc_bits  2 (strict 1) tf_bits 8 tf_sum 1822 blockmax(fieldnorm_id 88, tf 141) bytes 32+128 first docs [1, 2, 3, 4]
  block 1: last_doc  299 doc_bits  2 (strict 1) tf_bits 7 tf_sum 1773 blockmax(fieldnorm_id 84, tf 94) bytes 32+112 first docs [152, 153, 154, 156]
  block 2: last_doc  461 doc_bits  2 (strict 1) tf_bits 6 tf_sum 1433 blockmax(fieldnorm_id 71, tf 31) bytes 32+96 first docs [300, 302, 303, 304]
  block 3: last_doc  618 doc_bits  2 (strict 1) tf_bits 8 tf_sum 1711 blockmax(fieldnorm_id 74, tf 46) bytes 32+128 first docs [462, 463, 464, 465]
  block 4: last_doc  768 doc_bits  2 (strict 1) tf_bits 8 tf_sum 2202 blockmax(fieldnorm_id 67, tf 32) bytes 32+128 first docs [619, 620, 622, 623]
  block 5: last_doc  905 doc_bits  1 (strict 1) tf_bits 8 tf_sum 1669 blockmax(fieldnorm_id 70, tf 36) bytes 16+128 first docs [769, 770, 771, 773]
  bitpacked bytes 896, vint tail: 81 docs in 162 B
  BlockSegmentPostings block lens [128, 128, 128, 128, 128, 128, 81]

逐项对账：849 = 6 × 128 + 81，6 个满块、一个 81 个文档的尾块，和 tantivy 自己的 BlockSegmentPostings 报出的块长一致。字节数 1 + 72 + 896 + 162 = 1131，正好是 postings_range 的长度。

  • doc 块：第 0 块覆盖 doc 1 到 150，128 个文档分布在 150 个 id 里，差分减一后大多是 0 或 1，偶有 2，宽度 2 位，32 字节。第 5 块宽度只有 1 位，769 到 905 里几乎每篇都有 the。程序用自己解出的第 128 个值和跳表里的 last_doc 做了断言，全部相等。
  • 词频块：宽度 6 到 8 位，比 doc 块（1 到 2 位）大得多。896 字节的满块里，doc 占 176 字节，词频占 720 字节：常见词的倒排表，体积主要在词频上。
  • 尾块：81 个文档 162 字节，每个文档正好一个字节的 doc 差分加一个字节的词频。vint 每字节 7 位，差分小于 128、词频小于 128 时各占一个字节。

old 只在 35 篇文档里出现，没有跳表、没有满块：

term "old": doc_freq 35, postings 120839..120909 (70 B), positions 149513..149598 (85 B)
  field total_num_tokens 171650
  bitpacked bytes 0, vint tail: 35 docs in 70 B
  BlockSegmentPostings block lens [35]

一个段里绝大多数词都是这种情况（这个段的 body 有 19795 个词，其中 12111 个只出现在一篇文档里），倒排表就是几个字节的 vint。

读：BlockSegmentPostings 与 SkipReader

BlockSegmentPostings::open 先 read_bytes 整段（mmap 下不拷贝），split_into_skips_and_postings 按 doc_freq 判断有没有跳表，然后建 SkipReader，立刻 load_block 解出第一块。

open 还有一处容错：如果跳表长度不到「满块数 × 8」，说明这个词其实没写词频，就把 record_option 降成 Basic。JSON 字段同时有文本词（带词频）和数字词（PR #2185 起不写词频），同一个字段里两种布局并存，读端只能这样推断。

调用方要的信息少于字段存的，就不解词频：FreqReadingOption 在字段是 Basic 时为 NoFreq，请求是 Basic 时为 SkipFreq（跳过词频块的字节、不解码）。解码器预先填好默认值：doc 缓冲区填 TERMINATED，词频缓冲区填 1。尾块不满 128 时，后面的空位就是 TERMINATED。

seek

SegmentPostings 是 BlockSegmentPostings 加一个块内游标 cur。SegmentPostings::seek 先看下一个文档是不是已经够了，不够才交给 BlockSegmentPostings::seek：

  1. SkipReader::seek 一条一条往后走跳表，每走一条把字节偏移加上 (doc_bits + tf_bits) * 16，把位置偏移加上 tf_sum，直到某块的 last_doc >= target。这里只读条目、不解码任何块。
  2. load_block 解码选中的那一块（如果之前没解过）。
  3. search_block 在 128 个已解码的 doc id 里找第一个 >= target 的位置。它是 kary_search::<8>：每轮比较 7 个分段端点、累加比较结果、不分支，128 → 16 → 2，最后线性扫 2 个。尾块用 TERMINATED 填满，所以总能找到。

「跳表」只有一层：一个满块一条、顺序排列的定长条目，seek 只会往前走。一个百万文档的段，最常见的词最多 7812 条，每条至多 12 字节，连续存放；块内的二分换成了 8 路无分支查找（6892995d0「10% faster intersections: Use k-ary in block search」，首次进入 0.27.0）。

📝NOTE
没有蠢问题

问： 跳表只有一层、要线性走，seek 到很远的地方不是很慢吗？

答： 走一条条目只是读几个字节、做几次加法，不碰块数据；一个词最多 doc_freq / 128 条，seek 又只往前走，整个倒排表从头到尾 seek 一遍，跳表条目合计也只读一遍。真正贵的是解码一块：seek_block 只在 last_doc 不够时才换块，换块后才解码，路过的块一律不解。求交集时各个倒排表被同一个递增的 target 推着走，代价就是「读过的条目数 + 解过的块数」，多一层索引省不掉后者。

block-max 怎么用

查询走 Block-Max WAND 时，TermScorer 要问「当前块里这个词最多能贡献多少分」。BlockSegmentPostings::block_max_score 分三种情况：满块直接从跳表条目算，不用解码；尾块如果已经解码，就把块里每个文档的分算一遍取最大；尾块还没解码，返回 bm25_weight.max_score() 这个宽松上界，并且不缓存，等块解码后再精算。seek_block 跳了块不解码，正是为了让 WAND 能用跳表条目先判断「这块值不值得解」。剪枝的整个过程见布尔查询。

❗IMPORTANT
动脑筋：1000 篇文档，每篇都含 all，偶数号的文档还含 even。all 的 7 个满块，每块 doc id 占几字节？整个倒排表里最大的部分是什么？

body 是 TEXT，单线程 writer、一次提交、一个段，实验程序同上。答案在文末。

动脑筋答案

term "all": doc_freq 1000, postings 0..293 (293 B), positions 0..112 (112 B)
  field total_num_tokens 1500
  skip data: vint header 1 B, 84 B = 7 x 12 B
  block 0: last_doc  127 doc_bits  0 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 1, tf 1) bytes 0+0 first docs [0, 1, 2, 3]
  block 1: last_doc  255 doc_bits  0 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 1, tf 1) bytes 0+0 first docs [128, 129, 130, 131]
  ...
  block 6: last_doc  895 doc_bits  0 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 1, tf 1) bytes 0+0 first docs [768, 769, 770, 771]
  bitpacked bytes 0, vint tail: 104 docs in 208 B
  BlockSegmentPostings block lens [128, 128, 128, 128, 128, 128, 128, 104]
term "even": doc_freq 500, postings 293..610 (317 B), positions 112..280 (168 B)
  field total_num_tokens 1500
  skip data: vint header 1 B, 36 B = 3 x 12 B
  block 0: last_doc  254 doc_bits  1 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 2, tf 1) bytes 16+0 first docs [0, 2, 4, 6]
  block 1: last_doc  510 doc_bits  1 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 2, tf 1) bytes 16+0 first docs [256, 258, 260, 262]
  block 2: last_doc  766 doc_bits  1 (strict 1) tf_bits 0 tf_sum  128 blockmax(fieldnorm_id 2, tf 1) bytes 16+0 first docs [512, 514, 516, 518]
  bitpacked bytes 48, vint tail: 116 docs in 232 B
  BlockSegmentPostings block lens [128, 128, 128, 116]

0 字节。all 的 doc id 连续，严格差分全是 0，词频全是 1、减一也全是 0，doc 和词频的宽度都是 0，7 个满块合计 0 字节。整个 293 字节里，1 字节是跳表长度，84 字节是 7 条跳表条目，208 字节是 104 个文档的 vint 尾块（每个文档一个字节差分、一个字节词频）：尾块和跳表是全部内容，满块反而是空的。even 每隔一个文档出现一次，差分减一后全是 1，宽度 1 位，每块 16 字节；它的尾块 116 个文档 232 字节，同样比 3 个满块的 48 字节大得多。

小结

  • .idx 每个字段一段，开头 8 字节是字段总词数；每个词的倒排表 = 跳表（doc_freq >= 128 时）+ 128 个一块的满块 + vint 尾块。
  • doc id 以上一块末尾为起点做严格差分（减一）后用 BitPacker4x 打包，词频减一后打包；一块的字节数 = 宽度 × 16，所以跳表里不存偏移。
  • 跳表条目定长（5、8、12 字节）：块末 doc id、宽度（含严格差分标记位）、词频宽度、词频和（给位置用）、block-max 的 (fieldnorm_id, tf)。PR #2185（0.22.0）引入减一编码并用标记位兼容老索引。
  • 实测 the：849 篇 = 6 满块 + 81 尾块，1131 字节；doc id 约 2 位，词频 6 到 8 位，体积主要在词频。只出现一次的词占多数，倒排表只有几字节 vint。
  • seek：单层跳表线性前进、不解码路过的块，选中后解一块，块内 8 路无分支查找；block-max 让 WAND 不解码就能估分。

💬 关联讨论

发起讨论
加载中...