企业官网建设流程全解析

Elasticsearch 倒排索引中词条索引原理分析 — 基于 Lucene FST

1. 概述

Elasticsearch 的倒排索引（Inverted Index）由三层结构组成：

Term Index（词条索引） → Term Dictionary（词条词典） → Posting List（倒排表） .tip 文件 .tim 文件 .doc / .pos 文件 FST 结构 Block Tree 分块存储 DocID、词频、位置 全部加载到内存 按需从磁盘加载 按需从磁盘加载

三层职责严格分离，不要混淆：

本文聚焦的是第一层 — Term Index 的底层数据结构 FST，由org.apache.lucene.util.fst.FST类实现。

FST vs Term Dictionary 的本质区别：

• FST（Term Index）只存每个 Block 的第一个词条，是"词典的索引"，量级很小
• Term Dictionary 存所有词条，数据量大，按 Block 分块存储在磁盘上
• 查询时：先用 FST 定位到目标 Block 的磁盘偏移 → 再从 .tim 文件加载该 Block → 在 Block 内二分查找目标词条 → 最后获取 Posting List

FST 本质上是一个带输出的有限状态自动机（FSA），它不仅能够判断某个输入字符串是否被接受（即是否存在），还能在匹配的同时输出与该词条关联的值（如指向 Term Dictionary Block 的磁盘偏移量）。

2. FST 核心概念

2.1 FSA vs FST

关系：FSA 是 FST 的特例（输出为空时 FST 退化为 FSA）。

2.2 FST 结构要素 — 理论与代码映射

FST 的理论定义：

FST = (States, Transitions, StartState, FinalStates)

每个要素的含义及其在 Lucene 源码中的对应：

关键设计理解：Lucene FST 中没有独立的 State 对象！

所有节点和边被紧凑地序列化到一个byte[]字节数组中：

• 一个"状态" =byte[]中的一个偏移量（long整数）
• 一个"边" = 从该偏移量开始的一段字节编码（通过FST.readFirstArc()/FST.readNextArc()解码）
• 这样做的好处是：零对象创建、GC 友好、可直接 mmap 磁盘文件

2.3 核心代码结构

// org.apache.lucene.util.fst.FSTpublicfinalclassFST<T>extendsAccountable{// 输入类型：BYTE1（单字节，ASCII）或 BYTE4（四字节，Unicode 码点）privatefinalINPUT_TYPEinputType;// === StartState ===// 起始节点在 bytes 数组中的偏移位置privatefinallongstartNode;// === States 的存储载体 ===// 所有节点和边紧凑序列化在此字节数组中// 没有独立的 State 对象，"状态" = 此数组的一个偏移量privatefinalFSTBytesbytes;// (新版 Lucene 使用 FSTBytes 封装)// === Transitions 的输出值类型 ===// 决定 output 的数据类型，如 POS_INTS_OFFSETS 表示正整数privatefinalOutputs<T>outputs;// === States / Transitions 的计数 ===privateintnodeCount;// 节点总数（States 的数量）privateintarcCount;// 边总数（Transitions 的数量）}// org.apache.lucene.util.fst.FST.Arc — 代表一条 Transition（边）publicstaticfinalclassArc<T>{// 输入标签：这条边匹配的字符（字节值）publicintlabel;// 输出值：沿这条边的输出（查询时沿路径累加）publicToutput;// 目标节点：这条边指向的状态节点在 bytes 中的偏移publiclongtarget;// === FinalState 判断 ===// 如果 target 指向的节点是终态，则 flags 中包含 BIT_FINAL_ARCpublicbyteflags;publicbooleanisFinal(){return(flags&BIT_FINAL_ARC)!=0;}// 同节点的下一条边（链式遍历同一状态的所有出边）publiclongnextArc;}

2.4 FST 的核心优势

1. 前缀共享：具有相同前缀的词条共享路径节点，大幅压缩空间
2. 后缀共享：具有相同后缀的词条在构建时可合并尾节点（minimization）
3. 空间压缩：FST 只存 Block 入口词条（稀疏采样），将 Term Index 压缩到 MB 级，可完全放入内存
4. 查询高效：时间复杂度为 O(len(term))，与词条数量无关

3. 举例：词条 “上海”、“上学”、“海上”、“上” 的 FST 构建

⚠️重要说明：本节示例 vs 生产环境的区别

本节（3.1 ~ 3.4）将4 个词条全部放入 FST，是为了讲解FST 数据结构的内部机制（前缀共享、增量编码）。

但在 Lucene生产环境中（见第 6 节），FST（Term Index）只存储每个 Block 的第一个词条（稀疏采样），不是全部词条。因为 Block 内剩余的词条（如 “上学了” 与 “上学” 在同一块）会通过FST 定位 Block → Block 内二分查找的方式找到。

请把本节理解为"数据结构层面的教学模型"，不是"生产架构的真实复现"。

3.1 词条排序

FST 构建的前提是词条必须按字典序排序后依次插入。对上述词条按字典序（UTF-8 字节序）排列：

UTF-8 编码（十六进制）：

• “上” =E4 B8 8A
• “海” =E6 B5 B7
• “学” =E5 AD A6

3.2 为每个词条分配输出值

假设每个词条的输出值（Output）是其对应的Term Dictionary Block在.tim文件中的偏移量：

再次强调：FST 的输出值指向的是 Term Dictionary 中的 Block 位置，不是直接指向 Posting List。
完整查询链路是：FST → 定位 Block 偏移 → 加载 .tim Block → 在 Block 中查找词条 → 获取 Posting List 偏移 → 加载 .doc/.pos

3.3 逐步构建 FST

步骤 1：插入 “上” → output=100

┌─────────────┐ │ Start (0) │ └──────┬──────┘ │ │ input='上' (E4 B8 8A) │ output=100 ▼ ┌─────────────┐ │ (1) ✓ │ ← ✓ 表示终态节点 └─────────────┘

此时 FST 只有一条路径：Start → ①，节点①是终态，输出累加为 100。

步骤 2：插入 “上海” → output=200

“上海” 与 “上” 共享前缀 “上”，需要在原有基础上扩展：

前缀共享 ┌──────────────┐ │ Start (0) │ └──────┬───────┘ │ │ input='上' │ output=100 ← "上" 的输出仍保留在此边上 ▼ ┌──────────────┐ │ (1) ✓ │ ← "上" 的终态（output=100，到此为止） └──────┬───────┘ │ │ input='海' (E6 B5 B7) │ output=100 ← 新增边的输出 = 200 - 100 = 100（增量） ▼ ┌──────────────┐ │ (2) ✓ │ ← "上海" 的终态 └──────────────┘

关键理解 — 输出值的增量编码：

FST 沿路径累加输出值。对于共享前缀的路径：

• 边(0)→(1)的 output = 100（“上” 的完整输出）
• 边(1)→(2)的 output = 100（增量：200 - 100 = 100）
• 到达节点 (2) 时，累加输出 = 100 + 100 =200（“上海” 的输出）

步骤 3：插入 “上学” → output=300

“上学” 同样共享前缀 “上”，从节点 (1) 分叉：

┌──────────────────────┐ │ Start (0) │ └──────────┬───────────┘ │ │ input='上' │ output=100 ▼ ┌───────────────┐ │ (1) ✓ │ ← "上" 的终态 └──────┬────────┘ │ ┌──────┴──────┐ │ │ │ │ input='学' (E5 AD A6) │ │ output=200 (增量: 300-100=200) │ ▼ │ ┌───────────────┐ │ │ (3) ✓ │ ← "上学" 的终态 │ └───────────────┘ │ │ input='海' │ output=100 (增量: 200-100=100) ▼ ┌──────────────┐ │ (2) ✓ │ ← "上海" 的终态 └──────────────┘

验证输出值：

• “上” → 路径到 (1)，输出 =100✓
• “上海” → 路径到 (2)，输出 = 100 + 100 =200✓
• “上学” → 路径到 (3)，输出 = 100 + 200 =300✓

步骤 4：插入 “海上” → output=400

“海上” 与前三个词条无公共前缀，需要从 Start 节点新增一条独立路径：

┌─────────────────────────────────────┐ │ Start (0) │ └──────┬──────────────────┬───────────┘ │ │ input='上' │ │ input='海' output=100 │ │ output=400 ▼ ▼ ┌───────────────┐ ┌───────────────┐ │ (1) ✓ │ │ (4) │ └──────┬────────┘ └──────┬────────┘ │ │ ┌──────┴──────┐ │ input='上' │ │ │ output=0 │ │ ▼ │ │ ┌───────────────┐ │ │ │ (5) ✓ │ ← "海上" 的终态 │ │ └───────────────┘ │ │ │ │ input='学' │ │ output=200 │ ▼ │ ┌───────────────┐ │ │ (3) ✓ │ ← "上学" 的终态 │ └───────────────┘ │ │ input='海' │ output=100 ▼ ┌──────────────┐ │ (2) ✓ │ ← "上海" 的终态 └──────────────┘

验证输出值：

• “上” → 100 ✓
• “上海” → 100 + 100 = 200 ✓
• “上学” → 100 + 200 = 300 ✓
• “海上” → 400 + 0 = 400 ✓

注意：边(4)→(5)的 output=0，因为 “海上” 的完整输出 400 已经全部编码在第一条边(0)→(4)上了。

3.4 完整 FST 结构总结

前缀压缩效果：

• “上”、“上海”、“上学” 共享了第一条边(0)→(1)，字符 “上” 只存储一次
• 节点 (1) 同时是终态（“上”）和中间节点（“上海”、“上学” 的前缀节点）

4. FST 查询过程

4.1 FST 内部的词条匹配

以查询“上学”为例：

步骤 1: 从 Start(0) 出发，匹配第一个字节序列 '上'(E4 B8 8A) → 找到边 (0)→(1)，output=100，累加输出=100 步骤 2: 从节点 (1) 出发，匹配 '学'(E5 AD A6) → 在节点(1)的所有出边中找到 input='学' 的边 → 找到边 (1)→(3)，output=200，累加输出=100+200=300 步骤 3: 到达节点 (3)，检查是否为终态 → (3) 标记为 ✓（终态）→ FST 匹配成功！ → 返回输出值 300（Term Dictionary Block 在 .tim 文件中的偏移量）

以查询“上学了”（不在 FST 中，但在 Block 内）为例：

步骤 1: 在 FST 中查找 "上学了" → FST 中没有精确匹配 "上学了" → 找到最后一个小于等于 "上学了" 的词条："上学" → 输出值 = 300（Block 偏移量） 步骤 2: 加载 .tim 中偏移量 300 处的 Block → Block 内包含词条：["上学", "上学了", "上学前", ... "上学难"] 步骤 3: 在 Block 内二分查找 "上学了" → 找到 → 返回其 Posting List 偏移

以查询“上人”（词条不存在）为例：

步骤 1: 在 FST 中查找 "上人" → FST 中没有精确匹配 → 找到 floor 词条 "上"，输出值 = 100（某个 Block 偏移） 步骤 2: 加载对应 Block → Block 内包含：["上", "上海", "上学", ... "上路"] 步骤 3: 在 Block 内二分查找 "上人" → 未找到 → 词条不存在

4.2 完整的查询链路

FST 匹配成功并不等于查询结束。FST 只完成了第一层定位，完整链路如下：

用户查询: "上学" ┌─ 第 1 层：Term Index（FST，内存中）────────────────────────┐ │ │ │ FST 匹配 "上学" → 成功，输出值 = 300 │ │ 输出值 300 = Term Dictionary 中目标 Block 的 .tim 偏移量 │ │ │ └────────────────────────────┬──────────────────────────────┘ │ 定位到 Block 偏移 ▼ ┌─ 第 2 层：Term Dictionary（.tim 文件，按需加载 Block）─────┐ │ │ │ 从 .tim 文件偏移量 300 处加载整个 Block（如 256 个词条） │ │ 在 Block 内对词条做二分查找 → 找到 "上学" │ │ 词条条目中记录了其 Posting List 在 .doc/.pos 的偏移量 │ │ │ └────────────────────────────┬──────────────────────────────┘ │ 获取 Posting List 偏移 ▼ ┌─ 第 3 层：Posting List（.doc / .pos 文件，按需加载）───────┐ │ │ │ 根据偏移量加载 DocID 列表、词频、位置信息 │ │ 返回匹配的文档集合 │ │ │ └───────────────────────────────────────────────────────────┘

关键点：

• FST 中存储的词条是稀疏采样（每个 Block 的第一个词条），不是所有词条
• FST 查询不是"精确匹配"，而是floor/ceiling 定位：找到不大于（或大于等于）目标词条的最大（或最小）Block 入口点
• FST 定位到 Block 后，还需在 Block 内二分查找做精确匹配
• 如果 FST 定位的 Block 内找不到目标词条，则词条不存在

5. Lucene FST 构建与查询 API

FST 的类结构已在 2.3 节 中详细说明，本节聚焦构建和查询过程。

5.1 构建过程 — Builder

// org.apache.lucene.util.fst.Builder// 词条必须按字典序依次 add()Builder<T>builder=newBuilder<>(FST.INPUT_TYPE.BYTE4,outputs);builder.add(Util.toIntsRef(newBytesRef("上"),scratch),output100);builder.add(Util.toIntsRef(newBytesRef("上海"),scratch),output200);builder.add(Util.toIntsRef(newBytesRef("上学"),scratch),output300);builder.add(Util.toIntsRef(newBytesRef("海上"),scratch),output400);FST<T>fst=builder.finish();

Builder 内部工作原理：

1. 每插入一个新词条，与上一个词条比较，找出最长公共前缀
2. 公共前缀部分复用已有路径
3. 非公共部分创建新的节点和边
4. 在添加新词条时，冻结（freeze）上一个词条中不可能再被共享的节点（因为词条有序，后续词条不会再有相同前缀到达这些节点）
5. 冻结时对节点做最小化（minimization）：如果两个节点的出边完全相同（相同的输入标签、输出值、目标节点），则合并为一个节点（实现后缀共享）

5.2 查询过程 — BytesRefFSTEnum / Util.get

// 快速查询：给定词条，获取输出值（Term Dictionary Block 偏移量）Toutput=Util.get(fst,newBytesRef("上学"));// output = 300 → 指向 .tim 文件中偏移量 300 处的 Block// 遍历查询BytesRefFSTEnum<T>fstEnum=newBytesRefFSTEnum<>(fst);IntsRefresult=fstEnum.seekCeil(newBytesRef("上"));// 返回 >= "上" 的第一个词条及其输出

6. FST 在 ES 倒排索引中的位置 — 三层架构详解

Lucene 倒排索引采用三层结构，FST 只是第一层（Term Index）：

┌─────────────────────────────────────────────────────────────┐ │ Segment (段) — Lucene 基本索引单元 │ │ │ │ ┌────────────────┐ ┌─────────────────┐ ┌──────────┐ │ │ │ Term Index │ │ Term Dictionary│ │ Posting │ │ │ │ (.tip 文件) │────▶│ (.tim 文件) │───▶│ List │ │ │ │ │ │ │ │(.doc/.pos)│ │ │ │ 结构: FST │ │ 结构: Block │ │ │ │ │ │ 内容: 每个 │ │ Tree 分块存储 │ │ 结构: │ │ │ │ Block 的入口 │ │ 内容: 全部词条 │ │ 差分编码 │ │ │ 词条（稀疏） │ │ + Posting List │ │ + 压缩 │ │ │ 输出: .tim │ │ 偏移量 │ │ │ │ │ │ Block 偏移量 │ │ │ │ │ │ │ │ │ │ 按 Block 加载 │ │ 按需加载 │ │ │ │ 全部内存驻留 │ │ (Block 默认 │ │ │ │ │ │ │ │ 256 词条) │ │ │ │ │ └────────────────┘ └─────────────────┘ └──────────┘ │ │ │ │ 内存中，很小 磁盘上，很大 │ │ ~几十 MB ~数百 MB - 数 GB │ └─────────────────────────────────────────────────────────────┘

索引文件层级：

6.1 为什么需要三层？— 空间与速度的平衡

假设一个 Segment 有1 亿个不同词条：

Lucene 的设计精髓：

• FST 只存每个 Block 第一个词条（稀疏采样），如每 256 个词条取 1 个 → FST 只需存 1亿/256 ≈ 39万 个词条
• 39万个词条的 FST 只有几十 MB，可完全放入内存
• 查询时：FST 内存定位 → 1 次磁盘 IO 加载 Block → Block 内二分查找（256 个词条，最多 8 次比较）

FST 稀疏采样查询示例：

假设 FST 中只存了以下 Block 入口词条（每 4 个为一组，实际生产环境是 256）：

FST 中存储的词条（Block 入口点）： "上" → 偏移 100（Block #0 的起始） "上海" → 偏移 200（Block #1 的起始） "上学" → 偏移 300（Block #2 的起始） Term Dictionary（.tim 文件，分 3 个 Block）： Block #0（偏移 100）: [上, 上午, 上面, 上学下] Block #1（偏移 200）: [上海, 上海滩, 上海话, 上海站] Block #2（偏移 300）: [上学, 上学了, 上学去, 上学路]

现在查询不同词条时：

最后一行 “上天”：FST floor 命中了 “上”，但 Block #0 内并没有 “上天”，最终词条不存在。这说明FST 只能缩小范围，不能判定词条一定存在，精确判定在 Block 内完成。

7. FST 空间压缩效果分析

回到我们的例子，对比传统存储与 FST 存储：

传统哈希表 / 排序数组

FST 存储

对于百万级词条的实际场景：

• 排序数组 / 哈希表：数百 MB ~ 数 GB
• FST：压缩到数十 MB，可完全放入内存

8. Lucene 索引构建顺序与分块规律

8.1 构建顺序：先 Term Dictionary，后 Term Index（FST）

Lucene 构建索引时的写入顺序是：

第 1 步：收集阶段（内存中） └─ 遍历文档 → 提取词条 → 构建 Posting List（DocID、Freq、Pos 等） 第 2 步：Flush Posting List（.doc / .pos） └─ 将内存中的 Posting List 按词条顺序写入磁盘 第 3 步：Flush Term Dictionary（.tim） ← 先写 └─ 按字典序遍历词条，分组写入 Block └─ 每确定一个 Block，记录该 Block 第一个词条及文件偏移量 第 4 步：Flush Term Index（.tip / FST） ← 后写 └─ 用第 3 步记录的 Block 入口词条构建 FST └─ FST 的输出值 = 对应 Block 在 .tim 中的偏移量 └─ 写入 .tip 文件

为什么 FST 必须最后写？

FST 的输出值是每个 Block 在.tim文件中的磁盘偏移量。只有等所有 Block 都写完了，才知道每个 Block 的精确偏移位置，才能构建 FST。

// 伪代码示意voidflush(){// 1. 先 flush Posting ListpostingsWriter.flush();// 2. 构建并写入 Term Dictionary（.tim）for(Blockblock:blocks){longblockOffset=out.getFilePointer();// 记录当前文件偏移writeBlock(block);// 写入 Block// 3. 收集 Block 入口词条，用于后续构建 FSTfstBuilder.add(block.firstTerm,blockOffset);}// 4. 最后构建并写入 FST（.tip）FSTfst=fstBuilder.finish();writeFST(fst);}

8.2 词条词典的分块规律

Lucene 的分块不是简单的前 N 个词条一组，而是基于前缀树（Prefix Trie）的自底向上合并：

分块流程

Step 1: 构建前缀树（Trie） 所有词条按字典序插入前缀树 示例词条：[上, 上海, 上海滩, 上海话, 上学, 上学了, 上学去, 海上] (root) / \ 上 海 / | | 海 学 上 / | | 滩 了 (end) / 话 Step 2: 自底向上合并节点 每个叶节点是一个"候选 Block" 如果候选 Block 词条数 < MIN_BLOCK_SIZE → 与兄弟合并 如果候选 Block 词条数 > MAX_BLOCK_SIZE → 拆分为多个子 Block Step 3: 确定最终 Block 每个 Block 内所有词条共享一个"公共前缀" Block 内只存后缀差异部分（前缀压缩）

具体规则

关键设计思想

传统做法：前 256 个词条为一组（固定大小） Lucene 做法：按前缀树合并（前缀共享最大化压缩） 为什么按前缀分块更好？ - "上海" 和 "上海滩" 共享前缀 "上海" - 如果它们被分到不同 Block，前缀 "上海" 要存两次 - 如果分到同一块，前缀只存一次，节省大量空间

代码层面

// org.apache.lucene.codecs.blocktree.BlockTreeTermsWriterpublicclassBlockTreeTermsWriter{// Block 大小阈值publicstaticfinalintDEFAULT_MIN_BLOCK_SIZE=25;publicstaticfinalintDEFAULT_MAX_BLOCK_SIZE=48;voidflush(){// 1. 先 flush Posting ListpostingsWriter.flush();// 2. 构建前缀树并分块PendingBlockroot=buildBlockTree();// 3. 写入 .tim（Term Dictionary）for(Blockblock:root.blocks){longblockOffset=out.getFilePointer();writeBlock(block);fstBuilder.add(block.firstTerm,blockOffset);}// 4. 构建并写入 .tip（FST）FSTfst=fstBuilder.finish();writeFST(fst);}}

8.3 总结

9. FST 的优缺点总结

优点

缺点

这些缺点在搜索引擎场景中完全可以接受：

• 索引写入是批量追加（Segment 机制），不是单条随机写
• 查询是高频操作，FST 的 O(len(term)) 查询性能极佳
• 空间压缩带来的内存收益远超构建成本

10. 总结

Lucene 倒排索引采用三层架构，FST 是第一层（Term Index）的核心数据结构：

FST (Term Index) → Block Tree (Term Dictionary) → Posting List .tip 内存 .tim 磁盘按需加载 .doc/.pos 磁盘 稀疏索引 全量词条 DocID 列表

FST 的关键特性：

1. 它是 Term Dictionary 的"索引的索引"，只存每个 Block 的入口词条（稀疏采样），不是所有词条
2. 它是有输出的自动机，匹配词条的同时输出指向.timBlock 的磁盘偏移量（不是直接指向 Posting List）
3. 增量编码使得共享前缀路径上的输出值可以高效累加
4. 最小化（Minimization）进一步合并相同后缀节点，实现极致压缩
5. 几十 MB 的 FST 可索引数亿词条的 Term Dictionary，完美平衡内存与磁盘 IO

理解 FST 以及它与 Term Dictionary 的分层关系，是深入理解 Elasticsearch 倒排索引底层原理的关键。

参考资料：

• Lucene 源码：org.apache.lucene.util.fst.FST、org.apache.lucene.util.fst.Builder
• Lucene FST 官方 Wiki：https://lucene.apache.org/core/9_0_0/core/org/apache/lucene/util/fst/package-summary.html
• 《Elasticsearch 权威指南》— 倒排索引章节