ElasticSearch核心引擎Apache Lucene（一）：倒排索引底层实现
文章目录
- 0. 全局视野：Lucene 索引结构思维导图
- 1. 倒排索引 (Inverted Index) 的基石
- 核心组成
- 2. Term Dictionary 的极致压缩：FST
- FST 原理图解
- FST 的优势
- 3. Posting List 的压缩艺术：Frame of Reference (FOR)
- 核心思想：分治 (Divide and Conquer)
- 形象案例
- 动态策略：三种容器 (Container)
- A. Array Container (数组容器) —— 人少的时候用
- B. Bitmap Container (位图容器) —— 人多的时候用
- C. Run Container (行程容器) —— 连号的时候用
- 核心难点图解：为什么界限是 4096？
- 结构示意图
- 为什么 Roaring Bitmaps 做交集（AND）这么快？
- 情况 1：Bitmap vs Bitmap
- 情况 2：Array vs Array
- 情况 3：Bitmap vs Array
- 总结
在分布式搜索引擎 ElasticSearch (ES) 的光环之下，默默支撑其海量数据毫秒级检索能力的，是底层的核心库 —— Apache Lucene。
很多开发者知道 ES 使用“倒排索引”，但对于倒排索引内部如何极致压缩空间、如何利用位运算加速过滤，往往知之甚少。本文将深入 Lucene 文件的内核，拆解其三大核心黑科技：FST (Finite State Transducers)、Frame of Reference (FOR) 以及 Roaring Bitmaps。
0. 全局视野：Lucene 索引结构思维导图
在深入细节前，我们先通过一张思维导图，俯瞰 Lucene 倒排索引的完整结构。
1. 倒排索引 (Inverted Index) 的基石
传统的数据库（如 MySQL）使用正排索引（Forward Index），即 ID -> Data。当我们搜索包含关键词 “Apple” 的文章时，数据库需要扫描每一行数据（Full Table Scan）或依赖 B+Tree 的最左前缀匹配。
Lucene 采用倒排索引，即 Term -> List。它就像书籍末尾的“索引页”，告诉我们某个单词出现在了哪几页。
核心组成
一个倒排索引主要由两部分组成：
- Term Dictionary (词项字典): 记录所有文档中出现过的单词（Term），并排序。
- Posting List (倒排表): 记录每个 Term 对应的文档 ID 集合，以及词频、偏移量等信息。
2. Term Dictionary 的极致压缩：FST
问题场景：
假设我们有十亿条数据，分词后的 Term 数量可能达到上千万。
- 如果将 Term Dictionary 全部存入内存（HashMap/TreeMap），内存会直接爆炸。
- 如果存入磁盘，每次查找都需要多次磁盘 IO，速度太慢。
- B+Tree 虽然优秀，但对于 String 类型的 Key，空间利用率不够极致。
解决方案：FST (Finite State Transducers)
FST 是一种有穷状态转换器。它本质上是一个有向无环图 (DAG)。Lucene 使用 FST 将 Term Dictionary 以极小的内存代价加载到内存（或通过 mmap 映射）。
FST 原理图解
假设我们有三个单词：mop, moth, pop, star, stop, top。
FST 会通过共享前缀和共享后缀来压缩存储。
(注：真实的 FST 还会为每条边赋予权重（Output），用于直接计算该 Term 在磁盘 Block 中的位置)
FST 的优势
- 空间换时间？不，是空间时间双赢：FST 的查找复杂度为
O(len(term))，与字典大小无关。 - 极度压缩：通过共享前缀和后缀，FST 可以将 Term Dictionary 压缩到原大小的 10% ~ 30% 甚至更低。这使得 ES 可以将索引常驻内存（Heap 外内存）。
- 前缀匹配神器：非常适合处理
prefix查询、Fuzzy 查询。
3. Posting List 的压缩艺术：Frame of Reference (FOR)
核心思想：分治 (Divide and Conquer)
传统的位图（BitSet）是一个巨大的、连续的 0/1 数组。
如果我们要存数字 2000000000（20亿），在传统 BitSet 中，我们需要申请 20亿个 bit 的空间（约 238MB），哪怕里面只存了这一个数字，前面的空间全是 0，极其浪费。
Roaring Bitmaps 的解决思路是：切分。
它将 32 位整数（Integer）切分为两部分：高 16 位 和 低 16 位。
- 高 16 位 (Key)：好比“宿舍楼号”。
- 低 16 位 (Value)：好比“房间号”。
32 位整数 = ( 高 16 位 ≪ 16 ) + 低 16 位 32位整数 = (高16位 ll 16) + 低16位 32位整数=(高16位≪16)+低16位
关键点：
2
16
=
65536
2^{16} = 65536
216=65536。
这意味着，每一个“宿舍楼”（高 16 位确定的桶）里，最多只能容纳 65536 个数字（0 ~ 65535）。
形象案例
假设我们要存三个数：10、65540、131080。
- 数字 10：
- 10 / 65536 = 0 10 / 65536 = 0 10/65536=0 (第 0 栋楼)
- 10 % 65536 = 10 10 % 65536 = 10 10%65536=10 (房间号 10)
- 数字 65540：
- 65540 / 65536 = 1 65540 / 65536 = 1 65540/65536=1 (第 1 栋楼)
- 65540 % 65536 = 4 65540 % 65536 = 4 65540%65536=4 (房间号 4)
- 数字 131080：
- 131080 / 65536 = 2 131080 / 65536 = 2 131080/65536=2 (第 2 栋楼)
- 131080 % 65536 = 8 131080 % 65536 = 8 131080%65536=8 (房间号 8)
Roaring Bitmap 会创建 3 个“桶”（Container），每个桶只负责管理自己那 65536 个数字范围内的事务。
动态策略：三种容器 (Container)
这是 Roaring Bitmap 最聪明的地方。对于每一个“宿舍楼”（Container），它根据里面住的人数（数据稀疏程度），自动选择最省空间的记账方式。
我们有三种记账本（容器类型）：
A. Array Container (数组容器) —— 人少的时候用
- 场景：这个“宿舍楼”里住的人很少（稀疏）。
- 结构：直接用一个
short[]数组，把房间号列出来。 - 存储：存
[10, 25, 300]。 - 占用空间：每个数字占 2 Bytes（short 类型）。
- 优点：人少时非常省空间。
- 缺点：查找需要二分查找，O(logN)。
B. Bitmap Container (位图容器) —— 人多的时候用
- 场景：这个“宿舍楼”里住的人很多（稠密）。
- 结构：直接搞一张固定的表格（BitSet），共有 65536 个格子，有人住就打勾（置 1），没人住就空着（置 0）。
- 占用空间：固定 8 KB。
- 计算方式： 65536 bits / 8 = 8192 Bytes = 8 KB 65536 ext{ bits} / 8 = 8192 ext{ Bytes} = 8 ext{ KB} 65536 bits/8=8192 Bytes=8 KB。
- 优点：无论存多少个数，空间固定；查找、判断是否存在只需 O(1)。
C. Run Container (行程容器) —— 连号的时候用
- 场景：住的人都是连续的，比如从 10 号房间到 1000 号房间都住了人。
- 结构：只记“起始房间”和“连续长度”。
- 存储：存
(10, 990)，表示从 10 开始，后面 990 个都有数据。 - 优点：对于连续数据压缩率极高。
核心难点图解：为什么界限是 4096？
你可能会问：什么时候从 Array Container 切换到 Bitmap Container？
答案是：4096 个元素。这是通过数学计算得出的“盈亏平衡点”。
我们来算一笔账：
- Array Container：存 N 个数，消耗 N × 2 N imes 2 N×2 Bytes。
- Bitmap Container：不管存几个数，固定消耗 8192 Bytes (8KB)。
这就变成了一个初中数学题：
N
×
2
<
8192
N imes 2 < 8192
N×2<8192
N
<
4096
N < 4096
N<4096
- 结论：
- 当一个 Block 里的数据少于 4096 个时，用 Array 存，因为它占用的空间小于 8KB。
- 当数据超过 4096 个时，Array 会占用超过 8KB，这时候直接申请一个 8KB 的 Bitmap 反而更省空间！
结构示意图
为什么 Roaring Bitmaps 做交集（AND）这么快？
ES 查询 status:active AND type:video 时，就是在做两个 Posting List 的交集。
Roaring Bitmap 的交集运算非常智能，它不是傻傻地挨个比对，而是同类型匹配：
情况 1：Bitmap vs Bitmap
这是最快的情况。
- 操作：直接对底层的
long[]数组进行位运算（Bitwise AND）。 - 原理：计算机 CPU 做位运算极快，而且现代 CPU 支持 SIMD（单指令多数据流）指令集，一次可以处理多个字长。这基本上是纳秒级的速度。
情况 2：Array vs Array
这是归并排序逻辑。
- 操作：两个有序数组找相同元素。
- 优化：如果两个数组大小差距很大（例如一个有 10 个元素，一个有 2000 个），它不会从头遍历，而是使用二分查找或者**指数查找（Galloping Search）**来跳过不需要比较的数据。
情况 3：Bitmap vs Array
这是查表逻辑。
- 操作：遍历 Array 中的每一个元素，看它在 Bitmap 中对应的位置是不是 1。
- 复杂度：O(N)，N 是 Array 的长度。因为 Bitmap 查找是 O(1) 的。
总结
当我们在这个瞬间发起一次 ES 查询时，底层发生了一系列精妙的配合：
- FST 像一张超浓缩的地图，在内存中瞬间定位到 Term 对应的 Block 指针。
- IndexReader 读取磁盘上的 Block，利用 FOR 算法极其紧凑地解压出 Posting List。
- 如果存在 Filter 查询，Roaring Bitmaps 将利用 CPU 的位运算能力，以纳秒级的速度完成集合的交、并、差操作。
正是这些对数据结构极致的压榨和优化，造就了 Lucene 乃至 ElasticSearch 的搜索引擎霸主地位。
参考资料:
- Apache Lucene Core Documentation
- “Roaring Bitmaps: Implementation of an Optimized Software Library”
- ElasticSearch: The Definitive Guide
