3、索引存储结构：倒排索引详解、跳表与位图、词典与倒排列表的存储优化
好，咱们今天聊聊搜索引擎最核心的存储结构——倒排索引。说实话，很多刚入行的同学觉得倒排索引就是个“词到文档”的映射表，太简单了。但实际生产环境里，一个倒排索引要支撑百亿级文档、毫秒级响应，里面的门道可深了。我当年第一次优化线上索引时，就因为没搞懂跳表和位图的区别，差点把集群搞崩了。
3.1 倒排索引的核心逻辑
倒排索引，说白了就是“反向”的索引。正排索引是“文档→词”，倒排索引是“词→文档”。举个例子：
正排索引（文档ID → 内容）：
doc1: "我喜欢吃苹果"
doc2: "苹果手机很好用"
doc3: "我喜欢吃香蕉"
倒排索引（词 → 文档ID列表）：
"苹果" → [doc1, doc2]
"喜欢" → [doc1, doc3]
"香蕉" → [doc3]
嗯，这里要注意：倒排索引不是简单的列表。每个词后面挂着的，是一个倒排列表。这个列表里不光有文档ID，还有词频、位置信息、偏移量等元数据。我见过有人把倒排列表设计成纯文档ID数组，结果做短语查询时完全没法用——因为没有位置信息。
倒排列表的典型结构：
- 文档ID：唯一标识一篇文档
- 词频（TF）：这个词在文档中出现了几次
- 位置列表：每个出现位置的具体偏移
- Payload：附加信息，比如权重、域标识等
3.2 跳表：让查询飞起来
倒排列表存好了，怎么快速查？最笨的办法是遍历整个列表。但你想，一个高频词比如“的”字，倒排列表可能有上亿个文档ID。遍历一遍？那延迟得奔着秒级去了。
这时候跳表就登场了。跳表本质上是个多层链表，底层存所有数据，上层存“快速通道”。我习惯把跳表叫做“带电梯的链表”——你从顶层开始跳，跳过那些不可能匹配的区间，直达目标。
跳表示意（查找文档ID=42）：
Level 2: 1 ------------ 30 ------------ 60 ------------ 90
Level 1: 1 ---- 15 ---- 30 ---- 45 ---- 60 ---- 75 ---- 90
Level 0: 1-5-8-12-15-20-25-30-35-40-42-45-50-55-60...
查找过程：从Level 2开始，看到30小于42，跳到30；再看60大于42，降到Level 1；从30跳到45，发现45大于42，再降到Level 0；从30往后走两步，找到42。总共4步，比遍历快了一个数量级。
我的经验：跳表的层数一般设为log2(N)，N是列表长度。层数太少跳不快，层数太多浪费内存。我曾经在一个项目里把层数设成了16，结果内存暴涨了30%，后来改成动态层数才解决问题。
3.3 位图：另一种选择
跳表不是万能的。当倒排列表非常密集时（比如一个词出现在80%的文档中），跳表的优势就不明显了。这时候位图（Bitmap）是更好的选择。
位图的思想很简单：用一个bit位表示一篇文档是否存在。比如有100万篇文档，位图就占100万个bit，约122KB。查询时直接按位与、按位或，CPU一条指令就搞定了。
位图示例（文档ID从0开始）：
文档ID: 0 1 2 3 4 5 6 7 8 9 ...
位图: 1 0 1 1 0 0 1 0 1 0 ...
查询文档ID=2是否存在：检查第2位，值为1，存在。
查询文档ID=5是否存在：检查第5位，值为0，不存在。
但位图有个致命缺点：稀疏列表时浪费空间。如果一个词只出现在1%的文档中，位图里99%的bit都是0，白白占内存。我见过有人不分青红皂白全用位图，结果索引大小膨胀了10倍。
避坑指南：我曾经在一个电商搜索项目里，把所有倒排列表都转成了位图。结果上线后内存直接爆了，因为商品标题里的词大多很稀疏。后来改成“密集列表用位图，稀疏列表用跳表”的策略，内存降了60%。
3.4 词典存储优化
词典是倒排索引的“目录”。一个搜索引擎可能有几千万甚至上亿个不同的词。怎么存？最直接的想法是用哈希表。但哈希表有两大问题：一是内存占用大（每个词条要存哈希值、指针等），二是不支持前缀查询（比如搜“苹果”时想提示“苹果手机”）。
我推荐用前缀树（Trie）或有限状态转换器（FST）。FST是Lucene的核心数据结构，它能把词典压缩到极致。举个例子：
传统哈希表存储：
"apple" → 指针
"app" → 指针
"application" → 指针
总内存：3个字符串 + 3个指针 ≈ 30字节
FST存储：
a → p → p → l → e (指向倒排列表)
→ (指向倒排列表)
→ l → i → c → a → t → i → o → n (指向倒排列表)
总内存：共享前缀"app"，只存一次，约15字节
嗯，这里要注意：FST的构建比较耗时，但查询极快。我习惯在离线构建阶段用FST，在线查询时直接内存映射，毫秒级响应。
3.5 倒排列表的压缩
倒排列表是索引里最占空间的部分。一个高频词的倒排列表可能有几百万个文档ID，每个ID占4字节，那就是几MB。所有词加起来，轻松上百GB。
压缩的核心思路是：差值编码。文档ID通常是递增的，我们不用存原始ID，只存相邻ID的差值。比如：
原始列表： [1, 5, 8, 12, 15, 20]
差值编码： [1, 4, 3, 4, 3, 5]
差值都很小，可以用更少的bit位存储。比如用Varint编码，小数字只占1个字节，大数字才占多个字节。我做过测试，差值编码加Varint能把倒排列表压缩到原来的30%-40%。
常用压缩算法对比：
| 算法 | 压缩比 | 解压速度 | 适用场景 |
|---|---|---|---|
| Varint | 中等（40%-60%） | 极快 | 通用场景 |
| Simple9 | 较高（30%-50%） | 快 | 密集列表 |
| PForDelta | 高（20%-40%） | 中等 | 长列表 |
| Roaring Bitmap | 极高（10%-30%） | 中等 | 稀疏/密集混合 |
我个人最喜欢Roaring Bitmap。它把文档ID分成高16位和低16位，高16位相同的ID归到一个桶里，桶内用位图或数组存储。这样既保留了位图的快速运算能力，又解决了稀疏列表的浪费问题。我在一个日志搜索系统里用Roaring Bitmap替换了原来的跳表，查询性能提升了3倍，内存还降了一半。
3.6 实战中的取舍
说了这么多，到底怎么选？我总结几条经验：
- 词典：优先用FST，内存敏感且需要前缀查询。如果词典很小（百万级以下），哈希表也够用。
- 倒排列表：密集列表（出现率>10%）用位图或Roaring Bitmap；稀疏列表用跳表加差值编码。
- 压缩：通用场景用Varint，追求极致压缩用PForDelta，但要注意解压速度。
- 查询模式：如果经常做交集（AND查询），位图和Roaring Bitmap优势明显；如果做并集（OR查询），跳表更灵活。
最后说一句：没有银弹。我见过有人把Roaring Bitmap吹上天，结果在某个场景下性能还不如简单的数组遍历。最好的办法是——拿你的真实数据跑个benchmark。嗯，实践出真知。