Bitmap、Roaring Bitmap、HyperLogLog对比介绍

一、Bitmap（位图）概述

Bitmap 是一种用位（bit）来表示集合元素是否存在的数据结构。每个位代表一个元素的状态（0或1），非常节省空间且支持快速集合操作。

常见Bitmap类型：

1. 普通Bitmap

   • 最简单的位数组，适合元素范围固定且不稀疏的场景。
   • 例如，元素范围是0~1000，用1001个位表示是否存在。

2. Roaring Bitmap

   • 一种压缩型Bitmap，适合稀疏和密集数据混合的场景。
   • 通过分块和压缩技术，既节省空间又保持高效操作。

二、Roaring Bitmap

1. 概念

Roaring Bitmap是一种高效的压缩位图格式，广泛应用于大数据系统（如Druid、ClickHouse、Apache Spark等）。

2. 原理

• 分块存储：将整个整数空间分成多个固定大小的块（通常是2^16大小的区间）。
• 块内存储：
  <