倒排索引介绍
好的，倒排索引是一种高效的信息检索数据结构，常用于搜索引擎和数据库系统中。以下是它的介绍：
1. 基本概念
倒排索引（Inverted Index）的核心思想是将「文档-词汇」的正向关系转换为「词汇-文档」的逆向关系。与传统索引（文档指向词汇）不同，它通过词汇快速定位包含该词汇的文档集合。
2. 核心结构
倒排索引主要由两部分组成：
- 词项字典（Term Dictionary）：存储所有不重复的词汇，并关联到倒排记录表。
- 倒排记录表（Postings List）：每个词项对应一个列表，记录包含该词项的文档ID（及位置、频率等元数据）。
例如：
词项“算法” → 文档ID：{101, 205, 307}
词项“数据结构” → 文档ID：{101, 307}
3. 查询流程
当用户输入查询词（如“算法”）时：
- 在词项字典中定位该词项
- 获取对应的倒排记录表
- 返回表中所有文档ID
多词查询（如“算法 AND 数据结构”）可通过集合交集快速实现： $$ {101, 205, 307} \cap {101, 307} = {101, 307} $$
4. 优势与适用场景
- 高效检索：时间复杂度可接近$O(1)$（哈希表实现）或$O(\log n)$（树结构）
- 支持复杂查询：布尔运算（AND/OR/NOT）、短语搜索等
- 典型应用：搜索引擎、文档数据库、代码搜索引擎
类比理解
类似书籍末尾的「索引」：通过关键词（如“牛顿定律”）直接找到出现该关键词的页码，而非逐页翻阅全书。
倒排索引通过空间换时间的策略，成为大规模文本检索系统的基石技术。