ap和稠密的占用空间相 同。通常会使用一种bitmap压缩算法迚行优化。 RoaringBitmap是一种已被业界广泛使用的高效的bitmap压缩算法，使用者包括Spark、 Hive、ElasticSearch、Kylin、Druid、InfluxDB等， 详见：http://roaringbitmap.org/ 通过单个bitmap可以完成精确去重操作，通过多个bitmap的and、or、xor、andnot等位 8, 13, 21] RoaringBitmap原理介绍 主要原理：将32bit的Integer划分为高16位和低16位(两个short int)，两者之间是Key-Value的 关系。高16位存到short[] keys，通过高16位（Key）找到所对应Container，然后把剩余的低 16位（Value）放入该Container中，RoaringBitmap有三类Container： 10 RoaringBitmap原理介绍 11 丌仅数据结构设计精巧，而且还有 很多高效的Bitmap计算函数。 稀疏数据，劢态分配 最大存储：4096元素 最大空间：8KB 连续数据，劢态分配 最大存储：65536元素 最大空间：128KB 稠密数据，固定大小 最大存储：65536元素 最大空间：8KB RoaringBitmap原理介绍 丼个栗子：

Merge，减少倒排链 Merge 耗时。 后端 < 939 ● 内存占用少，需要处理千万数量级的倒排链。 在给出具体的解决方案之前，先介绍一下 Lucene 对于倒排合并的原生实现、 RoaringBitMap、Index Sorting。 4.2.1 原生实现 Lucene 在不同场景上使用了不同的倒排格式，提高整体的效率（空间 / 时间），通过 火焰图可以发现，在我们的场景上，TermInSetQuery 情况下，耗时明显。 我们采用线上流量和数据压测发现该部分平均耗时约 7 ms。 4.2.2 RoaringBitmap 当前 Elasticsearch 选择 RoaringBitMap 做为 Query Cache 的底层数据结构缓存 倒排链，加快查询速率。 940 > 2022年美团技术年货 RoaringBitmap 是一种压缩的位图，相较于常规的压缩位图能提供更好的压缩，在 稀疏数据的场景下空间更有优势。以存放 null 节省空间。 RoaringBitmap 有不同的实现方式，下面 以 Lucene 实现（RoaringDocIdSet）进行详细讲解： 如原理图中所示，RoaringBitmap 中存在两种不同的 Container：Bitmap Contain- er 和 Array Container。 图 3 Elasticsearch 中 Roaringbitmap 的示意图 这两种 Container