RoaringBitmap位图

时间：2024-10-12 10:01:03

RoaringBitmap位图

  • 前言
    • Bitmap 常用场景
    • Bitmap缺陷
  • RoaringBitmap
    • 主要思想
    • RoaringBitmap 数据结构
      • 整体结构图
      • ArrayContainer
      • BitmapContainer
  • 后记

前言

Bitmap目前是一种比较常见的计数统计模型，Bitmap的数据结构是二进制类型的按位统计，每一位都有两种状态（0，1）。
  • 1

举个例子：比如我们要使用Bitmap记录当前系统的在线人数，假设我们系统有1000个用户（包含在线和不在线的用户），那么我们设定状态0为不在线， 1为在线状态，每一位的顺序代表用户id，初始化Bitmap（1000位）
那么此时模型：000000000… （1000个0）
假设用户id为7的用户登录，那么我们的Bitmap的第7位设置成1代表用户id为7的用户是在线状态。
此时模型：000000100…
因为二进制的特性我们可以进行一些与或非运算以及将二进制转换成十进制。
比如

  • 每周在线的人数统计，将本周每天的Bitmap进行 | 运算 1|1 = 1。
  • 当前日活总数，将二进制转为十进制就是目 000000100… = 1（十进制）

Bitmap 常用场景

  • 快速排序（计数排序）
  • 快速去重
  • 快速查询（如刚刚提到的在线人数查询等）

Bitmap缺陷

Bitmap是一种非常好的数据结构，但是也存在着空间浪费的问题，比如我系统的在线人数是1，整个系统有1000w用户，那么就会造成大量的空间浪费。

RoaringBitmap

针对于Bitmap空间利用率低下的问题，RoaringBitmap相对于Bitmap有效的提高了空间利用率以及提供了更好的性能。并且被Lucene，Spark，Kylin开源框架所采用。

主要思想

RoaringBitmap主要思想是将数据的前16位进行Hash分组，后十六位存储到数据容器中，RoaringBitmap的常用容器目前有两种
ArrayContainer(动态数组最大数组长度为4096的short数组)，BitmapContainer(Bitmap容器这里的实现使用的是长度为1024的Long数组)。
  • 1
  • 2

举个例子：
假设我们要存储userId为100001的用户在线状态，那么我们先将userId转换为二进制：
10000000 00000000 10000110 10100001 那么100001的前十六位 10000000 0000000进行取模运算hash分桶， 确定桶位置后（假设在桶1），确定桶1中当前的容器类型，如果是ArrayContainer则使用二分查找进userId的后16位10000110 10100001转成十进制（100001）插入到指定位置，如果容器类型是BitmapContainer则首先确定十进制（100001）在BitmapContainer的索引i，之后将BitmapContainer[i] 的0000 0000 … (Long）的指定位置为1。

RoaringBitmap 数据结构

整体结构图

整体结构图

ArrayContainer

ArrayContainer是一种动态有序数组结构，每当一个数据进行插入时会先根据二分查找确定新数据的索引，之后进行插入以及动态扩容。
ArrayContainer的最大数组长度是4096。 这里设置成4096的原因是每个short占2B 乘以长度 4096 则消耗内存为8KB， 这里与BitmapContainer（1024固定长度的Long数组）占用大小相等(long占 8B 乘以长度1024 为 8KB)但是由于BitmapContainer占用空间不会继续增多，在ArrayContainer长度大于4096时就会转换成BitmapContainer。

BitmapContainer

BitmapContainer是固定长度为1024的Long（Long是32位二进制）数组，结构如下图
在这里插入图片描述
当新数据插入时，先确定新数据的大小在Long数组中的索引（将long数组拉平 将 index1 + index2…各个二进制连接起来），之后更新指定Long[i]里面二进制的位。

后记

RoaringBitmap是一种相较于Bitmap更加节省空间的数据格式。也是Bitmap的一种压缩算法，相较于其他压缩算法：

  • WAH，
  • ConciseBitmap

RoaringBitmap提供了更好的计算性能，在一些Bitmap运算中可以不进行解压，或者局部解压的方式进行计算。

本文参考：/

相关文章