第1章索引基础回顾

1. 索引基础回顾：倒排索引原理、正排索引与倒排索引对比、索引的存储结构（跳表、FST）

好，咱们正式开始。在聊实时索引之前，我觉得有必要先把地基夯实一下。毕竟，你连倒排索引长什么样都不清楚，后面谈什么增量合并、内存 Flush，那都是空中楼阁。

这一节，我带你快速过一遍索引的核心概念。嗯，都是干货，没有废话。

说白了，倒排索引就是一本「词典」。你想想看，我们平时查新华字典，是通过拼音找到字在哪一页。搜索引擎也一样，用户输入一个词，它得立刻知道这个词出现在哪些文档里。

举个例子，假设我们有三个文档：

文档1：我喜欢吃苹果
文档2：苹果很好吃
文档3：我喜欢吃香蕉

正着存（正排索引），就是文档ID -> 内容。但用户搜「苹果」时，你得遍历所有文档，效率极低。

倒排索引的做法是反过来：

苹果 -> [文档1, 文档2]
喜欢 -> [文档1, 文档3]
吃   -> [文档1, 文档3]
香蕉 -> [文档3]

你看，每个词后面挂着一个链表，记录哪些文档包含这个词。搜索「苹果」时，直接查词典，拿到文档列表，完事。

核心要点：倒排索引的本质是「词 -> 文档ID列表」的映射。这是搜索引擎的基石，没有它，一切免谈。

我在项目中遇到过一个问题：有人把倒排索引理解成了「反向索引」，觉得就是把文档倒过来存。其实不是。它倒的是「映射方向」，不是文档本身。这个坑，我见过不少人踩过。

咱们直接上表格，一目了然。

你可能会问：那正排索引是不是就没用了？当然不是。我个人的习惯是，倒排索引负责「搜」，正排索引负责「取」。比如你搜到一篇文档的ID，然后需要展示标题、摘要、发布时间，这时候就得靠正排索引去拿原始字段。

说白了，两者是搭档，不是对手。

好，原理讲完了。但词典和倒排链表在磁盘上怎么存？这就涉及到具体的数据结构了。我重点讲两个：跳表和FST。

跳表，说白了就是一个「带索引的链表」。普通链表查一个元素，得从头遍历，O(n) 复杂度。跳表在链表上建了几层「快速通道」，让你可以跳着走。

举个例子：

第3层: 1 -------------------------> 9
第2层: 1 -------> 5 -------> 9
第1层: 1 -> 3 -> 5 -> 7 -> 9

你想找7。从第3层开始，1比7小，走；9比7大，降一层。到第2层，1到5，5比7小，走；9比7大，再降一层。到第1层，5往后走一步就是7。总共走了3步，比遍历快多了。

我的经验：跳表在Lucene里主要用于存储倒排链表。为什么不用B+树？因为跳表实现简单，而且支持高效的并发更新。我曾经在优化一个实时索引时，把链表改成跳表，查询延迟直接降了40%。

嗯，这里要注意：跳表的层数是概率决定的，不是固定的。每个节点有50%的概率升到上一层。所以理论上，跳表的查询复杂度是 O(log n)，和平衡树差不多。

FST 这个东西，我第一次接触时也觉得挺玄乎。说白了，它是一种「压缩后的词典」。你想想看，词典里可能有几百万个词，每个词都存一遍，空间受不了。FST 通过共享前缀和后缀，把存储空间压到极致。

举个例子，假设词典里有这些词：

cat, cats, catty, dog, dogs

用 FST 存，大概是这个样子：

c -> a -> t -> (输出: cat)
           -> s -> (输出: cats)
           -> t -> y -> (输出: catty)
d -> o -> g -> (输出: dog)
           -> s -> (输出: dogs)

你看，「cat」这个前缀只存了一次。后面的分支共享了前面的路径。这就是 FST 的厉害之处。

避坑指南：我曾经在构建FST时，忽略了词条的排序要求。FST要求输入的词必须按字典序排序，否则构建出来的结构是错的。那次排查了整整一天，最后发现是排序问题。所以，记住：构建FST前，先排序。

FST 在 Lucene 里用于存储词典（Term Dictionary）。它有两个优点：一是内存占用小，二是支持前缀查询和模糊查询。你搜「cat*」，FST 可以快速定位到所有以 cat 开头的词。

这一节我们回顾了三个核心点：

我个人觉得，理解这些基础，比背一堆调优参数重要得多。你想想看，如果你连索引怎么存的都不知道，出了问题怎么排查？