上一篇【第41篇】为什么需要搜索引擎——关系数据库的搜索困境下一篇【第43篇】Elasticsearch搜索过程原理——分词、查询树与BM25评分摘要倒排索引Inverted Index是Elasticsearch实现高性能全文搜索的基石也是Lucene最核心的数据结构。本文将从正排索引与倒排索引的概念对比入手详细解析倒排索引的逻辑结构包括Term Dictionary词项词典、Posting List文档列表、词频TF和位置Position等核心概念。随后深入Lucene的物理存储结构讲解Segment段机制、Commit Point提交点以及词典文件.tii/.tim和Posting List文件.doc的底层实现。最后介绍FST有限状态转换器的紧凑词典编码、Frame of Reference和Roaring Bitmap的压缩编码技术并通过手动模拟倒排索引的创建过程帮助读者直观理解其工作原理。一、正排索引 vs 倒排索引1.1 正排索引Forward Index正排索引是按照文档到词的映射关系组织的即已知文档查找其中包含的词正排索引结构 ┌──────────┬─────────────────────────────┐ │ 文档ID │ 文档内容 │ ├──────────┼─────────────────────────────┤ │ Doc 1 │ 耐克运动鞋精品推荐 │ │ Doc 2 │ 阿迪达斯运动鞋新款上市 │ │ Doc 3 │ 小米充电宝20000mAh大容量 │ │ Doc 4 │ 运动鞋跑步专用训练鞋 │ └──────────┴─────────────────────────────┘ 查询运动鞋需要逐一遍历每个文档的内容 时间复杂度O(N)1.2 倒排索引Inverted Index倒排索引将映射关系反转为已知词查找包含它的文档倒排索引结构 ┌──────────┬─────────────────────────────┐ │ Term │ 文档列表 │ ├──────────┼─────────────────────────────┤ │ 耐克 │ [1] │ │ 运动 │ [1, 2, 4] │ │ 鞋 │ [1, 2, 4] │ │ 精品 │ [1] │ │ 推荐 │ [1] │ │ 阿迪达斯 │ [2] │ │ 新款 │ [2] │ │ 上市 │ [2] │ │ 小米 │ [3] │ │ 充电宝 │ [3] │ │ 跑步 │ [4] │ │ 专用 │ [4] │ │ 训练鞋 │ [4] │ └──────────┴─────────────────────────────┘ 查询运动鞋直接在词典中查找运动和鞋 时间复杂度O(logN)词典查找 O(K)文档列表遍历1.3 对比总结对比维度正排索引倒排索引映射方向文档 → 词词 → 文档查询方式遍历文档查找词查找词定位文档查找复杂度O(N)O(logN)适用场景根据文档ID获取内容根据关键词搜索文档存储方式行式存储列式存储二、倒排索引的逻辑结构倒排索引由三个核心组件构成Term Dictionary、Posting List和词频与位置信息。2.1 Term Dictionary词项词典Term Dictionary是一个有序的词典存储了所有经过分析器处理后的唯一词项Term。词典按字典序排列支持高效的二分查找。Term Dictionary有序词典 ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ │ 阿迪达斯│ → │ 充电宝 │ → │ 耐克 │ → │ 跑步 │ → ... └───┬───┘ └───┬───┘ └───┬───┘ └───┬───┘ │ │ │ │ ↓ ↓ ↓ ↓ Posting Posting Posting Posting List List List List查找过程二分查找查找运动 第1次比较: 中间词项 耐克 → 运动 耐克右半区 第2次比较: 中间词项 专用 → 运动 专用左半区 第3次比较: 中间词项 运动 → 命中 复杂度: O(logN)N为词典中的词项数量2.2 Posting List文档列表每个Term对应一个Posting List存储了包含该Term的所有文档ID列表Term 运动 的 Posting List: ┌─────┐ ┌─────┐ ┌─────┐ │Doc 1│→ │Doc 2│→ │Doc 4│ └─────┘ └─────┘ └─────┘Posting List的增强信息完整的Posting结构 Term: 运动 Posting List: ┌───────────┬────────────┬───────────────────┐ │ DocID │ TF(词频) │ Position(位置) │ ├───────────┼────────────┼───────────────────┤ │ Doc 1 │ 1 │ [1] │ │ Doc 2 │ 1 │ [2] │ │ Doc 4 │ 2 │ [0, 2] │ └───────────┴────────────┴───────────────────┘ Term: 鞋 Posting List: ┌───────────┬────────────┬───────────────────┐ │ DocID │ TF(词频) │ Position(位置) │ ├───────────┼────────────┼───────────────────┤ │ Doc 1 │ 1 │ [2] │ │ Doc 2 │ 1 │ [3] │ │ Doc 4 │ 2 │ [1, 3] │ └───────────┴────────────┴───────────────────┘2.3 TFTerm Frequency词频词频表示某个Term在文档中出现的次数是相关度评分BM25算法的重要因子Term 运动鞋 的搜索过程 1. 分词: [运动, 鞋] 2. 查找Posting List: 运动 → Doc1(TF1), Doc2(TF1), Doc4(TF2) 鞋 → Doc1(TF1), Doc2(TF1), Doc4(TF2) 3. 合并AND关系: Doc1, Doc2, Doc4 4. 计算相关度分数简化BM25: Doc4: TF(运动)2, TF(鞋)2 → 最高分出现次数多 Doc1: TF(运动)1, TF(鞋)1 → 中等分 Doc2: TF(运动)1, TF(鞋)1 → 中等分 5. 结果排序: Doc4 Doc1 ≈ Doc22.4 Position词位置Position记录了Term在文档中的出现位置支持短语查询和邻近查询短语查询: 运动鞋 需要验证运动和鞋在文档中是否相邻 Doc1: 耐克 运动 鞋 精品推荐 Pos: 1 2 3 运动在位置1, 鞋在位置2 → 相邻 ✓ 匹配 Doc4: 运动 鞋 跑步 训练 鞋 Pos: 0 1 2 3 4 运动在位置0, 鞋在位置1 → 相邻 ✓ 匹配 运动在位置0, 鞋在位置4 → 不相邻 短语查询 运动跑步: Doc1: 运动在位置1, 跑步不存在 → ✗ Doc4: 运动在位置0, 跑步在位置2 → 不相邻 ✗三、Lucene的物理存储结构3.1 Segment段Lucene将倒排索引分为多个不可变的Segment段。每次索引新文档时会创建新的Segment。合并操作Merge会将多个小段合并为大段。索引的段结构 Index ├── Segment_1 (已合并) │ ├── .tim (词典文件) │ ├── .doc (文档列表文件) │ ├── .pos (位置文件) │ ├── .fdx, .fdt (存储字段文件) │ └── .si (段信息文件) │ ├── Segment_2 (新写入) │ ├── .tim │ ├── .doc │ └── ... │ └── Segment_3 (新写入) ├── .tim ├── .doc └── ... Commit Point提交点: 记录当前所有活跃的Segment列表 提交点保证了索引的原子性和一致性Segment是Lucene索引的基本更新单位具有以下特点不可变性一旦创建就不能修改写入即可见新文档写入新Segment后立即可搜索后台合并定期将小段合并为大段优化查询性能删除标记文档删除不是物理删除而是在段中标记为已删除3.2 核心存储文件文件扩展名说明内容.tii词典索引文件Term Dictionary的前缀索引用于加速词典查找.tim词典文件完整的Term Dictionary Posting List偏移量.docPosting List文件文档ID列表、词频等.pos位置文件Term在文档中的位置信息.payPayload文件偏移量、负载等额外信息.fdx字段数据索引指向字段数据的指针.fdt字段数据文件存储字段的原始值storetrue的字段.dvDocValues文件列式存储用于排序和聚合.nvm/.nvdNorms文件归一化因子影响评分.si段信息段的元数据.cfs/.cfe复合文件合并后的文件格式减少文件句柄3.3 词典查找过程查找Term 运动 的物理过程 1. 加载 .tii 文件词典索引 .tii 存储了Term Dictionary的索引块 每个 .tii 条目指向 .tim 中的一段Term范围 2. 在 .tii 中二分查找 定位到 运动 所在的索引块 该索引块指向 .tim 中的偏移量 [offset] 3. 在 .tim 文件中查找 从 offset 开始在对应范围内查找 运动 找到后获取其 Posting List 在 .doc 文件中的偏移量 4. 在 .doc 文件中读取 Posting List 根据 offset 读取 DocID 列表和词频四、FST——紧凑词典实现4.1 什么是FSTFSTFinite State Transducer有限状态转换器是Lucene用来实现Term Dictionary的数据结构具有以下特点内存紧凑高度压缩相比Hash Map节省大量内存前缀共享公共前缀只存储一次后缀共享公共后缀也共享存储有序输出按字典序遍历4.2 FST结构示意普通Trie存储 abc, abd, bef: a b / \ / \ b c e f / \ | c d g Trie存储 abc, abd, bef: 节点数: 8个 FST存储前缀后缀共享: (a) -b→ (c) -#→ 0 | d → #→ 1 (b) -e→ (f) -#→ 2 其中 # 表示终结状态数字表示Posting List的偏移量 FST的优势 - abc 和 abd 共享前缀 ab - 节点数更少内存占用更小 - 对于英文词典通常能压缩到原来大小的1/5~1/104.3 FST的实际效果对于英文词典的压缩效果词典大小HashMap内存占用FST内存占用压缩比10万Term~16MB~3MB~5x100万Term~160MB~30MB~5x1000万Term~1.6GB~300MB~5xFST将整个Term Dictionary加载到内存中通过.tii索引文件和.tim词典文件协同工作。五、Posting List的压缩编码5.1 Frame of ReferenceFORPosting List中的DocID是递增排列的因为文档是按顺序写入的这种有序性使得差值编码Delta Encoding非常高效原始Posting List: [3, 7, 12, 20, 35] 差值编码Delta Encoding: DocID: 3 7 12 20 35 Delta: 3 4 5 8 15 差值都小于32只需要5位bit即可表示 原始DocID需要至少6位最大值35 FOR编码步骤 1. 计算差值序列 2. 找出最大差值15确定每个值的位宽5位 3. 将所有差值用5位紧凑存储Frame of Reference的分块编码分块FOR每256个DocID为一个Block Block 1: [3, 7, 12, 20, 35, ...] (最多256个) → 计算Delta: [3, 4, 5, 8, 15, ...] → 最大值: 15 → 位宽: 5 bits → 编码: 011 100 101 1000 1111 ... Block 2: [150, 160, 172, ...] (最多256个) → 计算Delta: [150, 10, 12, ...] → 最大值: 150 → 位宽: 8 bits → 编码: 10010110 00001010 ... 每个Block存储: [最小DocID] [位宽] [Delta数据] 优势 - 同一Block内的值使用相同的位宽 - 位宽由最大值决定避免浪费 - 块间独立可以随机访问5.2 Roaring Bitmap对于需要快速进行集合运算AND、OR、NOT的场景Lucene使用Roaring Bitmap来压缩Posting List。Roaring Bitmap的核心思想是将32位整数空间划分为65536个Container每个Container覆盖65536个值根据Container内数据密度选择不同的存储方式Roaring Bitmap结构 高16位 低16位 ┌──────────────────────────────┐ │ Container 0 (0-65535) │ │ Container 1 (65536-131071) │ │ Container 2 (131072-196607) │ │ ... │ │ Container 65535 │ └──────────────────────────────┘ Container类型选择根据元素数量动态切换 元素 4096 个: 使用 Bitmap Container固定65536 bits 8KB → 位运算效率高支持快速AND/OR 元素 4096 个: 使用 Array Container有序short数组 → 节省内存每个元素2字节 两种Container可以互相转换根据数据分布自动优化Roaring Bitmap的集合运算查询 运动 AND 鞋: 运动 的 Roaring Bitmap: Container 0: [Doc1, Doc2, Doc4] (Array Container) 鞋 的 Roaring Bitmap: Container 0: [Doc1, Doc2, Doc4] (Array Container) AND运算: Container 0: 两个有序数组取交集 Result: [Doc1, Doc2, Doc4] 时间复杂度: O(n m)n和m为两个Container的元素数量FOR vs Roaring Bitmap对比特性FORRoaring Bitmap编码方式差值 固定位宽分块 Bitmap/Array集合运算需解码后计算原生支持位运算随机访问需遍历前序元素O(1) 随机访问适用场景顺序遍历频繁AND/OR运算内存占用更紧凑略大但可控Lucene会根据查询模式自动选择最优的编码方式。六、手动模拟倒排索引的创建过程6.1 模拟数据假设有以下4篇文档Doc 1 (ID1): 运动鞋跑步专用 Doc 2 (ID2): 耐克运动鞋推荐 Doc 3 (ID3): 充电宝20000mAh Doc 4 (ID4): 运动鞋品牌推荐6.2 步骤1分析Analysis对每个文档的内容进行分词处理使用空格分词器简化演示Doc 1: 运动鞋跑步专用 → [运动鞋, 跑步, 专用] Doc 2: 耐克运动鞋推荐 → [耐克, 运动鞋, 推荐] Doc 3: 充电宝20000mAh → [充电宝, 20000mah] Doc 4: 运动鞋品牌推荐 → [运动鞋, 品牌, 推荐]6.3 步骤2建立倒排索引将分析结果转换为倒排索引结构遍历所有Term建立映射 充电宝 → Doc3 (Position: [0]) 品牌 → Doc4 (Position: [1]) 跑步 → Doc1 (Position: [1]) 耐克 → Doc2 (Position: [0]) 推荐 → Doc2 (Position: [2]), Doc4 (Position: [2]) 专用 → Doc1 (Position: [2]) 运动鞋 → Doc1 (Position: [0]), Doc2 (Position: [1]), Doc4 (Position: [0]) 20000mah→ Doc3 (Position: [1])6.4 步骤3生成最终倒排索引按字典序排列Term┌──────────┬────────────────────────────────────┐ │ Term │ Posting List │ ├──────────┼────────────────────────────────────┤ │ 20000mah │ [Doc3: TF1, Pos[1]] │ │ 品牌 │ [Doc4: TF1, Pos[1]] │ │ 充电宝 │ [Doc3: TF1, Pos[0]] │ │ 跑步 │ [Doc1: TF1, Pos[1]] │ │ 耐克 │ [Doc2: TF1, Pos[0]] │ │ 推荐 │ [Doc2: TF1, Pos[2]], │ │ │ [Doc4: TF1, Pos[2]] │ │ 专用 │ [Doc1: TF1, Pos[2]] │ │ 运动鞋 │ [Doc1: TF1, Pos[0]], │ │ │ [Doc2: TF1, Pos[1]], │ │ │ [Doc4: TF1, Pos[0]] │ └──────────┴────────────────────────────────────┘6.5 步骤4执行搜索查询1搜索运动鞋1. 分析: [运动鞋] 2. 查词典: 运动鞋 → Posting List [Doc1, Doc2, Doc4] 3. 返回结果: Doc1, Doc2, Doc4按相关度排序查询2搜索运动鞋 推荐AND关系1. 分析: [运动鞋, 推荐] 2. 查词典: 运动鞋 → [Doc1, Doc2, Doc4] 推荐 → [Doc2, Doc4] 3. 求交集: [Doc1, Doc2, Doc4] ∩ [Doc2, Doc4] [Doc2, Doc4] 4. 返回结果: Doc2, Doc4查询3短语查询运动鞋推荐1. 分析: [运动鞋, 推荐] 2. 查词典: 运动鞋 → Doc1(Pos[0]), Doc2(Pos[1]), Doc4(Pos[0]) 推荐 → Doc2(Pos[2]), Doc4(Pos[2]) 3. 检查相邻性运动鞋的位置1 推荐的位置: Doc1: 无推荐 → 排除 Doc2: 运动鞋在位置1, 推荐在位置2 → 112 ✓ 匹配 Doc4: 运动鞋在位置0, 推荐在位置2 → 011≠2 ✗ 不匹配 4. 返回结果: Doc26.6 完整流程示意图倒排索引完整工作流程 ┌─────────────┐ │ 原始文档 │ │ Doc1, Doc2..│ └──────┬──────┘ │ 写入 ↓ ┌─────────────┐ │ 分析器 │ ← 分词、过滤、标准化 │ Analyzer │ └──────┬──────┘ │ Term序列 ↓ ┌─────────────────────────────────────────┐ │ 倒排索引 │ │ │ │ ┌──────────────────────┐ │ │ │ Term Dictionary │ ← FST编码 │ │ │ (词典有序) │ │ │ └──────────┬───────────┘ │ │ │ │ │ ↓ │ │ ┌──────────────────────┐ │ │ │ Posting List │ ← FOR/Roaring│ │ │ (文档列表) │ 压缩编码 │ │ │ DocID | TF | Pos │ │ │ └──────────────────────┘ │ └──────────────────┬──────────────────────┘ │ 查询 ↓ ┌─────────────┐ │ 搜索请求 │ │ 运动鞋 推荐│ └──────┬──────┘ │ 分析为Term ↓ ┌─────────────┐ ┌──────────────┐ │ 查词典 │────→│ 合并结果 │ │ 运动鞋 │ │ AND/OR操作 │ │ 推荐 │ └──────┬───────┘ └─────────────┘ │ ↓ ┌──────────────┐ │ 相关度评分 │ │ (BM25算法) │ └──────┬───────┘ │ ↓ ┌──────────────┐ │ 返回结果 │ │ [Doc2, Doc4]│ └──────────────┘七、总结与最佳实践核心要点倒排索引是搜索引擎的基石通过词→文档的反向映射实现O(logN)级别的搜索性能Term Dictionary Posting List词典提供Term的查找入口Posting List提供包含该Term的文档列表FST实现内存高效通过前缀和后缀共享将词典压缩到原大小的1/5~1/10FOR和Roaring Bitmap差值编码和位图压缩使Posting List占用空间大幅减少Segment是不可变单元Lucene通过Segment的不可变性简化并发控制通过后台合并优化查询最佳实践清单理解分析器对倒排索引的影响合理配置分词器注意Posting List的压缩开销极高频Term如的、“是”应加入停用词表Segment大小影响查询性能合理配置合并策略使用_segmentsAPI查看索引段信息通过_analyzeAPI验证分词效果监控索引的段数量和大小避免段过多影响查询上一篇【第41篇】为什么需要搜索引擎——关系数据库的搜索困境下一篇【第43篇】Elasticsearch搜索过程原理——分词、查询树与BM25评分
