倒排索引原理：从正排到倒排，搜索引擎的基石

聊搜索引擎，绕不开倒排索引。我当年刚接触这个名词时，觉得它挺玄乎。说白了，它就是一本「关键词→文档」的快速查表。今天咱们把这层窗户纸捅破，看看它到底怎么工作。

正排索引与倒排索引

先说说正排索引。正排索引就是「文档→关键词」的映射。比如你有一堆文档，每个文档里有哪些词，正排索引一查便知。这结构在数据库里很常见，按文档ID查内容，速度飞快。

但搜索引擎面临的问题不一样。用户输入的是关键词，不是文档ID。你想想看，如果用户搜「分布式」，你得从所有文档里找出包含这个词的。用正排索引，就得遍历每个文档，检查它有没有这个词。数据量一上来，这效率简直灾难。

倒排索引正好反过来。它建立的是「关键词→文档」的映射。每个词后面挂着一串文档ID，表示哪些文档包含这个词。用户搜「分布式」，直接查这个词的倒排列表，瞬间拿到所有相关文档。

我在项目中遇到过这样一个场景：早期用MySQL做站内搜索，用户搜一个词，后台用LIKE '%关键词%'去扫表。数据量到百万级时，一次查询要好几秒。后来换成倒排索引，同样的查询，毫秒级返回。嗯，这就是数据结构的威力。

倒排索引的数据结构

倒排索引由两部分组成：词典（Dictionary）和倒排列表（Posting List）。

词典就是所有不重复词的集合。每个词对应一个倒排列表的指针。词典的查询效率直接影响搜索速度。常用的实现方式有哈希表和B+树。我个人习惯用哈希表，查询O(1)，简单粗暴。但如果你需要范围查询或前缀匹配，B+树更合适。

倒排列表记录的是包含某个词的所有文档信息。每个记录叫一个倒排项（Posting），通常包含：

• 文档ID：唯一标识一篇文档
• 词频（TF）：这个词在文档中出现了几次
• 位置信息：这个词在文档中的具体位置（用于短语查询）

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

文档1：分布式系统设计
文档2：搜索引擎架构
文档3：分布式搜索引擎

对「分布式」这个词，倒排列表可能是这样：

分布式 → [(文档1, 1次, 位置0), (文档3, 1次, 位置0)]

对「搜索引擎」这个词：

搜索引擎 → [(文档2, 1次, 位置0), (文档3, 1次, 位置1)]

你看，用户搜「分布式搜索引擎」，先查「分布式」得到文档1和3，再查「搜索引擎」得到文档2和3。取交集，文档3同时包含两个词，排在最前面。这就是最基础的布尔检索。

倒排索引的构建过程

构建倒排索引，说白了就是三步：分词、排序、合并。我带你走一遍。

第一步：文档分词

把每篇文档拆成一个个词。中文分词比英文复杂，得用分词器。比如「分布式系统设计」拆成「分布式」「系统」「设计」。每个词记录它所在的文档ID和位置。

第二步：排序

把所有词按字典序排序。排序的目的是让同一个词的所有记录聚在一起，方便后续合并。

第三步：合并

遍历排序后的列表，把同一个词的记录合并成一个倒排列表。合并时，文档ID按从小到大排列，这样后面做交集运算时效率更高。

伪代码大概长这样：

// 伪代码：构建倒排索引
Map<String, List<Posting>> invertedIndex = new HashMap<>();

for each document in documents:
    tokens = tokenize(document.content)
    for each token in tokens:
        posting = new Posting(document.id, token.position)
        invertedIndex.get(token).add(posting)

// 排序并去重
for each entry in invertedIndex:
    sort(entry.value)  // 按文档ID排序

实际工程中，文档量是海量的，内存装不下。这时候要用外部排序，或者用MapReduce分布式构建。我在做搜索引擎时，用的是分段构建：先把文档分成多个小批次，每个批次构建一个局部倒排索引，最后再合并成全局索引。这样内存压力小很多。

倒排索引的压缩技术

倒排索引很占空间。你想想看，一个词可能出现在几百万篇文档里，倒排列表的长度可想而知。不压缩的话，存储和IO都是大问题。

常用的压缩技术有几种：

1. 差值编码（Delta Encoding）

倒排列表里的文档ID是递增的。与其存完整的ID，不如存差值。比如文档ID序列 [1, 3, 7, 12]，存成 [1, 2, 4, 5]。差值比原值小得多，需要的存储空间更少。

2. 变长编码（Variable Byte Encoding）

固定用4字节存一个整数太浪费。变长编码根据数值大小动态调整字节数。小数值用1字节，大数值用更多字节。我常用的实现是VByte，每个字节的最高位表示是否还有后续字节。

3. 位图压缩（Bitmap Compression）

对于稀疏的倒排列表，用位图表示更省空间。每个文档对应一个bit，1表示包含该词。但位图在文档数量极大时也会膨胀，这时候可以用Roaring Bitmaps，它结合了位图和数组的优点，在稀疏和密集场景下都有不错的表现。

压缩方法	原理	适用场景	压缩比
差值编码	存相邻文档ID的差值	所有场景	中等
变长编码	按数值大小动态分配字节	数值分布不均匀	较高
位图压缩	用bit位表示文档是否存在	密集倒排列表	极高
Roaring Bitmaps	混合位图和数组	通用场景	高

嗯，倒排索引的原理就这些。从正排到倒排，从数据结构到构建过程，再到压缩技术，每一步都有它的设计考量。搜索引擎能在大数据量下做到毫秒级响应，倒排索引功不可没。下一章咱们聊聊索引的更新策略，那又是另一番天地了。