4、倒排列表构建：文档ID编码与存储优化

好，咱们接着聊倒排列表的构建。前面我们把词典搞定了，现在轮到真正的重头戏——倒排列表本身怎么存、怎么编、怎么查得快。

说白了，倒排列表就是一堆文档ID的集合。但你别小看它，一个搜索引擎里，倒排列表的数据量可能是词典的几百倍。我见过一个中型项目，光倒排列表就占了几个TB。所以，怎么压缩、怎么编码、怎么加速查询，这里面的门道可不少。

文档ID编码：Varint 与 Group Varint

先说说最基础的——文档ID怎么存。你想想看，文档ID通常是递增的整数，比如 1、5、23、107... 这些数字直接存成32位整数，太浪费了。特别是ID之间的差值往往很小，比如 5-1=4，23-5=18，107-23=84。我们存差值（也叫d-gap）就行了。

那差值怎么编码呢？我最早接触的是 Varint（可变长整数编码）。

举个例子，数字 300 的二进制是 100101100。用Varint编码：

• 先取低7位：0101100，加上标志位1（后面还有）→ 10101100
• 再取剩下的：0000010，加上标志位0（结束了）→ 00000010
• 所以 300 编码成两个字节：0xAC 0x02

嗯，这里要注意：Varint对小数字特别友好。1个字节就能表示0-127，2个字节能表示16383。但遇到大数字就有点尴尬了——比如一个亿，得用4个字节，跟直接存32位整数差不多。

我在项目中遇到过一个问题：有些文档集合的ID分布特别不均匀，有的地方差值只有个位数，有的地方突然跳几百万。Varint在这种场景下，解码效率会下降。为什么？因为每个字节都要检查标志位，没法并行处理。

后来我换成了 Group Varint。这玩意儿怎么玩？它把4个整数打包成一个组，每组用一个字节的元数据来描述每个整数占几个字节。

编码方式	空间效率	解码速度	适用场景
Varint	中等（平均1-2字节/数）	较慢（逐字节判断）	小数字为主，内存敏感
Group Varint	略差（有元数据开销）	快（可SIMD加速）	需要快速解码，CPU敏感

我个人习惯：如果倒排列表需要频繁查询，用Group Varint；如果主要是存储归档，用Varint就够了。

词频与位置信息的存储

光存文档ID肯定不够。搜索引擎还得知道这个词在文档里出现了几次、出现在什么位置。这就是词频（Term Frequency）和位置信息（Position）。

我见过一种很蠢的做法：把词频和位置分开存成两个列表。结果查询的时候要跳两次内存，缓存命中率直线下降。正确的做法是——把词频和位置打包在一起。

具体怎么打包？我常用的格式是这样的：

// 倒排列表条目结构
struct PostingEntry {
    uint32_t doc_id;      // 文档ID（或差值）
    uint32_t term_freq;   // 词频
    uint32_t positions[]; // 位置列表（变长）
};

每个文档ID后面紧跟着它的词频，然后是一个变长的位置数组。位置数组本身也可以用Varint编码，因为位置也是递增的。

我曾经踩过一个坑：位置信息用Varint编码后，解码时忘了处理最后一个字节的标志位。结果查出来的位置全是错的，调试了整整一个下午。嗯，从那以后我写解码器都会先写单元测试。

跳跃表（Skip List）优化

好了，现在倒排列表存好了。但查询的时候，我们经常要做 求交 操作——比如查“搜索引擎 AND 优化”，需要把两个倒排列表的交集找出来。

最笨的办法：两个列表从头到尾遍历，时间复杂度O(n+m)。如果列表有上百万个ID，那就慢了。

这时候 跳跃表（Skip List） 就派上用场了。说白了，就是在倒排列表上建一些“快速通道”，让我们能跳过那些肯定不匹配的ID。

我画个简单的结构：

Level 2:  1 --------------------------> 100 --------------------------> 200
Level 1:  1 ------------> 50 ----------> 100 ----------> 150 ----------> 200
Level 0:  1 -> 5 -> 23 -> 50 -> 78 -> 100 -> 120 -> 150 -> 180 -> 200

最底层（Level 0）是完整的倒排列表。上面每层是稀疏的采样点。查询时从顶层开始，如果目标ID大于当前节点，就跳到下一个节点；如果小于，就降到下一层。

这样做的好处很明显：

• 查询复杂度从O(n)降到O(log n)
• 构建简单，不需要像B+树那样复杂的平衡操作
• 支持范围查询

我在实际项目中，跳跃表的构建参数是这样调的：

列表长度	层数	采样间隔	额外存储开销
< 1000	不建跳跃表	-	0%
1000 - 10万	8层	128	约1.5%
10万 - 1000万	16层	256	约2%

你想想看，用2%的存储开销，换来10倍以上的查询加速，这笔买卖划算吧？

综合实战：一个完整的倒排列表构建流程

最后，我分享一下我在项目中用的完整流程。假设我们要构建一个新闻搜索引擎的倒排索引：

1. 分词与统计：对每篇文档分词，统计每个词出现的文档ID、词频、位置列表
2. 排序与合并：按词排序，同一个词的文档ID按升序排列
3. 计算差值：文档ID转成d-gap，位置列表也转成差值
4. 编码：用Group Varint编码文档ID差值，用Varint编码位置差值
5. 建跳跃表：如果列表长度超过1000，按2的幂次采样建跳跃表
6. 写入磁盘：按块写入，每个块包含元数据（长度、层数等）和编码后的数据

我曾经用这套流程处理过10亿篇文档的索引构建。刚开始没加跳跃表，一个“中国”这个词的倒排列表就有8000万个ID，求交查询要好几秒。加上跳跃表后，同样的查询降到几十毫秒。效果立竿见影。

好了，这一章的内容就到这里。下一章我们聊聊索引的更新策略——毕竟互联网上的文档是不断变化的，怎么在不影响查询的情况下更新索引，那又是另一门学问了。