3、倒排索引：倒排索引原理、构建过程、压缩技术、更新策略
好，咱们今天聊聊搜索引擎的“心脏”——倒排索引。
我经常跟团队里的新人说，你搞懂了倒排索引，搜索引擎的大门就算推开了一半。这东西说白了，就是把“文档→词”的关系，反过来变成“词→文档”。你想想看，用户搜一个词，你总不能把几亿个文档都翻一遍吧？那得等到猴年马月。倒排索引就是提前告诉你：这个词出现在哪些文档里，位置在哪。
3.1 倒排索引的原理
先看个简单的例子。假设我们有三个文档：
- Doc1: “我喜欢搜索引擎”
- Doc2: “搜索引擎优化很重要”
- Doc3: “我喜欢优化代码”
分词之后，我们建立一个“正排索引”，就是文档ID到词的映射。但这玩意儿对搜索没啥用。我们需要的是“倒排”：
| 词项 | 倒排列表（文档ID:位置） |
|---|---|
| 我 | Doc1:1, Doc3:1 |
| 喜欢 | Doc1:2, Doc3:2 |
| 搜索引擎 | Doc1:3, Doc2:1 |
| 优化 | Doc2:2, Doc3:3 |
| 很 | Doc2:3 |
| 重要 | Doc2:4 |
| 代码 | Doc3:4 |
看到没？每个词项后面挂着一个链表，记录了它出现在哪些文档里，以及具体位置。用户搜“搜索引擎”，我直接查这个词的倒排列表，啪一下就把Doc1和Doc2拎出来了。速度快得飞起。
核心思想：以词为键，以文档列表为值。空间换时间，查询复杂度从O(N)降到O(1)。
3.2 构建过程
构建倒排索引，我一般分三步走。嗯，这里要注意顺序，搞反了会出大问题。
- 文档预处理：分词、去停用词、词干提取。比如“running”变成“run”，“搜索引擎”不能拆成“搜索”和“引擎”。
- 生成词项-文档ID对：遍历每个文档，对每个词输出一个二元组（词项，文档ID）。这一步会产生大量中间数据。
- 排序与合并：按词项排序，相同词项的文档ID合并成一个倒排列表。同时记录词频和位置信息。
我在项目中遇到过一个问题：当文档量达到亿级时，中间数据根本放不进内存。这时候就得用外部排序，或者用MapReduce的思想，分而治之。我记得有一次，我们团队用Hadoop跑了一个200TB的文档集，光排序阶段就跑了6个小时。但没办法，这一步省不了。
避坑指南：我曾经在合并阶段忘记去重，结果同一个文档ID在倒排列表里出现了好几次。用户搜一个词，同一个文档在结果里重复出现，那体验简直灾难。所以合并时一定要做去重和排序。
3.3 压缩技术
倒排索引建好了，但问题来了——它太占空间了。一个词项的倒排列表可能包含几百万个文档ID，每个ID都是32位整数，存下来就是几MB。整个索引动辄几十GB甚至TB。不压缩？服务器硬盘会哭的。
我常用的压缩技术有两种：可变字节编码和Gamma编码。说白了，就是用更少的比特位来表示数字。
3.3.1 可变字节编码
这个思路很朴素：小数字用少字节，大数字用多字节。每个字节的最高位作为“延续位”，1表示后面还有字节，0表示这是最后一个字节。剩下的7位存数据。
举个例子，数字 127 的二进制是 1111111，一个字节就能搞定：01111111（最高位0表示结束）。数字 128 呢？二进制是 10000000，需要两个字节：10000001 00000000。第一个字节最高位1表示后面还有，第二个字节最高位0表示结束。
// 可变字节编码示例
// 输入：文档ID列表 [1, 2, 127, 128, 300]
// 输出：字节序列
1 -> 00000001
2 -> 00000010
127 -> 01111111
128 -> 10000001 00000000
300 -> 10000010 01011100 // 300 = 0x12C，拆成7位一组你想想看，大部分文档ID的差值（后面会讲）都很小，用可变字节编码能省下不少空间。我实测过，对于普通网页索引，压缩比能达到3:1到4:1。
3.3.2 Gamma编码
Gamma编码更狠，它把数字拆成两部分：长度和偏移。长度用一元编码，偏移用二进制编码。
具体做法：对于数字N，先找到它的二进制表示，去掉最高位的1，剩下的就是偏移。长度就是二进制位数减1，用N-1个1后面跟一个0表示。
举个例子，数字 13 的二进制是 1101。去掉最高位1，偏移是 101。长度是 3（因为二进制有4位，4-1=3），用一元编码就是 1110。所以13的Gamma编码是：1110 101。
| 数字 | 二进制 | 长度（一元） | 偏移 | Gamma编码 |
|---|---|---|---|---|
| 1 | 1 | 0 | （空） | 0 |
| 2 | 10 | 10 | 0 | 10 0 |
| 3 | 11 | 10 | 1 | 10 1 |
| 13 | 1101 | 1110 | 101 | 1110 101 |
注意：Gamma编码适合小数字，大数字会变得很长。比如数字1000，长度部分就要写9个1加1个0，占10位，加上偏移9位，总共19位。而原始二进制才10位。所以实际应用中，我一般对差值小于128的用Gamma，大于128的用可变字节。
3.4 更新策略
索引建好了，但文档是动态的。今天新增100万篇，明天删除50万篇，后天修改30万篇。怎么更新？
我见过最蠢的做法是每次更新都重建整个索引。对于小网站还行，对于百度这种量级的，重建一次得几天，黄花菜都凉了。
常用的策略有三种：
- 完全重建：定期（比如每周）重建一次主索引。简单粗暴，但更新延迟高。
- 增量更新：维护一个小的增量索引，新文档只更新到增量索引里。查询时合并主索引和增量索引的结果。增量索引满了就合并到主索引里。
- 原地更新：直接修改倒排列表。但倒排列表是连续存储的，插入或删除会导致大量数据移动。我一般不推荐。
我个人习惯用“主索引+增量索引”的方案。主索引每周重建一次，增量索引每5分钟刷一次磁盘。查询时，先查增量索引，再查主索引，合并结果。这样既保证了实时性，又避免了频繁重建。
避坑指南：我曾经在增量索引合并时没处理好删除操作。用户删了一篇文章，但增量索引里还有它的记录，导致搜索结果里出现404页面。后来我加了一个“删除列表”，专门记录被删除的文档ID，查询时过滤掉。嗯，这个问题折腾了我两天才搞定。
好了，倒排索引的核心内容就这些。原理、构建、压缩、更新，环环相扣。你想想看，没有倒排索引，搜索引擎就是个瘸子。有了它，用户才能在一秒内从几十亿网页里找到想要的内容。下一章咱们聊聊查询处理，看看倒排索引是怎么被“用”起来的。