1. 倒排索引基础：从搜索引擎的“秘密武器”说起

大家好，我是老张。做搜索这块也有些年头了。今天咱们聊聊倒排索引——这玩意儿说白了，就是搜索引擎的“心脏”。你每次在百度、Google敲个关键词，背后都是它在干活。

我记得刚入行那会儿，带我的师傅跟我说：“小张，搞懂倒排索引，你就算入门了。”当时我还不太理解，后来踩了不少坑，才明白这句话的分量。

什么是倒排索引？

先别急着看定义。咱们想个场景：你有一堆文档，想找包含“搜索引擎”这个词的文章。最笨的办法是什么？——把每篇文章从头到尾读一遍。这就是“正排索引”的思路。

倒排索引反着来。它先建一个“词→文档”的映射表。比如：

“搜索引擎” → [文档1, 文档3, 文档7]
“倒排索引” → [文档2, 文档5, 文档9]
“存储优化” → [文档1, 文档4, 文档8]

你看，查“搜索引擎”时，直接定位到文档1、3、7。不用遍历所有文章。这就是倒排索引的核心思想——以词找文。

倒排索引 vs 正排索引：到底差在哪？

我做个对比，你一看就明白：

对比维度	正排索引	倒排索引
数据结构	文档ID → 词列表	词 → 文档ID列表
查询方式	遍历所有文档	直接定位词
查询速度	慢（O(n)）	快（O(1)）
存储空间	较小	较大（需要额外索引）
适用场景	全文遍历、文档更新频繁	关键词搜索、全文检索

说白了，正排索引就像图书馆的书架——你想找某本书，得挨个书架看。倒排索引就像图书目录卡——直接查“计算机”分类，就能找到所有相关书籍。

核心数据结构：词典 + 倒排列表

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

1. 词典（Dictionary）

词典就是所有“词”的集合。它负责回答一个问题：“这个词在不在索引里？”

词典的存储方式，我见过三种：

• 哈希表：查询快，但内存占用大。适合小规模数据。
• B树/B+树：支持范围查询，磁盘友好。适合大规模数据。
• 跳表（Skip List）：查询效率高，实现简单。我比较喜欢用这个。

嗯，这里要注意：词典的设计直接影响查询性能。我曾在项目中用哈希表存了500万个词，结果内存爆了。后来换成B+树，内存降了60%。

2. 倒排列表（Posting List）

倒排列表就是“这个词出现在哪些文档里”。每个条目叫一个“倒排项”（Posting），通常包含：

• 文档ID：文档的唯一标识
• 词频（TF）：这个词在文档中出现了几次
• 位置信息：在文档中的具体位置（第几个词）

举个例子：

词：“搜索引擎”
倒排列表：
  → 文档ID: 1, TF: 3, 位置: [12, 45, 78]
  → 文档ID: 3, TF: 1, 位置: [23]
  → 文档ID: 7, TF: 2, 位置: [56, 89]

你看，不仅知道哪些文档包含这个词，还知道出现次数和位置。这就是搜索引擎能高亮关键词的原因。

倒排索引的构建流程

我简单说下构建过程，让你有个整体印象：

1. 分词：把文档拆成一个个词。中文分词比英文复杂得多。
2. 去停用词：去掉“的”、“了”、“是”这类高频无意义词。
3. 统计词频：记录每个词在每篇文档中出现的次数和位置。
4. 排序：按词排序，相同词的文档ID合并。
5. 写入磁盘：词典和倒排列表分别存储。

你想想看，这个过程其实挺直观的。但实际做起来，坑不少。比如中文分词，我遇到过“南京市长江大桥”被分成“南京/市长/江大桥”的尴尬事。

存储优化：别让索引吃掉你的磁盘

倒排索引的存储是个大问题。我见过一个项目，索引文件比原始数据大了10倍。怎么优化？

几个常用手段：

• 压缩倒排列表：用变长编码（如Varint）存储文档ID差值。
• 分块存储：把大索引拆成多个小段，查询时只加载相关段。
• 词典前缀压缩：共享相同前缀的词，比如“计算机”、“计算器”共享“计算”。
• 跳表加速：在倒排列表里加跳指针，加快合并查询。

小结

倒排索引的核心就三点：

• 词典：存所有词，支持快速查找
• 倒排列表：存词对应的文档列表
• 存储优化：压缩、分块、跳表

说白了，倒排索引就是“空间换时间”的典型代表。它用额外的存储换来了极致的查询速度。你想想看，没有它，搜索引擎怎么可能在毫秒级返回结果？

下一章，我会讲倒排索引的构建细节，包括分词、排序、合并这些实战内容。到时候咱们再聊。