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

Elasticsearch 倒排索引中词条索引原理分析 — 基于 Lucene FST1. 概述Elasticsearch 的倒排索引Inverted Index由三层结构组成Term Index词条索引 → Term Dictionary词条词典 → Posting List倒排表 .tip 文件 .tim 文件 .doc / .pos 文件 FST 结构 Block Tree 分块存储 DocID、词频、位置 全部加载到内存 按需从磁盘加载 按需从磁盘加载三层职责严格分离不要混淆层级存储内容底层结构加载方式Term Index每个 Block 的入口词条稀疏采样指向 Term Dictionary 中对应 Block 的偏移量FSTFinite State Transducer全部驻留内存Term Dictionary全部词条按字典序排列按固定大小分 Block排序 Block 前缀压缩按需从磁盘加载 BlockPosting List每个词条对应的 DocID 列表、词频、位置等差分编码 压缩按需从磁盘加载本文聚焦的是第一层 — Term Index 的底层数据结构 FST由org.apache.lucene.util.fst.FST类实现。FST vs Term Dictionary 的本质区别FSTTerm Index只存每个 Block 的第一个词条是词典的索引量级很小Term Dictionary 存所有词条数据量大按 Block 分块存储在磁盘上查询时先用 FST 定位到目标 Block 的磁盘偏移 → 再从 .tim 文件加载该 Block → 在 Block 内二分查找目标词条 → 最后获取 Posting ListFST 本质上是一个带输出的有限状态自动机FSA它不仅能够判断某个输入字符串是否被接受即是否存在还能在匹配的同时输出与该词条关联的值如指向 Term Dictionary Block 的磁盘偏移量。2. FST 核心概念2.1 FSA vs FST特性FSA有限状态自动机FST有限状态转换器输入字符串字符串字节序列输出仅判断是否接受True/False输出一个关联值Output用途判断词条是否存在查询词条并返回关联数据关系FSA 是 FST 的特例输出为空时 FST 退化为 FSA。2.2 FST 结构要素 — 理论与代码映射FST 的理论定义FST (States, Transitions, StartState, FinalStates)每个要素的含义及其在 Lucene 源码中的对应理论要素含义Lucene 源码中的体现States状态集合自动机中的所有节点。每个状态代表已匹配了某个前缀不是独立对象。每个状态是byte[]数组中的一个偏移位置long nodeOffset。nodeCount记录总节点数Transitions转换/边状态之间的有向边每条边带有输入标签和输出值FST.ArcT类。字段label(输入字符)、output(输出值)、target(目标节点偏移)、nextArc(同节点的下一条边)StartState起始状态所有匹配的起点输入为空时的状态FST.startNodelong类型指向byte[]中起始节点的偏移位置FinalStates终态集合匹配成功的终点。到达终态说明输入串是一个合法词条没有独立集合。节点在序列化时通过flag 位标记是否为终态BIT_FINAL_ARC查询时通过Arc.isFinal()判断关键设计理解Lucene FST 中没有独立的 State 对象所有节点和边被紧凑地序列化到一个byte[]字节数组中一个状态 byte[]中的一个偏移量long整数一个边 从该偏移量开始的一段字节编码通过FST.readFirstArc()/FST.readNextArc()解码这样做的好处是零对象创建、GC 友好、可直接 mmap 磁盘文件2.3 核心代码结构// org.apache.lucene.util.fst.FSTpublicfinalclassFSTTextendsAccountable{// 输入类型BYTE1单字节ASCII或 BYTE4四字节Unicode 码点privatefinalINPUT_TYPEinputType;// StartState // 起始节点在 bytes 数组中的偏移位置privatefinallongstartNode;// States 的存储载体 // 所有节点和边紧凑序列化在此字节数组中// 没有独立的 State 对象状态 此数组的一个偏移量privatefinalFSTBytesbytes;// (新版 Lucene 使用 FSTBytes 封装)// Transitions 的输出值类型 // 决定 output 的数据类型如 POS_INTS_OFFSETS 表示正整数privatefinalOutputsToutputs;// States / Transitions 的计数 privateintnodeCount;// 节点总数States 的数量privateintarcCount;// 边总数Transitions 的数量}// org.apache.lucene.util.fst.FST.Arc — 代表一条 Transition边publicstaticfinalclassArcT{// 输入标签这条边匹配的字符字节值publicintlabel;// 输出值沿这条边的输出查询时沿路径累加publicToutput;// 目标节点这条边指向的状态节点在 bytes 中的偏移publiclongtarget;// FinalState 判断 // 如果 target 指向的节点是终态则 flags 中包含 BIT_FINAL_ARCpublicbyteflags;publicbooleanisFinal(){return(flagsBIT_FINAL_ARC)!0;}// 同节点的下一条边链式遍历同一状态的所有出边publiclongnextArc;}2.4 FST 的核心优势前缀共享具有相同前缀的词条共享路径节点大幅压缩空间后缀共享具有相同后缀的词条在构建时可合并尾节点minimization空间压缩FST 只存 Block 入口词条稀疏采样将 Term Index 压缩到 MB 级可完全放入内存查询高效时间复杂度为 O(len(term))与词条数量无关3. 举例词条 “上海”、“上学”、“海上”、“上” 的 FST 构建⚠️重要说明本节示例 vs 生产环境的区别本节3.1 ~ 3.4将4 个词条全部放入 FST是为了讲解FST 数据结构的内部机制前缀共享、增量编码。但在 Lucene生产环境中见第 6 节FSTTerm Index只存储每个 Block 的第一个词条稀疏采样不是全部词条。因为 Block 内剩余的词条如 “上学了” 与 “上学” 在同一块会通过FST 定位 Block → Block 内二分查找的方式找到。请把本节理解为数据结构层面的教学模型不是生产架构的真实复现。3.1 词条排序FST 构建的前提是词条必须按字典序排序后依次插入。对上述词条按字典序UTF-8 字节序排列序号词条Unicode 编码1上U4E0A2上海U4E0A U6D773上学U4E0A U5B664海上U6D77 U4E0AUTF-8 编码十六进制“上” E4 B8 8A“海” E6 B5 B7“学” E5 AD A63.2 为每个词条分配输出值假设每个词条的输出值Output是其对应的Term Dictionary Block在.tim文件中的偏移量再次强调FST 的输出值指向的是 Term Dictionary 中的 Block 位置不是直接指向 Posting List。完整查询链路是FST → 定位 Block 偏移 → 加载 .tim Block → 在 Block 中查找词条 → 获取 Posting List 偏移 → 加载 .doc/.pos词条输出值示例上100上海200上学300海上4003.3 逐步构建 FST步骤 1插入 “上” → output100┌─────────────┐ │ Start (0) │ └──────┬──────┘ │ │ input上 (E4 B8 8A) │ output100 ▼ ┌─────────────┐ │ (1) ✓ │ ← ✓ 表示终态节点 └─────────────┘此时 FST 只有一条路径Start → ①节点①是终态输出累加为 100。步骤 2插入 “上海” → output200“上海” 与 “上” 共享前缀 “上”需要在原有基础上扩展前缀共享 ┌──────────────┐ │ Start (0) │ └──────┬───────┘ │ │ input上 │ output100 ← 上 的输出仍保留在此边上 ▼ ┌──────────────┐ │ (1) ✓ │ ← 上 的终态output100到此为止 └──────┬───────┘ │ │ input海 (E6 B5 B7) │ output100 ← 新增边的输出 200 - 100 100增量 ▼ ┌──────────────┐ │ (2) ✓ │ ← 上海 的终态 └──────────────┘关键理解 — 输出值的增量编码FST 沿路径累加输出值。对于共享前缀的路径边(0)→(1)的 output 100“上” 的完整输出边(1)→(2)的 output 100增量200 - 100 100到达节点 (2) 时累加输出 100 100 200“上海” 的输出步骤 3插入 “上学” → output300“上学” 同样共享前缀 “上”从节点 (1) 分叉┌──────────────────────┐ │ Start (0) │ └──────────┬───────────┘ │ │ input上 │ output100 ▼ ┌───────────────┐ │ (1) ✓ │ ← 上 的终态 └──────┬────────┘ │ ┌──────┴──────┐ │ │ │ │ input学 (E5 AD A6) │ │ output200 (增量: 300-100200) │ ▼ │ ┌───────────────┐ │ │ (3) ✓ │ ← 上学 的终态 │ └───────────────┘ │ │ input海 │ output100 (增量: 200-100100) ▼ ┌──────────────┐ │ (2) ✓ │ ← 上海 的终态 └──────────────┘验证输出值“上” → 路径到 (1)输出 100✓“上海” → 路径到 (2)输出 100 100 200✓“上学” → 路径到 (3)输出 100 200 300✓步骤 4插入 “海上” → output400“海上” 与前三个词条无公共前缀需要从 Start 节点新增一条独立路径┌─────────────────────────────────────┐ │ Start (0) │ └──────┬──────────────────┬───────────┘ │ │ input上 │ │ input海 output100 │ │ output400 ▼ ▼ ┌───────────────┐ ┌───────────────┐ │ (1) ✓ │ │ (4) │ └──────┬────────┘ └──────┬────────┘ │ │ ┌──────┴──────┐ │ input上 │ │ │ output0 │ │ ▼ │ │ ┌───────────────┐ │ │ │ (5) ✓ │ ← 海上 的终态 │ │ └───────────────┘ │ │ │ │ input学 │ │ output200 │ ▼ │ ┌───────────────┐ │ │ (3) ✓ │ ← 上学 的终态 │ └───────────────┘ │ │ input海 │ output100 ▼ ┌──────────────┐ │ (2) ✓ │ ← 上海 的终态 └──────────────┘验证输出值“上” → 100 ✓“上海” → 100 100 200 ✓“上学” → 100 200 300 ✓“海上” → 400 0 400 ✓注意边(4)→(5)的 output0因为 “海上” 的完整输出 400 已经全部编码在第一条边(0)→(4)上了。3.4 完整 FST 结构总结路径词条边序列累加输出(0)→(1)上上/100100(0)→(1)→(2)上海上/100 → 海/100200(0)→(1)→(3)上学上/100 → 学/200300(0)→(4)→(5)海上海/400 → 上/0400前缀压缩效果“上”、“上海”、“上学” 共享了第一条边(0)→(1)字符 “上” 只存储一次节点 (1) 同时是终态“上”和中间节点“上海”、“上学” 的前缀节点4. FST 查询过程4.1 FST 内部的词条匹配以查询“上学”为例步骤 1: 从 Start(0) 出发匹配第一个字节序列 上(E4 B8 8A) → 找到边 (0)→(1)output100累加输出100 步骤 2: 从节点 (1) 出发匹配 学(E5 AD A6) → 在节点(1)的所有出边中找到 input学 的边 → 找到边 (1)→(3)output200累加输出100200300 步骤 3: 到达节点 (3)检查是否为终态 → (3) 标记为 ✓终态→ FST 匹配成功 → 返回输出值 300Term Dictionary Block 在 .tim 文件中的偏移量以查询“上学了”不在 FST 中但在 Block 内为例步骤 1: 在 FST 中查找 上学了 → FST 中没有精确匹配 上学了 → 找到最后一个小于等于 上学了 的词条上学 → 输出值 300Block 偏移量 步骤 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 IndexFST内存中────────────────────────┐ │ │ │ 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 构建与查询 APIFST 的类结构已在 2.3 节 中详细说明本节聚焦构建和查询过程。5.1 构建过程 — Builder// org.apache.lucene.util.fst.Builder// 词条必须按字典序依次 add()BuilderTbuildernewBuilder(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);FSTTfstbuilder.finish();Builder 内部工作原理每插入一个新词条与上一个词条比较找出最长公共前缀公共前缀部分复用已有路径非公共部分创建新的节点和边在添加新词条时冻结freeze上一个词条中不可能再被共享的节点因为词条有序后续词条不会再有相同前缀到达这些节点冻结时对节点做最小化minimization如果两个节点的出边完全相同相同的输入标签、输出值、目标节点则合并为一个节点实现后缀共享5.2 查询过程 — BytesRefFSTEnum / Util.get// 快速查询给定词条获取输出值Term Dictionary Block 偏移量ToutputUtil.get(fst,newBytesRef(上学));// output 300 → 指向 .tim 文件中偏移量 300 处的 Block// 遍历查询BytesRefFSTEnumTfstEnumnewBytesRefFSTEnum(fst);IntsRefresultfstEnum.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 │ └─────────────────────────────────────────────────────────────┘索引文件层级文件后缀层级数据结构存储内容加载方式.tipTerm IndexFST每个 Block 的入口词条 →.timBlock 偏移量全部内存驻留.timTerm Dictionary排序 Block 前缀压缩全部词条 每条词条的 Posting List 偏移量按需加载 Block.docPosting List差分编码 (FOR)DocID 列表、词频按需加载.posPosting List差分编码 压缩词条在文档中的位置按需加载6.1 为什么需要三层— 空间与速度的平衡假设一个 Segment 有1 亿个不同词条方案内存占用查询速度全部词条放内存HashMap~数 GBJVM 压力大O(1) 最快全部词条放磁盘B Tree内存占用小O(log N) 但每次可能触发磁盘 IOFST (Term Index) Block (Term Dict)✅~几十 MBFST 内存定位 1 次磁盘 IO 加载 BlockLucene 的设计精髓FST 只存每个 Block 第一个词条稀疏采样如每 256 个词条取 1 个 → FST 只需存 1亿/256 ≈ 39万 个词条39万个词条的 FST 只有几十 MB可完全放入内存查询时FST 内存定位 → 1 次磁盘 IO 加载 Block → Block 内二分查找256 个词条最多 8 次比较FST 稀疏采样查询示例假设 FST 中只存了以下 Block 入口词条每 4 个为一组实际生产环境是 256FST 中存储的词条Block 入口点 上 → 偏移 100Block #0 的起始 上海 → 偏移 200Block #1 的起始 上学 → 偏移 300Block #2 的起始 Term Dictionary.tim 文件分 3 个 Block Block #0偏移 100: [上, 上午, 上面, 上学下] Block #1偏移 200: [上海, 上海滩, 上海话, 上海站] Block #2偏移 300: [上学, 上学了, 上学去, 上学路]现在查询不同词条时查询词条FST 中查找结果定位到的 BlockBlock 内查找“上”精确命中Block #0找到 “上”“上面”floor 命中 “上”Block #0找到 “上面”“上海滩”floor 命中 “上海”Block #1找到 “上海滩”“上学了”floor 命中 “上学”Block #2找到 “上学了”“上天”floor 命中 “上”Block #0找不到 → 词条不存在最后一行 “上天”FST floor 命中了 “上”但 Block #0 内并没有 “上天”最终词条不存在。这说明FST 只能缩小范围不能判定词条一定存在精确判定在 Block 内完成。7. FST 空间压缩效果分析回到我们的例子对比传统存储与 FST 存储传统哈希表 / 排序数组词条存储内容上“上” (3B) 指针 (8B) 输出 (4B) 15B上海“上海” (6B) 指针 (8B) 输出 (4B) 18B上学“上学” (6B) 指针 (8B) 输出 (4B) 18B海上“海上” (6B) 指针 (8B) 输出 (4B) 18B合计69B不含哈希表额外开销FST 存储组件大小估算节点 0Start2 条出边节点 1上终态2 条出边节点 2上海终态0 条出边节点 3上学终态0 条出边节点 4中间节点1 条出边节点 5海上终态0 条出边边总数6 条字符存储上×1 海×1 学×1 海×1 上×1 5个字符×3B 15B关键Lucene FST 序列化后通过紧凑编码变长整数、位压缩实际约30-40B对于百万级词条的实际场景排序数组 / 哈希表数百 MB ~ 数 GBFST压缩到数十 MB可完全放入内存8. Lucene 索引构建顺序与分块规律8.1 构建顺序先 Term Dictionary后 Term IndexFSTLucene 构建索引时的写入顺序是第 1 步收集阶段内存中 └─ 遍历文档 → 提取词条 → 构建 Posting ListDocID、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.timfor(Blockblock:blocks){longblockOffsetout.getFilePointer();// 记录当前文件偏移writeBlock(block);// 写入 Block// 3. 收集 Block 入口词条用于后续构建 FSTfstBuilder.add(block.firstTerm,blockOffset);}// 4. 最后构建并写入 FST.tipFSTfstfstBuilder.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 内只存后缀差异部分前缀压缩具体规则规则默认值说明MIN_BLOCK_SIZE25少于 25 个词条就和兄弟合并MAX_BLOCK_SIZE48超过 48 个词条就拆分前缀选择最长公共前缀Block 内词条共享最长前缀减少冗余后缀存储差异部分Block 内只存去掉公共前缀后的后缀关键设计思想传统做法前 256 个词条为一组固定大小 Lucene 做法按前缀树合并前缀共享最大化压缩 为什么按前缀分块更好 - 上海 和 上海滩 共享前缀 上海 - 如果它们被分到不同 Block前缀 上海 要存两次 - 如果分到同一块前缀只存一次节省大量空间代码层面// org.apache.lucene.codecs.blocktree.BlockTreeTermsWriterpublicclassBlockTreeTermsWriter{// Block 大小阈值publicstaticfinalintDEFAULT_MIN_BLOCK_SIZE25;publicstaticfinalintDEFAULT_MAX_BLOCK_SIZE48;voidflush(){// 1. 先 flush Posting ListpostingsWriter.flush();// 2. 构建前缀树并分块PendingBlockrootbuildBlockTree();// 3. 写入 .timTerm Dictionaryfor(Blockblock:root.blocks){longblockOffsetout.getFilePointer();writeBlock(block);fstBuilder.add(block.firstTerm,blockOffset);}// 4. 构建并写入 .tipFSTFSTfstfstBuilder.finish();writeFST(fst);}}8.3 总结问题答案先写哪个先.timTerm Dictionary后.tipFST。FST 依赖 Block 的磁盘偏移量必须等 Block 都写完才能构建分块规律基于前缀树自底向上合并不是固定大小。词条共享相同前缀的尽量分到同一块Block 大小在 25~48 之间动态调整为什么这样设计前缀共享最大化压缩比同时控制 Block 大小在合理范围内存加载 二分查找效率9. FST 的优缺点总结优点优点说明空间极致压缩前缀共享 后缀合并 增量编码查询高效O(len(term))与词典大小无关内存友好可直接操作磁盘映射字节无需全量反序列化支持范围查询可枚举词条、前缀匹配、seekCeil/seekFloor关联输出一次查询同时获得 Term Dictionary Block 偏移量缺点缺点说明构建成本高必须有序插入构建时需要大量节点比较和冻结不可变构建完成后不可修改Lucene 每次写入 Segment 时重建随机写入不支持无法像哈希表一样 O(1) 插入这些缺点在搜索引擎场景中完全可以接受索引写入是批量追加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 的关键特性它是 Term Dictionary 的索引的索引只存每个 Block 的入口词条稀疏采样不是所有词条它是有输出的自动机匹配词条的同时输出指向.timBlock 的磁盘偏移量不是直接指向 Posting List增量编码使得共享前缀路径上的输出值可以高效累加最小化Minimization进一步合并相同后缀节点实现极致压缩几十 MB 的 FST 可索引数亿词条的 Term Dictionary完美平衡内存与磁盘 IO理解 FST 以及它与 Term Dictionary 的分层关系是深入理解 Elasticsearch 倒排索引底层原理的关键。参考资料Lucene 源码org.apache.lucene.util.fst.FST、org.apache.lucene.util.fst.BuilderLucene FST 官方 Wikihttps://lucene.apache.org/core/9_0_0/core/org/apache/lucene/util/fst/package-summary.html《Elasticsearch 权威指南》— 倒排索引章节