TL;DR

场景：想把 ES「为什么快/为什么占内存/为什么写入要 merge」讲清楚，必须下沉到 Lucene 的倒排索引与文件结构结论：查询链路本质是 Term 查找（tim/tip + FST）→ postings 读取（doc 等）→ postings 合并（SkipList/跳跃）产出：一套从概念到文件后缀、到数据结构选择、到查询执行的可复用讲解框架

版本矩阵

Elasticsearch 数据结构

倒排索引

概念概述

倒排索引是全文检索的根基，理解了倒排索引之后才能算是入门了全文检索的领域，倒排索引的概念很简单，也很好理解。

倒排索引（Inverted Index）是信息检索系统中常用的数据结构，它由两个核心部分组成：

1. 索引表（Terms Dictionary）：

2. 由文档集合中所有独立的关键词（Term）组成的有序列表

3. 每个 Term 通常是经过分词和标准化处理后的结果（如转为小写、去除停用词等）

4. 在实际实现中，索引表常采用 B 树或哈希表等数据结构来加速查找

5. 示例：对于文档"the quick brown fox"，处理后可能得到["quick", "brown", "fox"]三个 Term

6. 倒排表（Posting List）：

7. 记录每个 Term 在哪些文档中出现的信息集合

8. 每个 Posting 通常包含：

9. 文档 ID（DocID）

10. 词频（Term Frequency）

11. 位置信息（Position，用于短语查询）

12. 示例：Term"fox"的 Posting List 可能是[(doc1, 2, [5,12]), (doc3, 1, [7])]，表示在 doc1 中出现 2 次（位置 5 和 12），在 doc3 中出现 1 次（位置 7）

在实际应用中（如 Elasticsearch、Lucene 等搜索引擎）：

• 索引表通常存储在内存中以实现快速查找

• 倒排表采用压缩存储技术（如差值编码、位图等）来减少存储空间

• 还会维护额外的统计信息（如 DF-文档频率）用于查询优化

如果存储一个倒排索引数据？选择哪种数据结构？

全文搜索引擎通常是需要存储大量的文本，不仅仅是 Postings 可能会是非常巨大，同样 Dictionary 的大小极可能也是非常庞大，真正的搜索引擎的倒排索引实现都极其复杂，因为它直接影响了搜索性能和功能。

Lucene 作为一款高性能的全文检索引擎库，其实现采用了多项先进技术来保证索引的高效性和可靠性。以下是其核心特性的详细说明：

1. 索引持久化机制：

• 采用分段(segment)存储策略，每个 segment 都是一个独立的倒排索引

• 支持将索引数据序列化为二进制格式存储在磁盘上

• 使用特殊的文件格式(如.fdt, .fdx 等)组织索引数据

• 支持索引压缩以减少存储空间占用

2. 高性能写入设计：

• 采用写入缓冲机制，先在内存中构建索引

• 定期将内存中的索引 flush 到磁盘形成新的 segment

• 支持近实时的 NRT(Near Real-Time)搜索

• 通过合并(merge)策略优化 segment 数量

3. 核心数据结构与算法：

• 使用 FST(Finite State Transducer)实现高效词典查找

• 采用跳表(SkipList)加速倒排链的遍历

• 实现基于 BM25 的评分算法

• 支持多种查询优化技术，如查询重写和缓存

4. 实际应用场景：

• 电商平台的商品搜索(如 Amazon)

• 企业文档管理系统

• 日志分析系统(如 ELK Stack)

• 社交媒体的内容检索

Lucene 通过这种精心设计的架构，在保证数据持久化的同时，实现了接近内存级别的搜索性能，使其成为众多商业搜索系统的基础引擎。

Lucene 索引文件分析

Lucene 是一个基于 Java 的开源全文检索库，由 Doug Cutting 于 1999 年创建。Lucene 的核心功能是为应用程序提供高效的文本索引和搜索能力，它可以帮助开发者构建快速、可扩展的全文搜索功能。Lucene 本身是一个低级库，并不提供图形界面或高级应用功能，它更多是作为一个底层工具被集成到其他系统或框架中。

• 索引（Index）： 索引是 Lucene 的核心组件之一，它是为了加速搜索过程而创建的数据结构。Lucene 会将文档中的文本分解为称为 "倒排索引"（inverted index）的形式。倒排索引类似于书的索引页，它列出了每个关键字在文档中的位置。这样，当用户搜索特定的词或短语时，Lucene 可以快速查找到包含该词的文档。

• 文档（Document）： 在 Lucene 中，文档是搜索和索引的基本单元。每个文档由若干字段（Field）组成，字段可以包含不同类型的数据，比如标题、内容、日期等。文档在 Lucene 中通常与数据库中的一条记录相对应。

• 字段（Field）： 字段是文档的组成部分，每个字段可以存储不同类型的数据，比如字符串、数字、日期等。字段可以指定是否被索引，是否被存储，以及是否可以被搜索等。

• 分词器（Analyzer）： 分词器负责将输入的文本分解为词汇单元（Token），这些词汇单元是 Lucene 用来索引和搜索的基础。例如，对于中文文本，分词器需要将连续的字符切分为有意义的词汇；对于英文文本，它会移除标点符号、转换大小写等。不同的语言和需求可能需要不同的分词器。

• 查询（Query）： Lucene 提供了多种类型的查询（Query），允许用户构建复杂的搜索逻辑，比如布尔查询（Boolean Query）、短语查询（Phrase Query）、范围查询（Range Query）等。查询的作用是通过匹配倒排索引来查找符合条件的文档。

• 评分（Scoring）： Lucene 对搜索结果进行评分，根据文档与查询的匹配程度返回一个相关性得分（Relevance Score）。默认情况下，Lucene 使用 TF-IDF（词频-逆文档频率）算法来计算得分，确保更相关的文档排在搜索结果的前面。

• 索引器（Indexer）： 索引器负责将文档中的数据转化为倒排索引。Lucene 的索引过程包括将文档分解为词汇单元，过滤掉不必要的词（如停用词），然后将有意义的词汇存入倒排索引中。索引器还负责定期优化索引以提高搜索效率。

• 存储与合并（Storage and Merging）： Lucene 的索引存储是分段式的，每次索引操作会创建新的段（segment）。Lucene 会定期合并这些段以减少碎片、提高性能。段是不可变的，这样的设计使得 Lucene 能够高效地进行并发搜索和索引操作。

Lucene 将索引文件拆分为了多个文件，这里仅讨论倒排索引的部分：

• tip：Lucene 把用于存储 Terms 的索引文件叫 Terms Index，它的后缀是：tip

• doc：把 Postings 信息分别存储在 doc，分别记录 Postings 的 DocId 信息和 Term 词频信息

• tim：Terms Dictionary 的文件后缀称为 tim，它是 Term 与 Positings 的关系纽带，存储了 Term 和其对应的 Postings 文件指针

• Term Dictionary：把 Term 按字典排序，然后用二分法查找 Term（存在磁盘）在 Lucene，Terms Dictionary 被存储在 tim 文件上，当一个 Segment 的文档数量越来越多的同时 Dictionary 的词汇也会越来越多，那查询效率必然也会越来越慢。如果有一个很好的结构也为 Dictionary 构建一个索引，将 Dictionary 的索引进一步压缩，这就是后来的 Terms Index（.tip）。

• TermIndex：是 Term Dictionary 的索引，存 Term 的前缀，和与该前缀对应的 Term Dictionary 中的第一个 Term 的 Block 的位置，找到这个第一个 Term 后会再往后顺序查找，直到找到目标 Term（存在内存）。

小节一下：

• 通过 Terms Index（tip）可以快速的在 Terms Dictionary(tim)中找到你想要的 Term，以及它对应的 Postings 文件指针（指向 doc）

• Terms Index 实际上一个或者多个 FST 组成的，Segment 上每个字段都有自己的一个 FST（FST Index）记录在 tip 上（FST 类似一种 TRIE 树）

Trie

Trie 被称作字典树、前缀树（Prefix Tree）、单词查找树：Trie 搜索字符串的效率主要跟字符串的长度有关（O(len(单词长度))）使用 Trie 存储： cat->1，dog->2，doggy->3，does->4，cast->5，add->6，这六个单词时，如下图：

Trie（字典树）的时间复杂度为 O(len(key))，其中 len(key)表示查询键的长度。这种数据结构通过共享键的前缀来优化存储空间，但无法共享后缀部分。

FST（Finite State Transducer，有限状态转换器）是一种更高级的数据结构，它不仅能够共享键的前缀，还能共享后缀。FST 具有以下优势：

1. 功能更全面：除了能判断查找的 Key 是否存在外，还能给出相应的输出(output)

2. 双重优化：在时间复杂度和空间复杂度上都做了最大程度的优化

3. 内存效率：优化的数据结构使得 Lucene 能够将整个 Term Index 完全加载到内存中

在实际应用中，FST 的工作流程如下：

1. 快速定位：通过共享前后缀的特性快速定位到目标 Term

2. 输出获取：在定位到 Term 的同时获取对应的 output（即 posting 倒排列表）

3. 性能优势：相比传统 Trie，FST 能显著减少内存占用并提高查询效率

典型应用场景：

• 搜索引擎索引构建（如 Lucene）

• 大规模词典存储

• 需要快速前缀/后缀查询的系统

例如，在 Lucene 中，FST 可以将数十万个 Term 及其对应的 posting 列表高效地存储在内存中，实现毫秒级的查询响应。

SkipList 应用

概念概述

假设某个索引字段中有 sex、address 字段，检索条件为：sex='female' and address='北京'

• 给定查询过滤条件 sex='female'的过程就是先从 Term index 找到 female 在 Term Dictionary 的大概位置

• 再从 Term Dictionary 里精确的找到 Female 这个 Term，然后得到一个 posting list 或者一个指向 posting list 位置的指针

• 查询 address='北京' 的过程类似的，得到一个 posting list 或者一个指向 posting list 位置的指针

需要计算出 sex='female' and address='北京' 就是把两个 positing list 做一个与合并。ES 中使用 SkipList 数据结构，同时遍历 sex 和 address 的 posting list，相互 skip。

有序集合计算交集

list1: {1,2,3,4,20,21,50,60,70}list2: {50,70}

求交集 拉链法

两个指针指向首元素，比较元素的大小：

• 如果相同，放入结果集，随意移动一个指针

• 否则，移动值较小的一个指针，直到队尾

这种方法的优势：

• 集合中的元素最多被比较一次，时间复杂度 O（N）

• 多个有序集合可以同时进行

求交集 跳表 SkipList

有序链表集合求交集，跳表是最常用的数据结构，它可以将有序集合求交集的复杂度有 O（N）降至 O（Log（N））如果使用拉链法，会发现每个元素都要被比对但是其中很多都是无效比对，时间复杂度为 O（N），所谓跳表可以把时间复杂优化至 LogN，就是因为跳表可以跳过很多无效的对比。

跳表的实现：

搜索的过程：

• 从顶层链表的首元素开始，从左往右搜索，直到找到一个大于或者等于目标的元素，或者到达当前层链表的尾部

• 如果该元素等于目标元素，则表明该元素已经被找到

• 如果该元素大于目标元素或已经到达链表的尾部，则退回到当前层前一个元素，然后转入下一层进行搜索

添加元素，随机决定新添加元素的层数：

删除元素，修改跳表的有效层数：

错误速查

其他系列

🚀 AI 篇持续更新中（长期更新）

AI 炼丹日志-29 - 字节跳动 DeerFlow 深度研究框斜体样式架 私有部署 测试上手 架构研究，持续打造实用 AI 工具指南！AI 研究-132 Java 生态前沿 2025：Spring、Quarkus、GraalVM、CRaC 与云原生落地🔗 AI模块直达链接

💻 Java 篇持续更新中（长期更新）

Java-180 Java 接入 FastDFS：自编译客户端与 Maven/Spring Boot 实战 MyBatis 已完结，Spring 已完结，Nginx 已完结，Tomcat 已完结，分布式服务已完结，Dubbo 已完结，MySQL 已完结，MongoDB 已完结，Neo4j 已完结，FastDFS 已完结，OSS 正在更新... 深入浅出助你打牢基础！🔗 Java模块直达链接

📊 大数据板块已完成多项干货更新（300 篇）：

包括 Hadoop、Hive、Kafka、Flink、ClickHouse、Elasticsearch 等二十余项核心组件，覆盖离线+实时数仓全栈！大数据-278 Spark MLib - 基础介绍 机器学习算法 梯度提升树 GBDT 案例 详解🔗 大数据模块直达链接