从零构建现代搜索引擎（07）：第一张倒排索引

上一篇把文本切成了词项流。但词项流只是一个线性序列——要回答"哪些文档包含’Java’"这个问题，仍然需要扫描所有文档的词项流。1000 篇文档还能忍受，10 万篇就不行了。

倒排索引（inverted index）把"文档包含哪些词"的关系翻转成"每个词出现在哪些文档中"。查询时只需要查一次词典，就能拿到所有包含该词的文档列表，不需要扫描任何一篇文档的全文。

从正排到倒排

正排索引（forward index）是文档到词项的映射：

doc1 → [java, 内存, 模型, gc, 调优]
doc2 → [java, 线程, 池, 并发]
doc3 → [python, 内存, 管理]

查询 “java” 需要扫描全部 3 篇文档。

倒排索引把方向翻转：

java   → [doc1, doc2]
内存   → [doc1, doc3]
模型   → [doc1]
gc     → [doc1]
调优   → [doc1]
线程   → [doc2]
池     → [doc2]
并发   → [doc2]
python → [doc3]
管理   → [doc3]

查询 “java” 直接定位到 [doc1, doc2]，时间复杂度从 O(N) 降到 O(1) 词典查找 + O(k) 遍历结果列表（k 是包含该词的文档数）。

核心数据结构

倒排索引由三个部分组成：

词项字典（Term Dictionary）

存储所有出现过的词项，每个词项指向对应的倒排列表。最简单的实现是 HashMap<String, PostingList>。

生产级实现用 FST（Finite State Transducer）或前缀树压缩存储，Lucene 的 BlockTreeTermsReader 就是 FST。教学版本用 HashMap 足够，万级词项的查找仍然是 O(1)。

倒排列表（Posting List）

每个词项对应一个倒排列表，记录包含该词项的所有文档及相关统计信息。列表按 docId 升序排列——这个排序是 AND/OR 查询高效执行的前提。

public record Posting(
    int docId,
    int termFreq,
    int[] positions
) implements Comparable<Posting> {
    @Override
    public int compareTo(Posting o) {
        return Integer.compare(this.docId, o.docId);
    }
}

• docId：文档的内部编号（递增整数，第 02 篇的业务 docId 另存）
• termFreq：该词项在该文档中出现的次数（BM25 需要）
• positions：该词项在该文档中出现的位置列表（短语查询需要）

文档长度表

每篇文档的总词项数，用于 BM25 的长度归一化。

int[] docLengths; // docLengths[docId] = 文档总词数

构建过程

索引构建分两步：收集和整理。

收集阶段

逐篇处理文档，将每个 token 的出现记录到临时结构中：

// term → [(docId, position), ...]
Map<String, List<int[]>> tempIndex = new HashMap<>();
int[] docLengths = new int[maxDocs];
int nextDocId = 0;

void indexDocument(String text) {
    int docId = nextDocId++;
    List<Token> tokens = analyzer.analyze(text);
    docLengths[docId] = tokens.size();

    for (Token token : tokens) {
        tempIndex.computeIfAbsent(token.term(), k -> new ArrayList<>())
            .add(new int[]{docId, token.position()});
    }
}

整理阶段

收集完成后，将临时结构转换为不可变的倒排索引：

Map<String, PostingList> index = new HashMap<>();

for (var entry : tempIndex.entrySet()) {
    String term = entry.getKey();
    List<int[]> records = entry.getValue();

    // 按 docId 分组
    Map<Integer, List<Integer>> byDoc = new TreeMap<>();
    for (int[] rec : records) {
        byDoc.computeIfAbsent(rec[0], k -> new ArrayList<>())
            .add(rec[1]);
    }

    // 构建 Posting 列表
    List<Posting> postings = new ArrayList<>();
    for (var docEntry : byDoc.entrySet()) {
        List<Integer> positions = docEntry.getValue();
        postings.add(new Posting(
            docEntry.getKey(),
            positions.size(),
            positions.stream().mapToInt(Integer::intValue).toArray()
        ));
    }

    index.put(term, new PostingList(postings));
}

TreeMap 保证按 docId 排序。整理后的 PostingList 是不可变的——构建阶段结束后不再修改，查询阶段并发读取无需加锁。

查询执行

单词查询

最简单的查询：查词典，返回倒排列表中所有文档。

List<Integer> search(String queryTerm) {
    PostingList pl = index.get(queryTerm.toLowerCase());
    if (pl == null) return List.of();
    return pl.docIds();
}

AND 查询

两个词项的 AND 查询等于两个倒排列表的交集。由于列表按 docId 排序，双指针归并在 O(m+n) 时间内完成：

List<Integer> and(PostingList a, PostingList b) {
    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        int da = a.docId(i), db = b.docId(j);
        if (da == db) {
            result.add(da);
            i++; j++;
        } else if (da < db) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

查询 “java AND 内存”：先取 “java” 的列表 [doc1, doc2]，再取 “内存” 的列表 [doc1, doc3]，交集得 [doc1]。

OR 查询

两个倒排列表的并集。双指针同步推进，不跳过任何一方的文档：

List<Integer> or(PostingList a, PostingList b) {
    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        int da = a.docId(i), db = b.docId(j);
        if (da == db) {
            result.add(da);
            i++; j++;
        } else if (da < db) {
            result.add(da);
            i++;
        } else {
            result.add(db);
            j++;
        }
    }
    while (i < a.size()) result.add(a.docId(i++));
    while (j < b.size()) result.add(b.docId(j++));
    return result;
}

查询 “java OR python”：[doc1, doc2] 并 [doc3] 得 [doc1, doc2, doc3]。

不存在的词

查询一个不在词典中的词，返回空列表。AND 一个空列表与任何列表的交集都是空。这是正确行为：搜索一个不存在的词应该返回零结果。

与顺序扫描对照

第 01 篇实现了顺序扫描搜索。验证倒排索引的结果与顺序扫描一致。

对照方法：准备一组查询，分别用两种方式执行，比较返回的 docId 集合。

void verify(String query, SequentialSearcher seq, InvertedIndex idx) {
    Set<Integer> seqResult = new TreeSet<>(seq.search(query));
    Set<Integer> idxResult = new TreeSet<>(idx.search(query));
    assert seqResult.equals(idxResult)
        : "Mismatch for '" + query + "': seq=" + seqResult
          + " idx=" + idxResult;
}

两边必须使用相同的分析器。如果顺序扫描用的是子字符串匹配而倒排索引用的是词项精确匹配，结果会不同——这不是 bug，而是匹配语义的差异。对照时统一为"文档经过分析后产出的词项集合中包含查询词项"。

测试覆盖：

查询类型	示例	预期
单词	“java”	两边返回相同 docId 集合
AND	“java AND 内存”	交集一致
OR	“java OR python”	并集一致
不存在的词	“xyznotexist”	两边都返回空
空查询	“”	两边都返回空

内存占用估算

倒排索引的内存开销主要来自三个部分：

词项字典：HashMap 的每个 entry 需要约 48 字节（key 引用 + value 引用 + hash + next 指针 + 对象头）加上 String 对象本身。1 万个不同词项约 0.5-1 MB。

倒排列表：每条 Posting 包含一个 int（4B）、一个 int（4B）和一个 int[]。不含 positions 时约 24 字节/posting（含对象头）。1000 篇文档、平均 500 个不同词项/篇，约 50 万条 posting，占用约 12 MB。

positions 数组：如果记录位置信息（短语查询需要），每个位置占 4 字节。平均每条 posting 有 2 个位置，额外增加 50 万 × 2 × 4 = 4 MB。

总计：1 万词项 + 1000 篇文档 ≈ 15-20 MB。对教学场景完全在内存中可行。

超过万级文档时，内存放不下完整索引，需要分批构建段文件（segment）再合并——第 10 篇的主题。

倒排索引为什么快

顺序扫描 1000 篇文档，每篇平均 1000 个词项，单次查询需要比较 100 万个词项。倒排索引查一次词典（HashMap O(1)），再遍历倒排列表中平均几十到几百条 posting。差距在两到三个数量级。

AND 查询的加速更明显。顺序扫描需要对每篇文档检查是否同时包含所有查询词。倒排索引只需要对两个排序列表做一次归并，跳过大量不可能匹配的文档。

但倒排索引也有代价：构建时间（需要遍历所有文档）和存储空间（倒排列表加上词典）。对搜索引擎来说这是值得的——索引构建是一次性的，查询是频繁的。

当前局限

• 索引完全在内存中，不支持持久化——重启丢失
• 没有评分排序——所有匹配文档按 docId 返回，不按相关性
• 没有短语查询——AND 只检查共现，不检查位置
• 没有字段区分——标题和正文混在一起索引

这些限制在接下来的章节逐步解决：第 08 篇加入短语查询和布尔逻辑，第 09 篇加入 BM25 评分，第 10 篇解决磁盘持久化。

练习

1. 用 5 篇短文档手工构建倒排索引（纸上完成），验证对 “term1 AND term2” 的双指针归并结果
2. 实现 NOT 查询（从一个列表中排除另一个列表的文档），思考它与 AND/OR 的组合
3. 对 1000 篇 fixture 文档构建索引，统计词典大小、平均倒排列表长度和内存占用
4. 将单词查询的平均响应时间与顺序扫描对比，记录文档数从 100 到 1000 的加速比
5. 找一个出现在所有文档中的高频词（如"的"），观察它的倒排列表长度，思考这对查询性能的影响

延伸阅读

• Introduction to Information Retrieval, Chapter 1: Boolean retrieval
• Introduction to Information Retrieval, Chapter 2: The term vocabulary and postings lists
• Lucene 源码：org.apache.lucene.index.TermsEnum、org.apache.lucene.index.PostingsEnum