倒排索引基础：倒排列表结构、词典构建、压缩方式

面试问到搜索引擎或密文索引时，倒排索引几乎是必考题。我第一次接触倒排索引是在做日志检索系统的时候，脑子里全是正排索引的思维，结果查一个词要遍历全文档，耗时跟蜗牛一样。后来改成倒排，速度直接起飞。说白了，倒排索引就是把“文档→词”的关系倒过来，变成“词→文档列表”。

倒排列表结构

每个词项对应的倒排列表，本质上是一个有序的文档ID序列。我习惯把结构拆成三部分：文档ID、词频、位置列表。文档ID按升序排列，这是后续压缩和合并的前提。

举个例子，假设有三篇文档：

• Doc1: "我 爱 倒排"
• Doc2: "倒排 索引 很 快"
• Doc3: "倒排 压缩"

词项“倒排”的倒排列表大概长这样：

倒排 -> [(1, 1, [3]), (2, 1, [1]), (3, 1, [1])]

每个元组里依次是：文档ID、词频、出现位置。实际工程中位置信息常用于短语查询，但如果只做布尔检索，可以省略位置，只存docID。

词典构建

词典是倒排索引的“入口”，每个词项要能快速定位到对应的倒排列表。构建词典的方法有好几种，我整理了一个对比表：

方法	查询时间复杂度	内存占用	适用场景
哈希表	O(1) 平均	较高（冲突桶）	小规模词典，不要求前缀查询
排序数组 + 二分查找	O(log n)	低（连续内存）	静态词典，构建后不更新
Trie（前缀树）	O(len) 词长	较高（节点指针）	支持前缀匹配，自动补全
B树/B+树	O(log n)	中等（树结构）	动态更新，磁盘友好

我在项目中选过排序数组 + 二分。因为当时词典是离线生成的，不频繁更新，内存连续对缓存特别友好。有一次我图省事用了哈希表，结果测试时发现哈希冲突导致内存爆炸，查了十分钟才定位——这就是个坑。

压缩方式：Variable Byte 与 Simple9

倒排列表的原始数据一般很大，尤其docID和词频。压缩的目的就是在不影响解压速度的情况下减体积。面试时经常让你手撕编码或者对比两种压缩。我个人面试时被问过三次，每次都绕不开Variable Byte和Simple9。

Variable Byte（变长字节编码）

Variable Byte的思路很简单：每个整数用1-5个字节表示，每个字节的最高位是延续位（1表示后面还有字节，0表示结束），剩下的7位存数据。压缩率不错，解压速度也快。

我手写一个Python示例：

def vb_encode(numbers):
    res = []
    for n in numbers:
        while n > 127:
            res.append((n & 0x7f) | 0x80)
            n >>= 7
        res.append(n)
    return bytes(res)

def vb_decode(data):
    result = []
    n = 0
    for b in data:
        if b & 0x80:
            n = (n << 7) | (b & 0x7f)
        else:
            n = (n << 7) | b
            result.append(n)
            n = 0
    return result

核心就是每次取低7位，高位补1，直到最后一个字节高位为0。解压时拼回去。

Simple9（简单九编码）

Simple9的思想是把多个小整数打包到一个32位字里。它预设了9种打包模式，每个模式规定了字内分成几个比特段、每个段占几位。例如模式0表示每个段占1位，可以塞28个整数（因为需要4位存储模式标识）；模式1每个段占2位，能塞14个整数……模式8每个段占28位，只能塞1个整数。

编码时，遍历剩余整数，找到能打包最多的模式，然后一次压入一个32位整数。解码时根据前4位判断模式，然后按位解析。

我当初实现Simple9时犯了个错：没考虑剩余整数超过28个时，模式递归逻辑写错了，导致打包结果不正确。后来加了个极端情况处理才搞定。

两种方式的对比：

维度	Variable Byte	Simple9
压缩粒度	逐字节	逐字（32位）
适用整数范围	小数值更优	数值较均匀时较好
解压速度	较快（逐字节解析）	更快（SIMD可优化）
最差空间	5字节/整数	4字节/整数（1个整数装不满）

面试时，你如果能说出“Simple9利用字长对齐，现代CPU对字操作更快”这类细节，就能加分。