从零构建现代搜索引擎（10）：内存装不下时怎样建立索引

前面九篇的倒排索引和 BM25 有一个隐含假设：所有文档在内存里放得下。50 篇文档确实没问题。但把数据集扩展到 10,000 篇、每篇平均 2,000 词时，仅 (词项, docID) 对就可能有几千万条，单次排序的内存需求轻松超过 JVM 默认堆。

这不是"用更大的机器"就能解决的问题。即使加到 32 GB 内存，真实语料还是可能更大。需要一种策略：把内存装不下的数据分批处理，每一批写成磁盘上的段文件（segment），最后把所有段合并成完整索引。

分批建立索引

朴素方案的瓶颈

第 07 篇的索引构建把所有文档一次性塞进 HashMap：

Map<String, List<Integer>> index = new HashMap<>();
for (Document doc : allDocs) {
    for (String term : analyze(doc.content())) {
        index.computeIfAbsent(term, k -> new ArrayList<>()).add(doc.id());
    }
}

假设 10,000 篇文档平均 2,000 词，分析后约 1,500 个词项/篇，posting 总条目约 1,500 万。每个 Integer 对象 16 字节，加上 ArrayList 的数组、HashMap 的 Entry——实际内存远超数据本身大小。Java 对象头的开销在小对象上尤其明显。

SPIMI：Single-Pass In-Memory Indexing

SPIMI 的做法是：内存装不下就不装。每次只处理一批文档，在内存中构建一个小的倒排索引，写入磁盘成为一个段文件，然后清空内存处理下一批。

int memoryBudget = 64 * 1024 * 1024; // 64 MB
Map<String, List<Integer>> currentBlock = new HashMap<>();
int estimatedSize = 0;
int segmentCount = 0;

for (Document doc : documentStream) {
    for (String term : analyze(doc.content())) {
        currentBlock.computeIfAbsent(term, k -> new ArrayList<>()).add(doc.id());
        estimatedSize += 20; // 粗估每个 posting 的内存成本
    }

    if (estimatedSize >= memoryBudget) {
        writeSegment(currentBlock, segmentCount++);
        currentBlock.clear();
        estimatedSize = 0;
    }
}

if (!currentBlock.isEmpty()) {
    writeSegment(currentBlock, segmentCount++);
}

SPIMI 不需要预先建立词项到 ID 的映射——直接用字符串作 key，每个段文件独立包含自己的词典。这使得它可以处理任意规模的语料，只要磁盘够大。

另一种更早的做法是 BSBI（Blocked Sort-Based Indexing），它先把 (termID, docID) 对全部收集再排序。BSBI 需要全局 termID 映射表，而 SPIMI 省掉了这一步，在内存利用率上更好。

段文件格式

段文件需要一个结构使得后续合并可以顺序读取。最简单的设计：

[Header]
  magic: "SIDX" (4 bytes)
  version: 1 (4 bytes)
  termCount (4 bytes)
  checksum (4 bytes, CRC32)

[Term Dictionary] — 按词项字典序排列
  termLength (2 bytes)
  termBytes (variable)
  docFreq (4 bytes)
  postingOffset (8 bytes, 指向 Posting 区域的偏移)

[Posting Lists]
  每个词项的 docID 列表，用 delta + VByte 编码

词典按字典序排列是关键——合并时可以像归并排序一样同时扫描多个段。

为什么不用 JSON 或纯文本

段文件用二进制格式而非 JSON/文本，原因有三：

1. 空间效率：10 万个 docID 用 JSON 数组约 800 KB，VByte 编码后约 120 KB
2. 解析速度：二进制格式直接读字节，JSON 需要词法分析和数值转换
3. 定位能力：postingOffset 允许跳过不需要的词项，直接定位目标词项的 posting list

Delta 编码与 VByte

Delta 编码

Posting list 中的 docID 是递增排列的。存储绝对值浪费空间：

原始 docID:  [3, 5, 20, 21, 23, 76]
delta (gap): [3, 2, 15,  1,  2, 53]

第一个值保持原样，后续每个值只存与前一个的差（gap）。高频词的 posting list 中 docID 分布密集，gap 通常很小——大量的 1、2、3——可以用更少的字节表达。

VByte 编码

Variable Byte 编码用变长字节表示整数。每个字节的最高位是 continuation bit：1 表示这是最后一个字节，0 表示后续还有。低 7 位是数据。

void encodeVByte(int value, OutputStream out) throws IOException {
    byte[] buf = new byte[5]; // int 最多 5 个 VByte 字节
    int pos = 4;
    buf[pos] = (byte) ((value & 0x7F) | 0x80); // 最后一个字节，continuation=1
    value >>>= 7;
    while (value > 0) {
        buf[--pos] = (byte) (value & 0x7F); // continuation=0
        value >>>= 7;
    }
    out.write(buf, pos, 5 - pos);
}

int decodeVByte(InputStream in) throws IOException {
    int result = 0;
    int b;
    do {
        b = in.read();
        result = (result << 7) | (b & 0x7F);
    } while ((b & 0x80) == 0);
    return result;
}

编码示例：

gap	二进制	VByte 字节	字节数
1	1	10000001	1
5	101	10000101	1
127	1111111	11111111	1
128	10000000	00000001 10000000	2
214577	…	00001101 00001100 10110001	3

gap < 128 只需 1 字节。对高频词（gap 通常很小），压缩率很高。

压缩效果对比

假设 posting list 有 10,000 个 docID，总文档数 100,000：

编码方式	每个 docID 字节数	总字节
固定 4 字节 int	4	40,000
Delta + VByte	约 1.5（取决于分布）	约 15,000

压缩到原来的 37%。对低频词（gap 大）效果没这么好，但低频词的 posting list 本身就短，绝对空间不大。

K-way 合并

合并流程

10 个段文件合并成一个完整索引，用优先队列实现 k-way merge：

void mergeSegments(List<SegmentReader> segments, SegmentWriter output) {
    // 优先队列按当前词项的字典序排列
    PriorityQueue<SegmentReader> pq = new PriorityQueue<>(
        Comparator.comparing(SegmentReader::currentTerm));

    for (SegmentReader seg : segments) {
        if (seg.hasNext()) {
            seg.advance();
            pq.offer(seg);
        }
    }

    while (!pq.isEmpty()) {
        String term = pq.peek().currentTerm();

        // 取出所有当前词项相同的段
        List<int[]> postingsToMerge = new ArrayList<>();
        while (!pq.isEmpty() && pq.peek().currentTerm().equals(term)) {
            SegmentReader seg = pq.poll();
            postingsToMerge.add(seg.currentPostings());
            if (seg.hasNext()) {
                seg.advance();
                pq.offer(seg);
            }
        }

        // 合并 posting lists（已排序，做归并）
        int[] merged = mergePostingLists(postingsToMerge);
        output.writeTerm(term, merged);
    }
}

每个段的词典已按字典序排列，合并时优先队列确保全局字典序。同一词项在多个段中出现时，各段的 posting list 合并（docID 已排序，做归并即可）。

合并的 I/O 模式

合并是顺序读、顺序写——对磁盘最友好的访问模式。不需要随机寻址。这就是为什么段文件内部按字典序排列：它把合并变成了一次线性扫描。

正确性验证

合并后的索引与"假设内存无限、一次性建立的索引"必须完全一致。验证方法：

1. 用小数据集（100 篇文档），分别用一次性方式和分 5 段合并方式建索引
2. 对 10 个查询分别执行，比较返回的 docID 集合和 BM25 分数
3. 任何不一致都是 bug

损坏检测

段文件写入过程可能因程序崩溃、磁盘故障而中断。不检测损坏的后果是读到错误数据，返回错误的搜索结果——而且可能不报错，只是结果静默出错。

CRC32 校验：

void writeSegment(SegmentData data, Path path) throws IOException {
    byte[] payload = serializePayload(data);
    CRC32 crc = new CRC32();
    crc.update(payload);

    try (var out = new DataOutputStream(Files.newOutputStream(path))) {
        out.writeInt(0x53494458); // magic "SIDX"
        out.writeInt(1);          // version
        out.writeInt(data.termCount());
        out.writeInt((int) crc.getValue());
        out.write(payload);
    }
}

SegmentData readSegment(Path path) throws IOException {
    try (var in = new DataInputStream(Files.newInputStream(path))) {
        int magic = in.readInt();
        if (magic != 0x53494458) throw new IOException("不是段文件");
        int version = in.readInt();
        int termCount = in.readInt();
        int storedChecksum = in.readInt();

        byte[] payload = in.readAllBytes();
        CRC32 crc = new CRC32();
        crc.update(payload);
        if ((int) crc.getValue() != storedChecksum) {
            throw new IOException("段文件损坏：checksum 不匹配");
        }
        return deserializePayload(payload, termCount);
    }
}

这不是完整的持久性保证——写入中断时可能产生半截文件。完整的 crash recovery（预写日志、原子重命名）留给第 12 篇处理。本篇只保证：能识别损坏的段文件并拒绝使用。

内存受限下的端到端流程

完整流程：

文档流 ──→ SPIMI ──→ 段文件 0
                 ──→ 段文件 1
                 ──→ ...
                 ──→ 段文件 k

段文件 0..k ──→ K-way merge ──→ 最终索引文件

配置项只有一个：内存预算（memoryBudget）。预算越小，段文件越多，合并 I/O 越大。预算越大，段文件越少，合并越快。两者之间有平衡点，但对教学规模来说无需调参——64 MB 足够。

当前局限

• 段文件格式是教学级的，不兼容 Lucene 的段格式——第 15 篇迁移
• 没有实现增量索引（新文档到来时追加）——本篇只处理静态语料的一次性构建
• 合并策略是全量合并，没有分层（Tiered Merge Policy）——第 12 篇讨论
• VByte 不是最快的解码方式，PForDelta 在 SIMD 下更快——但教学场景不需要
• crash recovery 只有检测，没有恢复——第 12 篇补充

练习

1. 将第 07 篇的索引构建改为 SPIMI：设定 memoryBudget = 1 MB，用 50 篇文档验证分段后合并的结果与一次性构建一致
2. 实现 VByte 编码和解码，用 [1, 2, 127, 128, 100000] 作为测试用例
3. 故意在段文件中翻转一个字节，验证 CRC32 检测到损坏
4. 对比 delta + VByte 和不压缩的段文件大小，记录压缩率
5. 用 3 个段文件和 2 个共有词项，手工跟踪 k-way merge 的优先队列变化

延伸阅读

• Introduction to Information Retrieval, Chapter 4: Index Construction
• Introduction to Information Retrieval, Chapter 5: Index Compression
• Heinz, S. & Zobel, J. (2003). Efficient Single-Pass Index Construction for Text Databases. JASIST, 54(8).
• Lucene 源码：org.apache.lucene.index.TieredMergePolicy