Elasticsearch 底层原理系列（二）：倒排索引原理
2020-10-20·6 分钟阅读
前言
倒排索引（Inverted Index）是搜索引擎的核心数据结构，也是 Elasticsearch 高效检索的基础。理解倒排索引的实现原理，对于深入掌握 ES 的查询性能和存储优化至关重要。
本章将深入剖析 Lucene 倒排索引的内部实现，包括 Term Dictionary、Postings List、FST 等核心组件。
技术亮点
| 技术点 | 难度 | 面试价值 | 本文覆盖 |
|---|---|---|---|
| 倒排索引结构 | ⭐⭐⭐ | 高频考点 | ✅ |
| Term Dictionary 实现 | ⭐⭐⭐⭐ | 高频考点 | ✅ |
| FST 数据结构 | ⭐⭐⭐⭐⭐ | 进阶考点 | ✅ |
| Postings List 压缩 | ⭐⭐⭐⭐ | 进阶考点 | ✅ |
面试考点
- 什么是倒排索引？为什么搜索引擎使用倒排索引？
- Lucene 的 Term Dictionary 是如何实现的？
- FST 是什么？它解决了什么问题？
- Postings List 使用了哪些压缩技术？
倒排索引基础
什么是倒排索引
倒排索引是一种将"词"映射到"文档"的数据结构。与之相对的是"正排索引"（Forward Index），即从"文档"到"词"的映射。
┌─────────────────────────────────────────────────────────────────────────┐
│ 正排索引 vs 倒排索引 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 正排索引（Forward Index） │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ Document ID │ Content │ │
│ ├───────────────┼─────────────────────────────────────────────┤ │
│ │ Doc 1 │ "Elasticsearch is powerful" │ │
│ │ Doc 2 │ "Lucene is the core of Elasticsearch" │ │
│ │ Doc 3 │ "Search engine is useful" │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ │ │
│ ▼ 构建 │
│ │
│ 倒排索引（Inverted Index） │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ Term │ Document IDs │ │
│ ├────────────────┼─────────────────────────────────────────────┤ │
│ │ elasticsearch │ [1, 2] │ │
│ │ lucene │ [2] │ │
│ │ search │ [3] │ │
│ │ engine │ [3] │ │
│ │ powerful │ [1] │ │
│ │ core │ [2] │ │
│ │ useful │ [3] │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
为什么选择倒排索引
┌─────────────────────────────────────────────────────────────────────────┐
│ 倒排索引的优势 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 查询："包含 Elasticsearch 的文档" │
│ │
│ 正排索引方案： │
│ • 遍历所有文档 │
│ • 对每个文档进行全文匹配 │
│ • 时间复杂度：O(N × L)，N=文档数，L=平均文档长度 │
│ │
│ 倒排索引方案： │
│ • 直接查找 Term "elasticsearch" │
│ • 返回 [1, 2] │
│ • 时间复杂度：O(log M)，M=词项数量 │
│ │
│ 结论：倒排索引将查询复杂度从线性降低到对数级别 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
倒排索引的组成
Lucene 的倒排索引由三个核心部分组成：
┌─────────────────────────────────────────────────────────────────────────┐
│ 倒排索引的三层结构 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Term Dictionary（词项字典） │ │
│ │ │ │
│ │ 排序后的所有词项列表，支持快速查找 │ │
│ │ ┌─────┬─────┬─────┬─────┬─────┐ │ │
│ │ │apple│ ... │lucene│ ... │zoo │ │ │
│ │ └──┬──┴─────┴──┬──┴─────┴──┬──┘ │ │
│ └──────┼───────────┼───────────┼──────────────────────────────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Term Index（词项索引） │ │
│ │ │ │
│ │ 存储词项的前缀，用于快速定位到 Term Dictionary │ │
│ │ 使用 FST（有限状态转换器）实现，内存占用极小 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Postings List（倒排表） │ │
│ │ │ │
│ │ 每个词项对应的文档 ID 列表，包含位置和偏移信息 │ │
│ │ ┌────────────────────────────────────────────────────────┐ │ │
│ │ │ DocID │ Freq │ Positions │ Offsets │ Payload │ │ │
│ │ ├───────┼──────┼───────────┼─────────┼──────────────────┤ │ │
│ │ │ 1 │ 2 │ [3, 10] │ [12,28] │ ... │ │ │
│ │ │ 5 │ 1 │ [7] │ [45,52] │ ... │ │ │
│ │ └────────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Term Dictionary（词项字典）
Term Dictionary 存储了索引中所有的词项（Term），并按照字典序排序。
┌─────────────────────────────────────────────────────────────────────────┐
│ Term Dictionary 存储结构 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 磁盘文件：.tim（Term Dictionary） │
│ │
│ ┌────────────────────────────────────────────────────────────────┐ │
│ │ Block 0 │ │
│ │ ┌──────────┬──────────┬──────────┬──────────┬──────────┐ │ │
│ │ │ apple │ apply │ apt │ archive │ are │ │ │
│ │ │ →block │ →block │ →block │ →block │ →block │ │ │
│ │ └──────────┴──────────┴──────────┴──────────┴──────────┘ │ │
│ └────────────────────────────────────────────────────────────────┘ │
│ │ Block 1 │ │
│ │ ┌──────────┬──────────┬──────────┬──────────┬──────────┐ │ │
│ │ │ art │ article │ artist │ ask │ at │ │ │
│ │ └──────────┴──────────┴──────────┴──────────┴──────────┘ │ │
│ └────────────────────────────────────────────────────────────────┘ │
│ │ ... │ │
│ │
│ 特点： │
│ • 每个 Block 包含 25-48 个 Term │
│ • Block 内的 Term 共享前缀压缩 │
│ • Block 有最小/最大 Term 作为索引 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Term Index（词项索引）
Term Index 是 Term Dictionary 的索引，存储在内存中，用于快速定位 Term 所在的 Block。
问题：为什么不直接把 Term Dictionary 加载到内存？
┌─────────────────────────────────────────────────────────────────────────┐
│ Term Index 的必要性 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 假设： │
│ • 100 万文档，平均每文档 100 词 │
│ • 去重后约 1000 万 Term │
│ • 每个 Term 平均 10 字节 │
│ │
│ Term Dictionary 大小： │
│ 1000万 × 10字节 = 100MB（仅词项本身） │
│ 加上指针和其他元数据，可能达到 200-500MB │
│ │
│ ❌ 全量加载到内存不可行！ │
│ │
│ 解决方案：Term Index │
│ • 只存储 Term 的前缀（如前 3 字节） │
│ • 使用 FST 压缩存储 │
│ • 内存占用可控制在几 MB │
│ │
└─────────────────────────────────────────────────────────────────────────┘
FST（Finite State Transducer）
FST 是 Lucene 4.0 引入的核心数据结构，用于存储 Term Index。
┌─────────────────────────────────────────────────────────────────────────┐
│ FST 结构示例 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 存储词项：["mop", "moth", "pop", "star", "stop"] │
│ │
│ ┌───► [o] ───► [p] ───► (终) "mop" │
│ │ │
│ ┌───► [m] ──────┤ │
│ │ │ │
│ │ └───► [o] ───► [t] ───► [h] ───► (终) "moth" │
│ │ │
│ (起点)──┤ │
│ │ ┌───► [p] ───► (终) "pop" │
│ │ │ │
│ ├───► [p] ──────┤ │
│ │ │ │
│ │ └───► [o] ───► [p] ───► (终) "pop" │
│ │ │
│ │ ┌───► [t] ───► [a] ───► [r] ───► (终) "star" │
│ │ │ │
│ └───► [s] ┤ │
│ │ │
│ └───► [t] ───► [o] ───► [p] ───► (终) "stop" │
│ │
│ 特点： │
│ • 共享公共前缀，极大节省空间 │
│ • 支持快速前缀查找 │
│ • 支持模糊查询（Levenshtein 自动机） │
│ │
└─────────────────────────────────────────────────────────────────────────┘
FST 的优势
| 特性 | 说明 |
|---|---|
| 空间效率 | 共享前缀，压缩率高，典型压缩比 10:1 |
| 查询效率 | O(k) 复杂度，k 为查询词长度 |
| 前缀查询 | 天然支持前缀匹配 |
| 模糊查询 | 结合 Levenshtein 自动机实现 |
| 内存友好 | 可序列化到磁盘，按需加载 |
Postings List（倒排表）
Postings List 存储每个 Term 对应的文档列表。
基本结构
┌─────────────────────────────────────────────────────────────────────────┐
│ Postings List 结构 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Term: "elasticsearch" │
│ │
│ ┌────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ DocID: 1 5 12 23 45 67 89 │ │
│ │ │ │ │ │ │ │ │ │ │
│ │ Freq: 2 1 3 1 2 1 4 │ │
│ │ │ │ │ │ │ │ │ │ │
│ │ Pos: [3,10] [7] [1,5,9] [12] [4,8] [6] [2,5,7,11] │ │
│ │ │ │
│ └────────────────────────────────────────────────────────────────┘ │
│ │
│ 字段说明： │
│ • DocID：文档 ID（实际上是在 Segment 内的序号） │
│ • Freq：词频，该词在文档中出现的次数 │
│ • Pos：位置信息，用于短语查询 │
│ • Offset：偏移信息，用于高亮显示 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Skip List（跳表）
为了加速 Postings List 的遍历，Lucene 使用跳表数据结构：
┌─────────────────────────────────────────────────────────────────────────┐
│ Skip List 结构 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Level 2: [1] ─────────────────────────────────────────► [89] │
│ │ │ │
│ Level 1: [1] ────────────► [23] ────────────► [67] ───► [89] │
│ │ │ │ │ │
│ Level 0: [1]─►[5]─►[12]─►[23]─►[45]─►[67]─►[89]─►[102]─►[89] │
│ │
│ 查询 DocID=45 的过程： │
│ 1. Level 2: 1 < 45, 跳到 89（太大），下降 │
│ 2. Level 1: 1 → 23 < 45, 跳到 67（太大），下降 │
│ 3. Level 0: 23 → 45 找到！ │
│ │
│ 复杂度：O(log n) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
压缩技术
Postings List 使用多种压缩技术减少存储空间：
1. Delta Encoding（差值编码）
┌─────────────────────────────────────────────────────────────────────────┐
│ Delta Encoding │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 原始 DocIDs: [1, 5, 12, 23, 45, 67, 89] │
│ │
│ 差值编码后: [1, 4, 7, 11, 22, 22, 22] │
│ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ └── 89 - 67 = 22 │
│ │ │ │ │ │ └────── 67 - 45 = 22 │
│ │ │ │ │ └────────── 45 - 23 = 22 │
│ │ │ │ └────────────── 23 - 12 = 11 │
│ │ │ └────────────────── 12 - 5 = 7 │
│ │ └────────────────────── 5 - 1 = 4 │
│ └───────────────────────── 保持 1 │
│ │
│ 优势：较小的数值可以用更少的字节存储 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2. Variable Byte Encoding（变长字节编码）
┌─────────────────────────────────────────────────────────────────────────┐
│ Variable Byte Encoding │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 原理：根据数值大小使用不同字节数 │
│ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 数值范围 │ 字节数 │ 示例 │ │
│ ├────────────────┼────────┼────────────────────────────────────┤ │
│ │ 0 - 127 │ 1 字节 │ 1 → [0x01] │ │
│ │ 128 - 16383 │ 2 字节 │ 300 → [0x82, 0x2C] │ │
│ │ 16384 - 2097151│ 3 字节 │ 50000 → [0xC3, 0x50, 0x00] │ │
│ └──────────────────────────────────────────────────────────────┘ │
│ │
│ 节省空间：小数值只占用 1 字节而非固定 4 字节 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. Frame of Reference (FOR)
Lucene 使用 Frame of Reference 对 Postings List 进行批量压缩：
┌─────────────────────────────────────────────────────────────────────────┐
│ Frame of Reference │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 将 DocIDs 分成 128 个一组： │
│ │
│ Block 1: [1, 4, 7, 11, 22, ..., ?] (128 个 delta 值) │
│ │
│ 1. 找出最大值所需位数（如最大值 22 需要 5 bits） │
│ 2. 用 5 bits 存储每个值 │
│ 3. Block 大小：128 × 5 = 640 bits = 80 bytes │
│ │
│ 对比： │
│ • 不压缩：128 × 32 bits = 4096 bits = 512 bytes │
│ • 压缩后：80 bytes │
│ • 压缩比：6.4:1 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Doc Values
除了倒排索引，Lucene 还使用 Doc Values 存储列式数据，用于排序、聚合等操作。
┌─────────────────────────────────────────────────────────────────────────┐
│ Doc Values vs Inverted Index │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Inverted Index: Term → DocIDs（适合搜索） │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ Term │ DocIDs │ │
│ │ "lucene" │ [1, 3, 5, 7] │ │
│ │ "search" │ [2, 4, 6, 8] │ │
│ └────────────────────────────────────────────────────────┘ │
│ │
│ Doc Values: DocID → Value（适合聚合、排序） │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ DocID │ price │ timestamp │ category │ │
│ ├───────┼───────┼──────────────────┼─────────────────────┤ │
│ │ 1 │ 100 │ 2023-08-30 10:00 │ electronics │ │
│ │ 2 │ 250 │ 2023-08-30 11:00 │ books │ │
│ │ 3 │ 80 │ 2023-08-30 12:00 │ electronics │ │
│ └────────────────────────────────────────────────────────┘ │
│ │
│ 列式存储优势： │
│ • 同一列数据连续存储，压缩率高 │
│ • 聚合时只需读取相关列，减少 I/O │
│ • 排序时直接访问，无需"反排"倒排索引 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
查询流程详解
Term 查询流程
┌─────────────────────────────────────────────────────────────────────────┐
│ Term 查询流程 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 查询：找到包含 "lucene" 的文档 │
│ │
│ Step 1: 在 FST 中查找前缀 │
│ ┌──────────────────────────────────────┐ │
│ │ 内存中的 FST: [l] → [u] → [c] ... │ │
│ │ 找到 "lucene" 对应的 Block 指针 │ │
│ └──────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ Step 2: 在 Term Dictionary 中精确定位 │
│ ┌──────────────────────────────────────┐ │
│ │ 磁盘上的 .tim 文件 │ │
│ │ 读取 Block，找到 "lucene" 的位置 │ │
│ └──────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ Step 3: 读取 Postings List │
│ ┌──────────────────────────────────────┐ │
│ │ 磁盘上的 .doc 文件 │ │
│ │ 读取 DocIDs: [1, 5, 12, 23] │ │
│ └──────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ Step 4: 返回结果 │
│ ┌──────────────────────────────────────┐ │
│ │ 返回文档列表给查询执行器 │ │
│ └──────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
多 Term 查询（AND/OR）
┌─────────────────────────────────────────────────────────────────────────┐
│ 多 Term 查询 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 查询："lucene" AND "search" │
│ │
│ Step 1: 获取两个 Postings List │
│ ┌──────────────────────────────────────┐ │
│ │ "lucene" → [1, 5, 12, 23, 45] │ │
│ │ "search" → [2, 5, 8, 23, 67] │ │
│ └──────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ Step 2: 求交集（类似归并排序） │
│ ┌──────────────────────────────────────┐ │
│ │ 指针同时遍历两个列表 │ │
│ │ [1, 5, 12, 23, 45] │ │
│ │ ↑ │ │
│ │ [2, 5, 8, 23, 67] │ │
│ │ ↑ │ │
│ │ │ │
│ │ 5 匹配！继续... │ │
│ │ 最终结果: [5, 23] │ │
│ └──────────────────────────────────────┘ │
│ │
│ 复杂度：O(n + m)，n、m 为两个列表长度 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
存储文件一览
Lucene 倒排索引相关的文件：
┌─────────────────────────────────────────────────────────────────────────┐
│ Lucene 索引文件 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Segment 文件（每个 Segment 一组）： │
│ │
│ .tim Term Dictionary 词项字典 │
│ .tip Term Index 词项索引（FST） │
│ .doc Postings List 倒排表 │
│ .pos Positions 位置信息 │
│ .pay Payloads 载荷和偏移 │
│ .fdt Field Data 存储字段 │
│ .fdx Field Index 字段索引 │
│ .dvd Doc Values 列式存储 │
│ .dvm Doc Values Metadata 元数据 │
│ │
│ 其他文件： │
│ .si Segment Info Segment 元信息 │
│ segments_N Commit Point │
│ │
└─────────────────────────────────────────────────────────────────────────┘
最佳实践
字段类型选择
// 根据使用场景选择字段类型
{
"mappings": {
"properties": {
"title": {
"type": "text", // 全文搜索
"analyzer": "standard"
},
"status": {
"type": "keyword" // 精确匹配、聚合
},
"price": {
"type": "double", // 数值类型，支持范围查询
"doc_values": true // 默认开启，用于排序聚合
},
"description": {
"type": "text",
"index": false, // 不索引，仅存储
"store": true
}
}
}
}
性能优化建议
┌─────────────────────────────────────────────────────────────────────────┐
│ 倒排索引优化建议 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 合理设置分词器 │
│ • 选择合适的 Analyzer 减少词项数量 │
│ • 使用 filter 过滤无用词（停用词等） │
│ │
│ 2. 控制字段索引 │
│ • 不需要搜索的字段设置 "index": false │
│ • 不需要聚合的字段设置 "doc_values": false │
│ │
│ 3. 避免高基数字段 │
│ • 高基数字段会生成大量 Term │
│ • 考虑使用 keyword + wildcard 替代 │
│ │
│ 4. 合并 Segment │
│ • 定期执行 force_merge 减少段数量 │
│ • 但不要过度合并，影响写入性能 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
总结
本章深入解析了倒排索引的实现原理：
- 三层结构：Term Index (FST) → Term Dictionary → Postings List
- FST 优势：共享前缀、内存友好、支持前缀和模糊查询
- 压缩技术：Delta Encoding、Variable Byte、Frame of Reference
- Doc Values：列式存储，用于排序聚合
参考资料
- Apache Lucene - Index File Formats
- Exploring Apache Lucene - Part 1: The Index
- From FST to Lucene Index Storage
下一章预告
下一章将探讨 文档写入流程，包括：
- Write → Buffer → Refresh → Segment 的完整流程
- Translog 的作用与配置
- Flush 操作与数据持久化
相关文章
Elasticsearch 底层原理系列（一）：架构概述
2020-10-06·5 分钟阅读
深入理解 Elasticsearch 整体架构设计，包括核心概念、分层架构、Lucene 与 ES 的关系，以及分布式搜索的基本原理。
Elasticsearch 底层原理系列（九）：生产实践与性能调优
2020-12-31·6 分钟阅读
深入解析 Elasticsearch 生产环境最佳实践，包括硬件选型、JVM 调优、索引设计、性能监控与调优、常见问题排查。
Elasticsearch 底层原理系列（八）：分布式一致性
2020-12-20·5 分钟阅读
深入解析 Elasticsearch 分布式一致性机制，包括 Master 选举、脑裂问题、故障检测与恢复、以及数据一致性保证。