首页 > 其他分享 >Roaring Bitmap

Roaring Bitmap

时间:2024-11-05 17:58:54浏览次数:3  
标签:Container 4096 16 Bitmap RBM Array Roaring

Roaring Bitmap

 

原理

Roaring Bitmaps 就是一种压缩位图索引,后文统称 RBM,RBM 的用途和 Bitmap 很差不多(比如说索引),只是说从性能、空间利用率各方面更优秀了。

RBM 的主要思想并不复杂,简单来讲,有如下三条:

  1. 我们将 32-bit 的范围 ([0, n)) 划分为 2^16 个桶,每一个桶有一个 Container 来存放一个数值的低16位;
  2. 在存储和查询数值的时候,我们将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16),取高 16 位找到对应的桶,然后在低 16 位存放在相应的 Container 中;
  3. 容器的话, RBM 使用两种容器结构: Array Container 和 Bitmap Container。Array Container 存放稀疏的数据,Bitmap Container 存放稠密的数据。即,若一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值。

 

举个栗子,现在我们要将 821697800 这个 32 bit 的整数插入 RBM 中,整个算法流程是这样的:

  1. 821697800 对应的 16 进制数为 30FA1D08, 其中高 16 位为 30FA, 低16位为 1D08。
  2. 我们先用二分查找从一级索引(即 Container Array)中找到数值为 30FA 的容器(如果该容器不存在,则新建一个),从图中我们可以看到,该容器是一个 Bitmap 容器。
  3. 找到了相应的容器后,看一下低 16 位的数值 1D08,它相当于是 7432,因此在 Bitmap 中找到相应的位置,将其置为 1 即可。

 

 

 

上面说到,若一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值。

先解释一下为什么这里用的 4096 这个阈值?因为一个 Integer 的低 16 位是 2Byte,因此对应到 Arrary Container 中的话就是 2Byte * 4096 = 8KB;同样,对于 Bitmap Container 来讲,2^16 个 bit 也相当于是 8KB。

然后,基于这两种 Container,在两个 Container 之间的 Union (bitwise OR) 或者 Intersection (bitwise AND) 操作又会出现下面三种场景:

  • Bitmap vs Bitmap
  • Bitmap vs Array
  • Array vs Array

RBM 提供了相应的算法来高效地实现这些操作。

 

一个C++ 开源实现版本

https://github.com/RoaringBitmap/CRoaring

 

标签:Container,4096,16,Bitmap,RBM,Array,Roaring
From: https://www.cnblogs.com/chenny7/p/14676246.html

相关文章

  • 安卓Android 图片/Bitmap工具类
    图片/Bitmap工具类1、根据uri解码图片,通常用在从相册选择照片(1)此方法包含了压缩Bitmap,根据目标尺寸缩放等/***根据Uri解码图片**@paramselectedImage图片的Uri*@return解码后的Bitmap对象*@throwsFileNotFoundException如果文件找不......
  • redis详细教程(3.ZSet,Bitmap,HyperLogLog)
    ZSetRedis的ZSet(有序集合)是一种特殊的数据类型,它允许存储一系列不重复的字符串元素,并为每个元素关联一个分数(score)。这个分数用于对集合中的元素进行排序。ZSet的特点是:唯一性:集合中的每个元素都是唯一的。可排序性:元素可以根据分数进行排序。内部实现:ZSet的内部实现......
  • Redis 的位图(Bitmap)设计签到系统
    在使用Redis的位图(Bitmap)实现签到系统时,可以通过字符串的位定位(bitposition)来记录用户的签到状态。这是一种高效的存储和检索方式,因为你可以在一个字符串中使用位来表示二进制状态,通常每一位(bit)代表一个用户或一天的状态。以下是如何实现签到系统的思路:设计数据结构:每个......
  • Redis 的位图(Bitmap)设计签到系统
    在使用Redis的位图(Bitmap)实现签到系统时,可以通过字符串的位定位(bitposition)来记录用户的签到状态。这是一种高效的存储和检索方式,因为你可以在一个字符串中使用位来表示二进制状态,通常每一位(bit)代表一个用户或一天的状态。以下是如何实现签到系统的思路:设计数据结构:每个用户......
  • 深入理解 Bitmap 应用于缓存穿透与解决方案
    文章目录常见的解决方案方案一:ID校验(检查ID是否小于零)方案二:缓存空结果进阶方案:列表验证合法性使用**Bitmap**优化存储空间Java实现示例:优化提示:结合布隆过滤器减少误判方案总结缓存穿透问题表面上看似复杂,实际上它的本质非常简单:当请求数据库中不存在的数据......
  • Bitmap 和 布隆过滤器傻傻分不清?你这不应该啊
    大家好,我是小富~有个兄弟私下跟我说,他在面试狗东时,有一道面试题没回答上来:Redis的Bitmap和布隆过滤器啥区别与关系?其实就是考小老弟对这两种工具的底层数据结构是否了解,不算太难的题。不过,bitmap和布隆过滤器在大数据量和高并发业务的使用频率不低,知识点应该掌握下,既然问了那咱......
  • 利用Redis的BitMap统计每月用户连续签到
    利用Redis的BitMap统计每月用户连续签到我们按月来统计用户签到信息,签到记录为1,未签到则记录为0.把每一个bit位对应当月的每一天,形成了映射关系。用0和1标示业务状态,这种思路就称为位图(BitMap)。这样我们就用极小的空间,来实现了大量数据的表示Redis中是利用string类型数据......
  • WPF Image display webp via BitMapImgae BeginInit UriSource EndInit in MVVM
    privatevoidGenenerateBitMapImageViaUrl(stringurl){BitmapImagebmi=newBitmapImage();bmi.BeginInit();bmi.UriSource=newUri(url,UriKind.RelativeOrAbsolute);bmi.EndInit();if(bmi.CanFreeze){bmi.Freeze();}......
  • FormatConvertedBitmap DestinationFormat Gray32Float BlackWhite
     <Windowx:Class="WpfApp410.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.micros......
  • WPF 的 WriteableBitmap 在 Intel 11 代 Iris Xe Graphics 核显设备上停止渲染
    在Intel11代锐炬Intel®Iris®XeGraphics核显设备上,如果此设备使用旧版本驱动,则可能导致WPF的WriteableBitmap停止渲染。此问题和WPF无关,此问题是Intel的bug且最新驱动版本已修复官方问题记录地址:https://www.intel.cn/content/www/cn/zh/support/articles/000......