3、索引优化（上）：倒排索引的构建原理，以及如何通过压缩算法（如Varint、Simple9）减少索引体积
3.1 倒排索引：搜索引擎的“杀手锏”
聊到搜索引擎，绕不开的一个核心就是倒排索引。说白了，它就是搜索引擎能秒级响应的秘密武器。
我刚开始接触搜索时，第一反应是：这不就是数据库的B+树吗？后来踩了坑才明白，完全不是一回事。
正排索引是按文档ID找内容，比如“文档1里有‘苹果’、‘香蕉’”。但用户搜的是词，不是文档ID。所以我们需要反过来——按词找文档。这就是倒排索引。
举个例子：
文档1: “我喜欢苹果”
文档2: “苹果很好吃”
文档3: “香蕉也不错”倒排索引长这样：
苹果 -> [文档1, 文档2]
喜欢 -> [文档1]
我 -> [文档1]
很好 -> [文档2]
香蕉 -> [文档3]
不错 -> [文档3]每个词后面挂着一个文档ID列表，这叫“倒排列表”。搜索“苹果”时，直接取出[文档1, 文档2]，快得飞起。
核心要点：倒排索引的本质是“词到文档ID列表”的映射。它牺牲了写入复杂度，换来了极致的查询速度。
3.2 构建倒排索引：从文档到索引的流水线
构建过程其实不复杂，但细节决定成败。我习惯把它拆成三步：
- 分词：把文档切成一个个词条。中文分词比英文麻烦得多，比如“我喜欢苹果”要切成“我”、“喜欢”、“苹果”。
- 去重与排序：同一个词出现在多个文档里，合并文档ID列表，并排序。排序是为了后续压缩和合并方便。
- 写入索引文件：把词和对应的文档ID列表持久化到磁盘。
嗯，这里要注意：构建时内存消耗很大。我曾在项目中遇到一个坑——索引构建到一半，内存爆了。后来加了分段构建，每段写一个临时文件，最后再合并。
避坑指南：我曾经以为一次性把所有文档加载到内存构建就行，结果线上服务直接OOM。建议用“分段+归并”策略，每段控制在几百MB，稳得很。
3.3 索引体积的痛点：为什么需要压缩？
你想想看，一个中等规模的搜索引擎，索引可能有几十亿个文档ID。每个ID占4字节（int32），一个词如果有100万个文档，光列表就4MB。全网几千万个词，索引体积轻松上TB。
更大的问题是：索引大了，磁盘IO就慢，缓存命中率也低。说白了，索引体积直接影响搜索延迟。
所以，压缩是必须的。但压缩不能乱来——要保证解压速度足够快，不能拖慢查询。
核心矛盾：压缩率 vs 解压速度。压缩率越高，索引越小，但解压越慢。我们需要在两者之间找到平衡点。
3.4 Varint：用变长编码省空间
Varint（Variable-length Integer）是我最早接触的压缩算法。它的思路很简单：
大部分文档ID的差值很小。比如文档ID是[1, 2, 3, 100, 101]，相邻差值就是[1, 1, 1, 97, 1]。这些差值用1个字节就能存，何必用4个字节？
Varint的做法是：每个字节的最高位作为“是否继续”标志。0表示这是最后一个字节，1表示后面还有字节。剩下的7位存数据。
举个例子：
数字 1 -> 二进制 00000001 -> 编码为 00000001（1字节）
数字 127 -> 二进制 01111111 -> 编码为 01111111（1字节）
数字 128 -> 二进制 10000000 00000001 -> 编码为 10000000 00000001（2字节）你看，小数字只用1个字节，大数字才用多个字节。对于搜索引擎的文档ID差值，大部分都很小，所以压缩效果很好。
个人经验：我在项目中实测过，Varint能把倒排列表压缩到原来的30%-50%。但要注意，解压时每个字节都要判断标志位，CPU开销不小。如果查询量极大，可以考虑用更快的算法。
3.5 Simple9：一次打包多个数字
Simple9的思路和Varint完全不同。它不按单个数字编码，而是把多个数字打包到一个32位的“字”里。
32位里，前4位存“选择器”，后28位存数据。选择器有9种模式（所以叫Simple9），每种模式规定了每个数字占多少位：
| 选择器 | 每个数字位数 | 可存数字个数 |
|---|---|---|
| 0 | 1位 | 28个 |
| 1 | 2位 | 14个 |
| 2 | 3位 | 9个 |
| ... | ... | ... |
| 8 | 28位 | 1个 |
举个例子：如果差值列表是[1, 2, 3, 4, 5]，最大是5，需要3位。选择器选2（3位模式），可以打包9个数字。但只有5个，剩下的位置浪费了？嗯，确实有浪费，但整体压缩率依然不错。
对比一下：Varint是“按需分配”，每个数字用多少位就占多少字节。Simple9是“批量打包”，一次处理多个数字，解压时不用逐字节判断，速度更快。但Simple9有浪费，压缩率略低于Varint。
3.6 实战选择：什么时候用哪个？
我个人的经验是：
- 查询量中等、磁盘敏感：用Varint。压缩率高，索引小，适合磁盘IO是瓶颈的场景。
- 查询量极大、CPU敏感：用Simple9。解压速度快，适合高并发场景。
- 混合使用：有些系统会结合两者，比如高频词用Simple9，低频词用Varint。
注意：压缩算法不是万能的。如果文档ID分布非常稀疏（差值很大），压缩效果会大打折扣。这时候可以考虑重排文档ID，让相似文档的ID尽量连续。
3.7 小结
倒排索引是搜索引擎的基石，而压缩算法是让索引“瘦身”的关键。Varint和Simple9各有千秋，选哪个取决于你的业务场景。
我记得有一次线上事故，就是因为索引太大导致缓存失效，查询延迟飙升到秒级。后来换了Simple9，索引体积降了40%，延迟直接回到毫秒级。嗯，压缩算法这东西，用好了就是神器。
下一节，我会聊聊更高级的压缩算法，比如PForDelta和Roaring Bitmaps。它们能进一步压榨索引体积，同时保持极快的查询速度。敬请期待。