跳至主要內容

ElasticSearch中的倒排索引是如何工作的

Corey2026/5/12大约 5 分钟面试题面试题

来源：ElasticSearch中的倒排索引是如何工作的

一、 标准面试回答模版（建议背诵）

面试官： ElasticSearch 的倒排索引是如何工作的？为什么它比 MySQL 快？

Fox版标准回答： “倒排索引（Inverted Index）是 Elasticsearch 能够实现亿级数据毫秒级搜索的核心基石。它的核心逻辑与传统数据库的正排索引（ID找内容）相反，它是‘根据内容（词项）找文档 ID’，类似于书籍末尾的‘关键词索引页’。

我对倒排索引的理解，核心概括为‘三层物理架构，三个核心算法’：

三层物理架构（从内存到磁盘）：

  1. Term Index（词项索引）： 它是‘字典的目录’，常驻内存。它的作用是快速定位到 Term Dictionary 在磁盘上的大概位置（Block）。
  2. Term Dictionary（词项字典）： 它是‘字典的正文’，存储了所有的 Term（单词），按字典序排序，存储在磁盘上。
  3. Posting List（倒排表）： 它是 Term 对应的‘文档 ID 列表’，记录了该词在哪些文档出现过，也存储在磁盘上。

三个核心算法（核心竞争力）：

  1. FST（有限状态转换器）： 用于压缩 Term Index。它通过共享前缀和后缀，将几千万个 Term 的索引压缩到几百 MB，使其能塞进内存。
  2. FOR（Frame of Reference）： 用于压缩 Posting List。它通过存储 ID 的‘差值（Delta）’和‘位打包’，极大地减少磁盘占用和 I/O 开销。
  3. Roaring Bitmap（咆哮位图）： 用于高效计算 交集（Filter查询）。它解决了传统 Bitmap 在稀疏数据下的空间浪费问题，兼顾了省内存和高性能位运算。”

二、 原理与数据结构层面的体现

1. 场景一：内存放不下怎么办？—— Term Index 与 FST（空间换时间）

  • 场景： 假设你的 ES 里有 10 亿个不同的单词（Term）。

  • 问题： 如果用 HashMap 存这 10 亿个词的索引，光是对象头和指针就能把 32G 内存撑爆，直接 OOM。

  • ES 的解法（FST）：

  • 原理： FST (Finite State Transducer) 将线性的单词集合看作一个“图”。它不仅共享前缀（如 mop 和 moth 共享 mo），还共享后缀（如 mop 和 pop 共享 op）。

  • 效果： 它可以将内存占用降低到 HashMap 的 1/20 甚至更低。

  • 代码体现： 当 ES 启动或 Segment merge 时，会将 Term Dictionary 的前缀抽出来构建 FST 加载到堆外内存（Off-heap）中。

2. 场景二：磁盘 I/O 瓶颈 —— Posting List 与 FOR（增量编码）

  • 场景： 单词 "Java" 非常热门，出现在 1 亿个文档中。Posting List 就是一个包含 1 亿个 Integer 的数组。

  • 问题： 直接存 int[]，占用 4字节 * 1亿 = 400MB。搜一个词就要加载 400MB 数据，磁盘 I/O 必死。

  • ES 的解法（FOR）：

  • 原理： 不存原值，存差值（Delta）。

  • 演示：

  • 原数据：[1000000, 1000001, 1000002]

  • 存差值：[1000000, 1, 1] （第一个存原值，后面存 Delta）

  • 位打包： 后面的 1 只需要 1 bit 就能存储，而不需要 32 bit。

  • 效果： 数据体积被压缩几十倍，读取速度飞升。

3. 场景三：联合查询性能 —— Roaring Bitmap（位图进化）

  • 场景： 执行 SQL：select * from user where gender='female' and age=18。这是两个 Posting List 求交集。

  • 问题： 如果用传统 Bitmap，ID 范围是 1 到 1 亿，Bitmap 需要 12MB。但如果只有两个文档符合条件，中间全是 0，空间极度浪费（稀疏问题）。

  • ES 的解法（Roaring Bitmap）：

  • 原理： 将 ID 切分成高 16 位和低 16 位。高 16 位作为 Key，低 16 位放入 Container。

  • 智能切换：

  • Array Container： 如果 Container 里 ID 少（<4096），直接存 short[] 数组（省空间）。

  • Bitmap Container： 如果 Container 里 ID 多（>4096），自动升级为 Bitmap（位运算快）。

  • 效果： 既解决了稀疏浪费，又保留了位运算的高效。

三、 Fox的深度解析

如果面试官问：“为什么 ES 检索快，但更新/删除慢？” 或者 “ES 和 MySQL 的 B+ 树有什么本质区别？”

Fox版解析：

1. 关于“不可变性”与“伪更新”： “面试官，这是一个非常好的问题。倒排索引有一个致命的特性：它是 Immutable（不可变）的。

  • 原因： 一旦 FST 和 FOR 压缩生成落盘，想往里面插入一个 ID 或修改一个词，就得把整个结构解压、重排、再压缩，这代价是无法承受的。

  • 后果： 所以 ES 的‘更新’（Update）其实是 Delete + Insert。

  • 删除： 并不是真的删文件，而是在 .del 文件里给这个 DocID 打个‘已删除’的标记（逻辑删除）。搜索时依然能搜到，只是在最后一步被过滤掉了。这也是为什么删除数据后磁盘空间不降反升的原因。

  • 写入： 新数据会生成一个新的 Segment（段）。

  • 避坑： 生产环境中要控制 Segment 的数量，定期执行 force_merge，否则大量的逻辑删除数据会拖慢查询性能。”

2. 关于 ES vs MySQL B+ 树的权衡： “我认为没有万能的数据库，只有最适合的场景：

  • MySQL (B+ 树)： 本质是‘正排索引’的变种（聚簇索引）。它适合‘精准定位’和‘范围查询’（因为 key 有序）。但在处理 LIKE '%keyword%' 这种模糊匹配时，因为无法走索引，必须全表扫描，性能极差。
  • ES (倒排索引)： 本质是‘词项词典’。它天生就是为了‘模糊匹配’和‘全文检索’设计的。它通过 FST 快速定位 Block，再通过倒排表直接拿到 ID。
  • 结论： 简单的 ID 查询或数值范围查询，MySQL 更好；复杂的全文搜、多维度 Filter 组合查询，ES 是降维打击。”