4、倒排索引核心：正排索引 vs 倒排索引、倒排索引的数据结构、构建倒排索引的步骤

好，咱们今天来啃一块硬骨头——倒排索引。说实话，很多做搜索的人干了三五年，倒排索引的原理还是模模糊糊的。我当年刚入行时也踩过这个坑，以为倒排索引就是个「词→文档」的映射表，结果在优化一个千万级文档的搜索系统时，性能死活上不去。后来才发现，我对数据结构的理解太浅了。

这一章，咱们就把倒排索引的里里外外彻底讲透。你想想看，搜索引擎的核心就两个东西：一个是排序算法，另一个就是索引结构。而倒排索引，就是那个让搜索引擎能在毫秒级响应你查询的「幕后英雄」。

4.1 正排索引 vs 倒排索引：一个硬币的两面

先说说正排索引。说白了，正排索引就是「文档→词」的映射。你有一堆文档，每个文档里有哪些词，正排索引就记录这个关系。比如：

文档1：我 爱 北京 天安门
文档2：北京 的 秋天 很美
文档3：我 爱 秋天 的 北京

正排索引长这样：

文档ID	内容（词列表）
1	我, 爱, 北京, 天安门
2	北京, 的, 秋天, 很美
3	我, 爱, 秋天, 的, 北京

这种结构有什么问题？我举个例子。你想查「北京」出现在哪些文档里。用正排索引，你得把每个文档都扫一遍，看看里面有没有「北京」这个词。文档少还行，文档一多，比如上亿篇，那速度就慢得让人抓狂了。

倒排索引正好反过来。它是「词→文档」的映射。每个词后面跟着一个列表，记录这个词出现在哪些文档里：

词	文档列表
北京	[1, 2, 3]
爱	[1, 3]
秋天	[2, 3]
天安门	[1]

看到区别了吗？查「北京」的时候，直接去倒排索引里找这个词，后面跟着的文档列表就是答案。时间复杂度从 O(n) 降到了 O(1)。这就是倒排索引的核心优势——查询时不需要扫描所有文档。

我在项目中遇到过一种情况：有人用正排索引做全文搜索，结果每次查询都要遍历几百万个文档。我问他为什么不建倒排索引，他说「正排索引也能查啊」。嗯，能查是能查，但用户体验就是每次搜索都要等好几秒。后来改成倒排索引，响应时间直接降到了几十毫秒。

4.2 倒排索引的数据结构：不只是个列表

很多人以为倒排索引就是个「词→文档ID列表」的哈希表。其实没那么简单。真正的倒排索引，数据结构要复杂得多。我建议你从三个层面来理解：

4.2.1 词典（Dictionary）

词典就是所有不重复词的集合。它通常用哈希表或B树来存储。为什么？因为你要快速定位一个词是否存在。哈希表能做到 O(1) 的查找，B树则支持范围查询和前缀匹配。

我个人习惯用哈希表做词典，因为大部分搜索场景都是精确匹配。但如果你要做模糊搜索或者自动补全，B树会更合适。

4.2.2 倒排列表（Posting List）

每个词后面跟着的文档ID列表，就是倒排列表。但这里有个坑：如果文档数量巨大，倒排列表会非常长。比如「的」这个字，几乎每篇中文文档都有，它的倒排列表可能有上亿个ID。

所以倒排列表不能简单用数组存。常用的优化手段有：

• 差分编码（Delta Encoding）：不存原始ID，存相邻ID的差值。比如 [1, 3, 7, 12] 变成 [1, 2, 4, 5]。差值更小，可以用更少的bit表示。
• 变长编码（Variable Byte Encoding）：根据数值大小动态调整存储空间。小数值用1个字节，大数值用多个字节。
• 位图（Bitmap）：对于密集的文档ID集合，用位图比用列表更省空间。

4.2.3 附加信息（Payload）

光存文档ID还不够。你想想看，搜索时还要排序吧？还要高亮吧？所以倒排列表里通常还会存一些附加信息：

• 词频（TF）：这个词在文档里出现了几次。用于计算相关性。
• 位置信息（Position）：这个词在文档中的具体位置。用于短语查询和高亮。
• 字段信息（Field）：这个词出现在标题里还是正文里？标题里的词权重更高。

一个完整的倒排列表项大概长这样：

词：北京
倒排列表：
  (文档ID: 1, 词频: 2, 位置: [5, 12], 字段: 标题)
  (文档ID: 2, 词频: 1, 位置: [3], 字段: 正文)
  (文档ID: 3, 词频: 3, 位置: [1, 8, 15], 字段: 标题+正文)

4.3 构建倒排索引的步骤：从文档到索引

好，理论说完了，咱们来点实战。构建倒排索引到底分几步？我把它拆成五个步骤：

步骤一：文档预处理

原始文档不能直接用。你得先做清洗：去掉HTML标签、去掉特殊字符、统一大小写。这一步看似简单，但容易出问题。我记得有一次，因为没处理好Unicode字符，导致「café」和「cafe」被当成两个不同的词，搜索结果漏掉了很多。

步骤二：分词（Tokenization）

把文档切成一个个词。英文好办，按空格和标点切就行。中文就麻烦了，没有天然的分隔符。常用的中文分词工具有jieba、HanLP等。

举个例子，「我爱北京天安门」分词后变成：

我 / 爱 / 北京 / 天安门

这里要注意：分词粒度直接影响搜索效果。粒度太细，比如「天安门」切成「天」「安」「门」，搜索「天安门」时可能匹配不到。粒度太粗，比如「北京大学」作为一个词，搜索「北京」时又找不到。这是个权衡问题。

步骤三：词项处理（Term Processing）

分词后得到的词，还要进一步处理：

• 去停用词：去掉「的」「了」「是」这些高频但无意义的词。它们会占用大量索引空间。
• 词干提取（Stemming）：把「running」「runs」「ran」统一成「run」。英文常用，中文用得少。
• 大小写归一化：把「Apple」和「apple」当成同一个词。

步骤四：建立倒排列表

这是核心步骤。对每个文档，遍历它的词列表，为每个词建立或更新倒排列表：

// 伪代码示例
for each document d:
    for each term t in d:
        if t not in dictionary:
            dictionary[t] = new PostingList()
        dictionary[t].add(docID=d, position=pos, tf=count)

实际实现时，不会一次性把所有文档都加载到内存。通常是分批处理，每批处理完就写入磁盘，最后再合并。这叫「外部排序合并」，能处理海量数据。

步骤五：索引优化与持久化

倒排列表建好后，还要做优化：

• 排序：每个词的倒排列表按文档ID排序。这样合并查询结果时效率更高。
• 压缩：用前面说的差分编码、变长编码压缩。
• 写入磁盘：把词典和倒排列表写入索引文件。通常词典放在内存，倒排列表放在磁盘。

这一步完成后，你的倒排索引就建好了。可以开始用它做搜索了。

嗯，这一章的内容就到这里。倒排索引看起来简单，但真正做好不容易。我见过太多人把倒排索引当成一个简单的哈希表来用，结果索引文件巨大、查询速度慢。记住，倒排索引的设计核心是「空间换时间」，但空间也不能无限大，所以压缩和优化才是真正的技术活。

下一章，咱们聊聊倒排索引的查询过程，看看搜索引擎是怎么在毫秒级内从几亿篇文档中找到你要的结果的。