倒排索引
概述
倒排索引（Inverted Index）是搜索引擎的核心数据结构：将词条→文档的映射颠倒为词条→包含该词条的文档列表，使查询从 O(N) 全表扫描降至 O(1) 词典查找 + O(k) 遍历。
关键内容
- 核心结构三层：
- 词典（Term Dictionary）：内存驻留，
term → (term_id, df, offset)，支持快速查找。实现方式：哈希表（O(1) 精确查找）、B+树（支持范围查询）、Trie（前缀匹配）、FST（Lucene 用，共享前缀+后缀，最省空间）。 - Posting Lists：磁盘存储，按需加载。每个词条的文档列表，按 doc_id 升序排列。
-
文档元数据：文档长度（BM25 必需）、字段信息。
-
Posting 三种粒度：
- 基础（doc_id only）：布尔检索
- 带词频（doc_id + tf）：TF-IDF / BM25 评分
-
带位置（doc_id + tf + positions）：短语查询、近邻查询
-
差值编码（Delta Encoding）：Posting list 的 doc_id 有序升序，存储差值而非原值（差值通常远小于原值），配合变长编码大幅压缩，详见索引压缩。
-
构建算法：
- BIIP：小规模，完全装入内存
- SPIMI（Single-Pass In-Memory Indexing）：大规模，O(T) 时间，分批写出临时块再归并，比基于排序的 BSBI 更快
-
MapReduce：超大规模分布式，Map 阶段 emit (term, (doc_id, tf))，Reduce 阶段排序生成 Posting List
-
Posting 合并算法：AND 查询用双指针交集 O(|p1|+|p2|)；Skip Pointers 跳表加速大 posting list 合并（每隔 √n 设跳指针）。
-
索引更新策略：全量重建（简单但延迟高）；增量索引（主索引+辅助索引，定期合并）；NRT 近实时（Elasticsearch：1s Refresh → 内存 Segment 可搜索，30min Flush 持久化）。
来源
raw/articles/ai-engineering/search-retrieval/03_inverted_index.md— 传统搜索引擎深度解析系列 第3篇