Elasticsearch part2—深入讲解ES倒排索引及其优化机制

Elasticsearch的索引

深入理解 ES 的索引

Elasticsearch是一个基于Lucene库的开源搜索引擎，它提供分布式的实时文件存储和搜索，可扩展性好，并且支持通过HTTP网络接口交互，数据以JSON格式展示。

之前中我们介绍过，Elasticsearch 索引是一个逻辑命名空间，其中包含一系列的文档。每个文档由一系列字段组成，字段则是包含数据的键值对。可以将 Elasticsearch 集群视为一个数据库，索引就相当于数据库中的表，而文档类似于表中的行。

而关系数据库中的索引是与表相关联的一种数据结构，用于加速数据检索。

Elasticsearch 索引是一个包含文档的逻辑单元，且无需预先定义模式便可导入数据，具有更高的灵活性。

而 Elasticsearch 的索引机制是完全不同于MySQL的 B+Tree 结构。索引会被压缩放入内存用于加速搜索过程，这一点在效率上是完爆 MySQL 的。但是 Elasticsearch 会对全部 text 字段进行索引，必然会消耗巨大的内存，为此Elasticsearch针对索引进行了深度的优化。在保证执行效率的同时，尽量缩减内存空间的占用。

首先，要记住，Elasticsearch会对所有输入的文本进行处理，建立索引放入内存中，从而提高搜索效率。

而 MySQL 是将索引放入磁盘，每次读取需要先从磁盘读取索引然后寻找对应的数据节点

但是ES能够直接在内存中就找到目标文档对应的大致位置，最大化提高效率。

索引

ES将数据存储于一个或多个索引中，索引是具有类似特性的文档的集合。类比传统的关系型数据库领域来说，索引相当于SQL中的一个数据库。

一个ES集群中可以按需创建任意数目的索引，但根据不同的硬件配置，索引数有一个建议范围

在ES中每个字段都是被索引的，所以不会像MySQL中那样需要对字段进行手动的建立索引。

索引的组成部分

索引名称：是索引的唯一标识符，必须为小写字母，不能包含特殊字符，用于在集群中识别该索引。
设置（Settings）：用于配置索引的各种行为和属性，如分片数量、副本数量、分析器、刷新间隔、段合并策略等，这些设置会直接影响索引的性能、可用性和功能。
映射（Mappings）：定义了文档的结构和字段类型，可通过动态映射让 Elasticsearch 自动检测数据类型，也可预先定义显式映射来精确控制数据的索引方式。
别名（Aliases）：为索引创建的虚拟名称，可用于更灵活地访问索引，比如在索引重建或迁移时，通过别名可以不改变应用程序的访问方式。

分片和副本

索引被分成多个分片，每个分片是一个独立的 Lucene 索引，允许数据分布在集群中的多个节点上，从而实现水平扩展和并行处理。
每个分片可以有零个或多个副本，副本是分片的拷贝，用于提供高可用性和负载均衡，防止数据丢失。

索引的数据结构

对于文本字段，Elasticsearch 会将其进行分词，然后存储在倒排索引中，通过倒排索引可以快速执行文本查询。
对于数字和地理位置数据，则存储在 BKD 树中，以实现高效的空间索引和查询。此外，Elasticsearch 还支持通过 dense_vector 文档类型存储用于相似性搜索的稠密矢量。

在 ES9 中，索引出现了许多的新特性，Elasticsearch 9.0 基于 Lucene 10 运行，对多核机器的搜索并行处理更加高效，对高延迟存储（如对象存储）的 I/O 处理更好，同时稀疏索引得到改进，提高了 CPU 和存储效率，使搜索操作在不同的存储和计算环境中更加高效，降低了大规模部署的延迟。

而 Logsdb 索引模式在 9.0 的新部署中默认启用，且支持基于排序字段的自定义路由，与 8.17 相比，基准测试中存储减少了 20%，优化了存储布局，提升了查询性能并降低了存储成本。此外，还新增了一个选项，允许用户在启用合成源时跳过索引中的恢复源，消除了不必要的处理开销并减少了 IO，提升了索引吞吐量。

而 Elasticsearch 9.x 中语义检索功能正式可用，语义检索基于向量搜索，通过将原始的文本、图片或音视频等素材资源向量化，然后在查询时根据输入条件与存储的向量信息进行相似度匹配，能够检索到含义相关的内容，而不仅仅是字面匹配。

而 ES 在建立索引的时候采用了一种叫做倒排索引的机制，保证每次在搜索关键词的时候能够快速定位到这个关键词所属的文档。

倒排索引

什么是倒排索引

Elasticsearch 使用的是一种称为倒排索引的结构，采用Lucene倒排索引作为底层。这种结构适用于快速的全文搜索，一个索引由文档中所有不重复的列表构成，对于每一个词，都有一个包含它的文档列表

那么 ES 的特点是倒排索引，什么是正排索引呢？

在数据库中，索引就像一本书的目录，它能帮你快速找到内容，而不需要一页一页地翻。

正排索引和我们习惯的思维方式一样。它是一种“文档 -> 关键词”的映射。

例如，我们有三本书（文档）：

文档1： { "id": 1, "content": "今天天气很好" }
文档2： { "id": 2, "content": "今天不上班" }
文档3： { "id": 3, "content": "天气好就出去玩" }

正排索引就是按文档ID顺序存储文档内容。想找包含“天气”的文档，你必须逐个扫描每个文档的内容，效率较低（O(n)复杂度）。

而倒排索引则相反，它是一种“关键词 -> 文档”的映射。它反转了这个关系。

对于上面的三个文档，构建的倒排索引大概是这个样子：

关键词	文档ID列表
今天	[1, 2]
天气	[1, 3]
很好	[1]
不上班	[2]
好	[3]
就	[3]
出去玩	[3]

那么这时候，我们需要寻找包含关键词“天气”的文档，在其中发现了关键词天气对应的文档 ID 有 1，3，这样就比正排索引要快很多。

所以说倒排索引的核心是一个词典和一个倒排记录表。

词典：包含所有在文档集合中出现过的、独一无二的关键词（或称为“词项”）。
倒排记录表：对于词典中的每个词项，都关联着一个列表（称为“Posting List”），这个列表记录了所有包含这个词项的文档ID。

所以，倒排索引本质上就是一个巨大的“词到文档”的映射词典。

比如有三句话在数据库中：

Winter is coming Ours is fury Ths choice is yours

如果没有倒排索引（Inverted Index），想要去找其中的choice，需要遍历整个文档，才能找到对应的文档的id

这样做效率是十分低的，所以为了提高效率，我们就给输入的所有数据的都建立索引，并且把这样的索引和对应的文档建立一个关联关系，相当于一个词典。当我们在寻找choice的时候就可以直接像查字典一样，直接找到所有包含这个关键词 choice 的文档的id，然后找到数据。

引用：https://zhuanlan.zhihu.com/p/137574234

可以把倒排索引想象成一本书末尾的“索引”部分（比如一本技术书的术语索引）。如果你想找“分布式系统”相关的内容，你不需要一页一页地翻完整本书，而是直接去书后的索引里找到“分布式系统”这个词，它后面会列出所有提到这个词的页码。你直接翻到这些页码就行了。

Elasticsearch 的倒排索引就是这个原理的超级增强版，通过分词、规范化、压缩、不可变段、高效数据结构等一系列精妙的工程实现，使得它能够在浩如烟海的数据中，实现“大海捞针”般的即时响应。

倒排索引的工作流程

倒排索引的工作流程可以分为两大步：索引创建（写入） 和 查询处理。

索引创建

所以说，当你向 Elasticsearch 插入一个文档时，它并不会直接将其存入索引，而是经过一系列处理

文本分析：

分词：首先，将文本内容打碎成一个个独立的词条。例如，“Today is a good day!” 会被分词成 [“today”, “is”, “a”, “good”, “day”]。
规范化：
- 转小写：将所有字母转为小写，确保搜索 “today” 也能匹配到 “Today”。
- 去除停用词：移除 “a”, “an”, “the”, “is” 等没有实际搜索意义的词。
- 词干提取：将单词还原为其词根形式。例如 “running” -> “run”, “flies” -> “fly”。这样搜索 “run” 也能匹配到 “running”。
  
  这个过程由 Elasticsearch 中的 分析器 完成。

构建倒排索引：

经过分析后，我们得到了一系列规范化的词项。
对于每个词项，将其添加到全局的词典中（如果不存在），然后在这个词项对应的倒排记录表（Posting List）中，追加当前文档的ID。
实际上，Posting List 存储的不仅仅是文档ID，通常还包括：
- 文档ID：用于确定哪个文档。
- 词频：该词项在文档中出现的次数，用于相关性打分。
- 位置信息：词项在文档中出现的位置（第几个词），用于支持短语查询（如 “红色汽车” 必须是 “红色” 和 “汽车” 紧挨着的组合）。

查询处理

当你在 Elasticsearch 中执行一个搜索时（例如搜索 “天气好”）：

查询解析与分析：
- 首先，对查询字符串 “天气好” 进行同样的文本分析（分词、规范化）。假设它被分词为 [“天气”, “好”]。
查找倒排索引：
- 在词典中分别查找词项 “天气” 和 “好”。
- 获取到它们对应的倒排记录表：
  - “天气” -> [1, 3]
  - “好” -> [3]
集合运算：
- 根据你的查询逻辑（比如是 OR 还是 AND），对这两个列表进行集合运算。
- 如果是默认的 OR 逻辑（对应 should），结果是并集 [1, 3]。
- 如果是 AND 逻辑（对应 must），结果是交集 [3]。
相关性打分与排序：
- Elasticsearch 使用一种复杂的算法（通常是 TF-IDF 或 BM25）为每个匹配的文档计算一个相关性得分。
- TF：词频。一个词在单个文档中出现的次数越多，该文档对于该词的得分可能越高。
- IDF：逆文档频率。一个词在所有文档中出现的频率越低（越稀有），它的权重就越高。
- 结合 TF 和 IDF，以及其他因素（如字段长度归一化），计算出最终得分。
- 最后，按照得分从高到低返回结果。

ES的倒排索引如何支持海量数据

简单的倒排索引在数据量小的时候没问题，但在 ES 这种处理 PB 级数据的系统中，需要更精妙的设计。

不可变性、段和合并
- Elasticsearch 中的倒排索引是不可变的。一旦创建，就不能被修改。
- 优点： 1) 缓存友好；2) 无需锁，并发性能高；3) 可以安全地在内存中压缩。
- 如何更新？：当文档更新或删除时，ES 并不会直接修改旧的索引，而是：
  - 为新文档创建一个新的、小的倒排索引片段，称为 “段”。
  - 将文档的删除操作记录在一个单独的 .del 文件中。
- 段合并：随着段的增多，查询效率会下降（因为需要查询多个段再合并结果）。ES 会在后台定期将多个小的段合并成一个大的段，并在合并过程中真正地处理掉被标记为删除的文档。
高效的数据结构
- 词典查找：如何在百万甚至亿级的词项中快速找到 “weather” 这个词？
  - FST： ES 使用 有限状态转换器 来存储词典。它是一种类似 Trie 树的结构，但内存效率极高，可以快速进行精确查找和前缀查找。
- 倒排记录表： Posting List 如何高效地进行交集、并集操作？
  - 编码压缩： Posting List 存储的文档ID通常是递增的，ES 会使用诸如 Frame of Reference 等编码方式对差值进行压缩，大大减少磁盘占用和内存占用。
  - Roaring Bitmaps：对于可用于筛选的字段（如 keyword, date），ES 使用 Roaring Bitmaps 来存储其倒排列表，这是一种非常高效进行位运算（与、或）的数据结构。

这部分内容会在下面细说

倒排索引的工作机制

ES如何把索引搬入内存

Lucene在对文档建立索引的时候，会给词典的所有的元素排好序，在搜索的时候直接根据二分查找的方法进行筛选就能够快速找到数据。

不过是不是感觉有点眼熟，这不就是MySQL的索引方式的，直接用B+树建立索引词典指向被索引的文档。

但是ES做的要更深一点，ES希望把这个词典“搬进”内存，直接从内存读取数据不就比从磁盘读数据要快很多

问题在于对于海量的数据，索引的空间消耗十分巨大，直接搬进来肯定不合适，所以需要进一步的处理，建立词典索引（term index）。通过词典索引可以直接找到搜索词在词典中的大致位置，然后从磁盘中取出词典数据再进行查找。所以大致的结构图就变成了这样：

很类似二级索引，ES通过有限状态转化器，把term dictionary变成了term index，放进了内存

从 O(n) 的全表扫描，变成了 O(1) 的词典查找 + O(m) 的列表合并（m是结果集大小，通常很小）。这种效率的提升是数量级的。

而且倒排索引将分散在大量文档中的信息，按关键词聚合在了一起。查询时只需要读取相关词项对应的少量数据，而不是所有文档，极大地减少了 I/O。

而且 ES 的索引是缓存友好的，索引的不可变性意味着一旦被加载到内存，就可以被多个查询安全、高效地共享。ES 大量使用了文件系统缓存来加速查询。

在并行上，一个查询可以同时在不同的段上执行，然后将结果合并。这种分而治之的策略充分利用了多核CPU的优势。

有限状态转换器FST

有限状态转换器FST 相当于是一个Trie前缀树，可以直接根据前缀就找到对应的term在词典中的位置。这里使用到了字典树的算法

你可以把 FST 理解成一个超级压缩的前缀树，核心作用是用极小的内存存下所有关键词（Term），同时快速定位它们的位置。

为什么要这样处理？词典里的关键词往往有很多重复前缀（比如 “mop” 和 “moth” 都以 “mo” 开头），直接存完整单词太浪费空间。FST 会把这些重复前缀合并，只存不同的部分。

所以这个树并不会包含所有的term，而是很多term的前缀，通过这些前缀快速定位到这个前缀所属的磁盘的block（磁盘块），再从这个block去找文档列表。

为了压缩词典的空间，实际上每个block都只会保存block内不同的部分，比如mop和moth在同一个以mo开头的block，那么在对应的词典里面只会保存p和th，这样空间利用率提高了一倍。

使用有限状态转换器在内存消耗上面要比远比SortedMap要少，但是在查询的时候需要更多的CPU资源。维基百科的索引就是使用的FST，只使用了69MB的空间，花了大约8秒钟，就为接近一千万个词条建立了索引，使用的堆空间不到256MB。

比如我们现在有已经排序好的单词mop、moth、pop、star、stop和top以及他们的顺序编号0..5，可以生成一个下面的状态转换图

有 “mop”“moth”“pop”“star”“stop”“top” 这 6 个词，FST 会：

合并相同前缀：“mop” 和 “moth” 共享 “mo”，只额外存 “p” 和 “th”；
用 “状态转换” 记录路径：比如输入 “stop”，会沿着s→t→o→p的路径走，每个步骤对应一个编号，最终算出这个词在词典中的位置（例子中是 4）。而对于mop，得到的排序的结果是0

那么 FST 还涉及到了许多 ES 中的其他内容

在ES中有一种查询叫模糊查询（fuzzy query），模糊查询是指允许输入词有拼写错误（比如搜 “stap” 想匹配 “stop”），通过 “编辑距离”（增删改字母的次数）判断是否匹配。

在ES4.0之前，模糊查询会先让检索词和所有的term计算编辑距离筛选出所有编辑距离内的字段，也就是拿查询词和词典里所有词一个个算编辑距离，符合条件的才保留。如果词典很大，这一步会非常慢。

在ES4.0之后，采用了由Robert开发的，直接用 FST 找符合编辑距离的词，因为 FST 本身是按前缀和路径组织的，能在遍历路径时就过滤出 “只差几个字母” 的词，不用全量计算，效率提升 100 倍以上，将模糊查询的效率提高了超过100倍。

现在已经把词典压缩成了词条索引，尺寸已经足够小到放入内存，通过索引能够快速找到文档列表。解决了 “关键词词典” 的压缩问题，但是！

每个关键词对应的文档 ID 列表（posting list）如果直接存，空间还是很大：

比如 1 亿个文档，每个文档有 10 个字段，可能要存 10 亿个整数（每个文档 ID 是整数），太占磁盘。

核心思路是：Elasticsearch 会对文档 ID 列表做进一步压缩，比如用差值编码、bit 压缩等方式，只存必要的信息，减少磁盘占用。

Posting Lists 倒排列表

这个倒排列表本质上就是解决 “文档 ID 存储占用过多磁盘空间” 的问题

倒排列表是从 “关键词（Term）” 到 “包含该关键词的文档 ID 集合” 的映射。

比如，关键词 “Elasticsearch” 的倒排列表，会存储所有包含 “ Elasticsearch” 的文档 ID（如[1,3,5,7]）。

为了高效存储和压缩，Elasticsearch 会对文档 ID 做两个关键处理：

整型唯一标识：（整型化）

文档在存入 Elasticsearch 时，会被转化为唯一的整型 ID（而不是原始的字符串 ID 或其他类型）。因为整数（integer）天生适合压缩，能大幅减少存储体积。
分片内的分段分配

Elasticsearch 的索引会被拆分为多个shard（分片），每个shard又会细分为更小的segment（段）。每个segment内部，文档 ID 是从 0 开始连续分配的，且每个segment最多存储 231 个文档（约 21 亿）。
- 这样做的好处是：每个segment内的文档 ID 范围固定且连续，为后续的 “差值压缩” 等算法提供了基础。
也就是说，ES 把索引拆成了很多个段，然后把索引对应的文档 ID 从0开始连续存入到每个段

假设直接存储 10 亿个文档 ID（每个用 4 字节的integer），需要约 4GB 空间。Elasticsearch 通过对整数序列的压缩算法，大幅减少存储开销，核心逻辑基于 “整数的特性” 和 “segment内文档 ID 的连续性”。

差值压缩（Delta Encoding）

由于segment内的文档 ID 是连续分配的（从 0 开始递增），倒排列表中的文档 ID 序列天然具有 “有序且递增” 的特点。
- 例如，某倒排列表的文档 ID 是[5,6,8,10]，直接存储需要 4 个integer。
- 用差值压缩后，只需要存储 “第一个 ID” 和 “后续每个 ID 与前一个的差值”
  
  第一个 ID 是5，后续差值为1（6-5）、2（8-6）、2（10-8）。
  
  存储的内容变为[5,1,2,2]，整体数值更小，更易压缩。
变长编码（Variable-Length Encoding）

对于压缩后的差值（或原始小整数），Elasticsearch 会用 “变长编码” 进一步压缩：
- 小整数可以用更少的字节存储（比如 1 个字节存1，而不是 4 字节的integer）；
- 常用算法如VInt（Variable Integer）*或*ZigZag 编码，能根据数值大小动态调整存储长度，避免固定字节的浪费。

每个segment是独立的存储单元，且会定期合并（Merge）。这种设计带来两个优势：

压缩粒度更细：

每个segment内的文档 ID 范围小且连续，差值压缩的效果更好（差值更小，更易压缩）。
合并时的二次压缩：

当多个小segment合并为大segment时，会对倒排列表再次进行压缩优化，进一步减少存储体积。

总结一下就是利用整数的可压缩性，以及 segment 内文档 ID 的有序性，将原本庞大的文档 ID 列表，压缩到远小于原始大小的体积，从而在保证查询效率的同时，大幅节省存储成本。

索引帧 Frame of Reference

在 Elasticsearch 中，常见组合查询（如 “同时包含 A 和 B 的文档” 或 “包含 A 或 B 的文档”），需要对多个倒排列表做 ** 交集（AND）或并集（OR）** 操作。

为了让 “交集 / 并集” 操作更高效，倒排列表中的文档 ID 必须是有序的，这样可以用 “双指针” 等算法快速合并。
但有序的文档 ID 直接存储会占用大量空间（比如 10 亿个文档 ID，每个用 4 字节integer，需要约 4GB）。

为了压缩空间，Elasticsearch 首先对有序的文档 ID 做增量编码（也叫差值编码）：

原理：存储 “当前 ID 与前一个 ID 的差值”，而非原始 ID。因为文档 ID 是有序递增的，差值通常比原始 ID 小很多，更易压缩。
示例：

原始 ID 列表：
1
[73, 300, 302, 332, 343, 372]
增量编码后（第一个 ID 的 “前一个 ID” 默认是 0，所以差值是自身）：
1
[73, 227, 2, 30, 11, 29]
可以看到，差值普遍比原始 ID 小，为后续更精细的压缩创造了条件。

在增量编码后，Elasticsearch 进一步通过 “分块 + 按位存储” 实现极致压缩，这就是 Frame of Reference（索引帧）技术。

分块算法就是其中的核心，Elasticsearch 会把增量编码后的差值列表，分成多个小 “块（Block）”（默认每个块包含 256 个文档的差值）。

目的是让每个块内的差值 “尽可能小且均匀”，从而用更少的二进制位存储每个差值。

然后按位封装（Bit-Packing），对每个块，Elasticsearch 会：

计算 “存储该块内所有差值，需要的最小二进制位数”（比如块内最大差值是 227，二进制是11100011，需要 8 位）；
把这个 “位数” 作为 ** 头信息（Header）** 存到块的开头；
然后用这个 “位数”，将块内的每个差值紧凑地按位存储（而不是用固定的 4 字节integer）。

有这样的一个压缩过程

原始 ID 列表：[73, 300, 302, 332, 343, 372] → 增量编码后：[73, 227, 2, 30, 11, 29]

步骤 1：分块

假设每个块存 3 个差值（实际默认是 256 个），则分成 2 个块：

块 1：[73, 227, 2]；块 2：[30, 11, 29]。
步骤 2：计算每个块的 “最小位数”
- 块 1 最大差值是 227，二进制是11100011，需要8 位存储；
- 块 2 最大差值是 30，二进制是11110，需要5 位存储。
步骤 3：按位存储 + 头信息
- 块 1：头信息存 “8”（占 1 字节），然后每个差值用 8 位（1 字节）存储，共 3 个差值 → 1 + 3×1 = 4 字节；
- 块 2：头信息存 “5”（占 1 字节），然后每个差值用 5 位存储（不足 1 字节的部分会紧凑拼接），共 3 个差值 → 1 + (3×5)/8 ≈ 3 字节（实际计算为向上取整，这里简化为 3 字节）；
- 总空间：4 + 3 = 7 字节，而原始 6 个 ID（每个 4 字节）需要 24 字节 → 空间效率提升约 3 倍。

压缩后的数据不需要 “全部解压后再查询”，而是通过迭代器（Iterator）逐次读取：

迭代器会根据 “头信息的位数”，从压缩数据中 “按需解压” 当前需要的差值；
这样可以避免 “全量解压” 的内存和计算开销，保证查询时的性能。

过滤器Filter

ES中的过滤器是干什么的

在 Elasticsearch 的查询上下文（Query Context）中，过滤器是一种用于筛选出完全匹配指定条件的文档的组件。它的核心任务是进行二元判断：“是”或“否”。一个文档要么满足过滤条件，要么不满足。它不关心文档与条件有多匹配，只关心是否匹配。

像在电商网站中使用筛选栏。你勾选“品牌：苹果”、“内存：128GB”。系统会精确地找出所有同时满足这两个条件的商品，返回的结果没有“相关度”的概念，所有结果都是平等的。

在 Elasticsearch 早期，查询和过滤器是两种独立的 API。后来它们被合并到 bool 查询中，但底层的行为和优化机制依然不同。理解它们的区别是使用好过滤器的关键。

特性	查询	过滤器
核心目标	查找相关的文档，并计算其相关性得分（_score）。	筛选出匹配/不匹配的文档，不关心得分。
得分计算	是。会计算 `_score`，这是一个相对昂贵的计算过程。	否。结果只有“匹配”或“不匹配”，不计算 `_score`。
性能	相对较慢，因为需要计算得分。	非常快。
缓存	默认不被缓存。	结果会被自动缓存。相同的过滤条件再次执行时，会直接从缓存中读取，速度极快。
使用场景	全文搜索、关键词搜索，任何需要结果排序的场景。	精确值匹配、范围查询、是否存在的判断，用于快速缩小结果集。

过滤器是如何工作的，工作流程如下

当执行一个过滤操作时（例如 term 过滤）：

查找倒排索引：与查询一样，ES 会去倒排索引中查找对应的词项，获取其倒排记录表。
位图操作： ES 会使用一种叫做位图的高效数据结构来表示匹配的文档。
- 想象一个很长的位数组，每一位代表一个文档ID（例如，第0位代表文档1，第1位代表文档2…）。
- 如果文档匹配，该位被设置为 1，否则为 0。
- 对于多个过滤条件（如 A AND B），ES 只需对两个位图进行快速的位与操作。对于 OR 操作，则进行位或操作。这些位运算在计算机底层是极其快速的。
返回结果：得到最终的位图，所有值为 1 的位对应的文档就是匹配的文档。由于不计算得分，这个过程到此基本结束。

也就是说，ES 中的过滤器放弃了评分，换来了无与伦比的筛选速度和系统效率。

缓存位图 Roaring Bitmaps

缓存机制是过滤器快如闪电的最重要原因。这离不开缓存位图的实现

什么是被缓存的？
- 过滤器的结果位图会被缓存起来。例如，你过滤 category: "electronics"，ES 会计算出所有分类为电子产品的文档的位图，并将这个位图缓存起来。
为什么能缓存？
- 因为过滤器是确定性的且不计算得分。对于相同的过滤条件，无论你执行多少次，结果集都是一模一样的。这使得缓存结果变得安全且有意义。
缓存的是什么级别？
- 缓存发生在段（Segment） 级别。每个段都有自己的缓存。如果一个段的文档没有变化，那么针对该段的过滤结果就可以一直被复用。
什么类型的过滤器容易被缓存？
- term 过滤器： {"term": { "status": "published" }}
- range 过滤器： {"range": { "age": { "gte": 18 }}}
- bool 过滤器组合

缓存的效果：第一次执行某个过滤条件可能会稍慢，但之后所有相同的过滤请求都会直接从内存中的缓存位图里获取结果，速度极快，对 CPU 几乎零压力。

Elasticsearch 中，filter查询（如范围查询、术语查询）是高频操作，且结果可以被缓存（因为filter不计算相关性得分，结果稳定）。但缓存面临两个矛盾：

性能需求：缓存要足够快，否则不如直接查询；
空间需求：缓存不能占用过多内存 / 磁盘，但传统结构（如普通数组、Bitmap）在 “空间 - 性能” 上难以兼顾。

Roaring Bitmap 是对 “整数数组” 和 “Bitmap（位图）” 的改良，结合了两者的优点：

整数数组：查询快，但空间消耗大；
Bitmap：空间紧凑，但小数据量时浪费（比如存 1 个 ID，Bitmap 也需要 12.5MB 空间）。

Roaring Bitmap 的工作原理如下

按 “高 16 位” 分块

将文档 ID（32 位整数）的高 16 位作为 “块 ID（Block ID）”，低 16 位作为 “块内 ID”。
- 示例：ID 为1000，高 16 位是0（因为 1000<216=65536），低 16 位是1000；
- 块的范围：每个块对应 “高 16 位相同” 的 ID，比如块0包含 ID 0~65535，块1包含65536~131071，以此类推。
块内动态选择存储结构

对每个块，根据 “块内 ID 的数量”，选择更高效的存储方式：
- 数量 < 4096：用short数组存储（每个 ID 的低 16 位用 2 字节的short表示）；
- 数量 ≥ 4096：用Bitmap存储（此时 Bitmap 的空间利用率更高）。
  - 数组查询是 “直接寻址”，Bitmap 是 “位运算”，两者都很快；
  - 相比之前的Frame of Reference（需要解压 + 按位解析），Roaring Bitmap 的 CPU 消耗更小，查询更高效。

可以发现，这很类似于计算机操作系统的内存块交换

存在这样一个流程，简单讲解一下

原始 ID 列表：[1000, 62101, 131385, 132052, 191173, 196658]

步骤 1：计算块 ID 和块内 ID

块 ID = ID÷65536（整数除法），块内 ID = ID%65536（取余）：
- 1000 → 块 ID 0，块内 ID 1000；
- 62101 → 块 ID 0（62101÷65536=0），块内 ID 62101；
- 131385 → 块 ID 2（131385÷65536=2），块内 ID 131385 % 65536 = 313；
- 以此类推，得到每个 ID 的(块ID, 块内ID)对。
步骤 2：分块存储
- 块0：包含(0,1000)、(0,62101) → 块内 ID 数量为 2（< 4096），用short数组存储；
- 块2：包含(2,313)、(2,980)、(2,60101) → 数量为 3（< 4096），用short数组存储；
- 块3：包含(3,50) → 数量为 1（< 4096），用short数组存储。
步骤 3：空间对比（为何选 4096 为分界）
- 若用Bitmap存 4095 个 ID：需要 4095÷8≈512 字节？不，实际 Bitmap 是按 “最大 ID” 分配空间。比如块内最大 ID 是 65535（2^16-1），则 Bitmap 需要 65536÷8=8192 字节（8KB）；
- 若用short数组存 4095 个 ID：每个short占 2 字节，总空间 4095×2=8190 字节（约 8KB），与 Bitmap 接近；
- 若数量 < 4096（比如 2048 个）：short数组空间是 2048×2=4096 字节（4KB），远小于 Bitmap 的 8KB → 因此选 4096 为分界，小数量时用数组更省空间。