📚 课程目录第1章倒排索引基础

1. 倒排索引基础

1.1 倒排索引定义

倒排索引（Inverted Index）是全文检索系统的核心数据结构，它通过“词项 → 文档”的映射关系，实现从关键词到包含该词文档的快速定位。与正排索引的“文档 → 词项”方向相反，倒排索引以词项为键、文档列表为值，是搜索引擎实现亚秒级响应的基石。

  核心思想：将文档集合中所有不重复的词项提取出来，为每个词项记录它出现过的文档编号及位置信息，从而将“扫描所有文档”的线性复杂度降为“查词项列表”的常数/对数复杂度。

1.2 文档-词项矩阵

文档-词项矩阵（Document-Term Matrix, DTM）是倒排索引的数学抽象，行代表文档，列代表词项，单元格值为词项在文档中的权重（如词频TF）。以下为3篇文档的DTM示例：

文档ID	倒排	索引	缓存	一致性
Doc1	2	1	0	0
Doc2	0	1	3	1
Doc3	1	0	1	2

实际工程中，DTM通常稀疏存储——只记录非零单元格，这正是倒排列表的雏形。

1.3 倒排列表结构

倒排列表（Posting List）是倒排索引的物理存储单元，每个词项对应一个倒排列表，包含以下核心字段：

文档ID（DocID）：词项出现的文档唯一标识，通常按升序排列以支持跳表合并。
词频（TF）：词项在该文档中出现的次数，用于BM25等相关性评分。
位置列表（Positions）：词项在文档中的偏移位置数组，支持短语查询和邻近搜索。
附加载荷（Payload）：可选字段，如词性标注、域信息（标题/正文）等。

// 倒排列表的简化内存结构示例（C语言风格）
struct Posting {
    uint32_t doc_id;        // 文档ID
    uint16_t term_freq;     // 词频
    uint32_t* positions;    // 位置数组指针
    uint8_t  payload_len;   // 载荷长度
    char*    payload;       // 载荷数据
};

// 词项"倒排"的倒排列表示例
PostingList inverted_list = {
    .term = "倒排",
    .postings = {
        { .doc_id = 1, .term_freq = 2, .positions = {15, 42} },
        { .doc_id = 3, .term_freq = 1, .positions = {7} }
    },
    .length = 2
};

工程要点：倒排列表的压缩是工业级搜索引擎的关键技术。常用算法包括：文档ID差分编码（Delta Encoding）、可变字节编码（VByte）、Simple9/16以及PForDelta等，可将存储空间压缩至原始大小的10%~30%。

1.4 与正排索引对比

正排索引（Forward Index）以文档为入口，记录文档包含的所有词项；倒排索引以词项为入口，记录词项出现的所有文档。两者在存储结构、查询场景和更新策略上存在本质差异：

对比维度	正排索引	倒排索引
映射方向	文档ID → 词项列表	词项 → 文档ID列表
典型查询	“文档1包含哪些词？”	“哪些文档包含‘倒排’？”
存储结构	文档级数组/哈希表	词项级跳表/位图
查询复杂度	O(1) 查文档，O(L) 遍历词项	O(1) 查词项，O(k) 合并文档列表
空间占用	与文档数成正比，冗余少	与词项数×文档频率成正比，需压缩
更新代价	追加文档即可，低	需更新多个倒排列表，高
主要用途	文档存储、字段检索、排序	关键词搜索、布尔查询、相关性排序

工程陷阱：许多初学工程师误以为倒排索引可以完全替代正排索引。实际上，搜索引擎通常同时维护两种索引：倒排索引用于快速定位候选文档集，正排索引用于获取文档完整字段、执行排序和摘要生成。两者协同工作，缺一不可。