面试官：倒排索引是什么？从 Lucene 三层结构到 Java 实现

在云栈社区的技术论坛里，这道面试题出现的频率相当高。面试官问一句“倒排索引是什么？”，看似在考概念，实际上会根据你的回答一路追问到存储结构、查询链路甚至压缩算法。今天我们就把它彻底拆解一遍，从原理到代码实现都给安排上。

面试考察点

基础掌握度：面试官不只想听你背定义，还想知道你是否理解它和正排索引的区别，以及全文检索为什么非用这种结构不可。

原理理解深度：倒排索引不是一张简单的“词 → 文档”映射表，它内部还有 Term Index、Term Dictionary、Posting List 这些分层设计。能不能讲清楚这三层，是“用过 ES”和“懂 ES”的分水岭。

知识延伸能力：这道题只是入口，面试官大概率会顺着往下问：“ES 为什么查询快”“FST 是什么”“Posting List 怎么压缩”，追问几轮就知道你的知识面到底有多深。

核心答案

先说结论：倒排索引（Inverted Index）是一种“从词条反向映射到文档列表”的数据结构，它是 Elasticsearch 全文检索的地基。ES 查询快，根子就在这里。

一句话理解：正排索引回答“这篇文档里有哪些词”，倒排索引回答“哪些文档里有这个词”。

对比项	正排索引	倒排索引
映射方向	文档 → 词	词 → 文档
查询方式	逐篇扫描，匹配关键词	拿词直接定位文档列表
查询效率	O(N)，文档越多越慢	近似 O(1)，跟文档总量关系不大
典型场景	按 ID 查详情、排序取值	关键词搜索、全文检索
谁在用	MySQL（B+ 树主键查询）	ES、Lucene 的核心结构

深度解析

一、先看一个例子，秒懂什么是“倒排”

假设我们有三篇文档：

• 文档 1：“犬小哈学 Elasticsearch”
• 文档 2：“Elasticsearch 倒排索引详解”
• 文档 3：“犬小哈的 Java 教程”

建索引时，ES 会先分词，再把结果“倒”过来——以词为 key，把包含这个词的文档 ID 挂在它名下：

上图就是倒排索引的工作方式，拆开来看：

• 建索引阶段：每篇文档写入时先经过分词器（Analyzer）切分成一个个词条（Term），然后维护一张“词条 → 文档 ID 列表”的映射表。
• 查询阶段：用户输入“犬小哈”，分词后拿这个词直接去映射表里查，一步就拿到文档 1 和 3，全程不需要扫描任何一篇原文档。
• 关键优势：文档从 1 万涨到 1 亿，查一个词的耗时几乎不变——因为你只是在查一张词典，而不是在扫全量文档。

MySQL 的 LIKE '%关键词%' 为什么慢？就是因为它只能全表扫描，本质上是拿正排的思路干倒排的活，数据量一大必死。

二、倒排索引的内部结构：三层设计

面试官听到你讲完上面的例子，大概率会追问一句：“那这个倒排索引内部是怎么组织的？”这才是这道题的加分项。

倒排索引在 Lucene 里由三部分组成：

这三层各自的作用：

• Term Index（词条索引）：词典可能非常大，没法全放内存。所以 Lucene 用 FST（Finite State Transducer，有限状态转换器） 对词条做前缀索引，体积小到可以常驻内存，作用类似词典的“目录”，告诉你某个前缀在磁盘词典的哪个块里。
• Term Dictionary（词条字典）：所有词条排序后存在磁盘上。因为是有序的，配合 Term Index 定位到块之后，块内二分查找即可。
• Posting List（倒排列表）：每个词条对应的文档信息列表，包含文档 ID、词频（TF）、位置（Position，用于短语匹配）、偏移（Offset，用于高亮）。

这套设计就是典型的“内存放目录、磁盘放数据”，跟 MySQL 的 B+ 树三层结构思想相通，只是实现完全不同。

三、Posting List 的压缩与合并

Posting List 里动辄几百万个文档 ID，Lucene 做了两件聪明事：

1. FOR 压缩（Frame of Reference）：文档 ID 本身是递增的，所以不存原始值，改存相邻 ID 的差值（增量编码），再用位压缩存储，大幅省空间。
2. Roaring Bitmaps（跳跃数组 + 位图）：用于 filter 查询的缓存。查询时多个条件的 Posting List 要做交集/并集，Roaring Bitmap 让这种集合运算又快又省内存。

这就是 ES 做 filter 查询（不算相关性评分的场景）特别快的原因，本质就是对多个有序文档 ID 列表做高效集合运算。

四、写个 Java 例子直观感受一下

如果让你自己用 Java 实现一个最简陋的倒排索引，核心就是一个 Map：

import java.util.*;

public class SimpleInvertedIndex {

    // 倒排索引核心结构: 词条 -> 包含该词条的文档 ID 集合
    private final Map<String, Set<Integer>> invertedIndex = new HashMap<>();

    // 正排索引: 文档 ID -> 文档原文, 用于查询命中后取回原文
    private final Map<Integer, String> forwardIndex = new HashMap<>();

    public void addDocument(int docId, String content) {
        // 1. 正排: 记住原文
        forwardIndex.put(docId, content);
        // 2. 分词: 真实场景用的是 IK / standard 等分词器, 这里简单按空格切
        String[] terms = content.toLowerCase().split("\\s+");
        // 3. 倒排: 把文档 ID 挂到每个词条名下
        for (String term : terms) {
            invertedIndex.computeIfAbsent(term, k -> new HashSet<>()).add(docId);
        }
    }

    public Set<Integer> search(String term) {
        // 查询: O(1) 直接拿词换文档列表, 这就是倒排索引的威力
        return invertedIndex.getOrDefault(term.toLowerCase(), Collections.emptySet());
    }

    public static void main(String[] args) {
        SimpleInvertedIndex index = new SimpleInvertedIndex();
        index.addDocument(1, "犬小哈 学 elasticsearch");
        index.addDocument(2, "elasticsearch 倒排索引 详解");
        index.addDocument(3, "犬小哈 的 java 教程");

        System.out.println(index.search("犬小哈"));        // 输出: [1, 3]
        System.out.println(index.search("elasticsearch")); // 输出: [1, 2]
    }
}

这个例子虽然简陋（真实 Lucene 的分词、压缩、持久化要复杂得多），但核心思想完全一致：写入时多花点功夫建好映射，查询时就能拿词一步换到文档列表。空间换时间的经典套路。

面试高频追问

1. ES 为什么查询快，写入却相对慢？

查询快靠倒排索引直接定位；写入慢是因为要经历分词、建倒排、写 segment、可能 refresh 等一整套流程。近实时（NRT）就是这两者权衡的产物。

2. FST 是什么？为什么用它做 Term Index？

有限状态转换器，可以理解为前缀树（Trie）的极致压缩版。它用极小的内存共享前缀和后缀，还能把“词 → 块地址”的映射直接编码在状态转移里，非常适合常驻内存的词典目录。

3. 什么是正排索引？ES 里正排索引用来干什么？

文档 → 字段值的映射。ES 的 _source、doc_values（用于排序和聚合）本质上都是正排思想的体现，倒排负责“找得到”，正排负责“取得出”。

4. doc_values 和倒排索引是什么关系？

倒排适合搜索，不适合排序聚合；doc_values 是列式存储的正排结构，排序、聚合、脚本取值都靠它。

常见面试变体

• “ES 为什么适合做全文检索，用 MySQL 的 LIKE 不行吗？”
• “倒排索引是怎么建出来的？讲讲写入的完整流程”
• “Term Dictionary 和 Term Index 分别是什么？为什么要分开？”
• “ES 的 filter 为什么比 query 快？跟倒排索引有什么关系？”

记忆口诀

方向记反就完蛋：正排“文找词”，倒排“词找文”；三层结构一口诀：内存 FST 指路，磁盘词典排队，帖表（Posting List）拎着文档 ID 走。

总结

倒排索引就是“词条 → 文档列表”的反向映射，用写入时多干活换查询时近乎 O(1) 的定位能力，内部靠 Term Index（FST）+ Term Dictionary + Posting List 三层结构支撑。把这套结构讲明白，再带一句 FOR 压缩和 Roaring Bitmap，这道题基本就是你的送分题。