RoaringBitmaps的设计原理是什么

蜗牛vps 互联网技术资讯 2021-12-03 272 0

RoaringBitmaps的设计原理是什么,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

刚接触编程那会记得用 Bitmap 的 0 和 1 位来标识数据是否存在,主要用于排序;

后来发现只要判断一个对象在大对象集合存在性,都可以考虑使用 Bitmap;

再后来,我知道了布隆这个人使用 Hash 算法结合 Bitmap 实现了 BoomFilter,用于海量数据处理场景,我觉得布隆过滤器在做数据过滤这方面天下无敌;

后来的后来,有人问我,布隆过滤器虽然解决了数据过滤问题,但是它不支持数据修改和删除,另外如果数据稀疏,只有最低位是 1,其它都是 0,还是会造成资源浪费。又该怎么办呢?

下面结合自己理解简单介绍下 RoaringBitmaps

 

RoaringBitmaps

RoaringBitmaps简称 RBM,主要是将 32 位无符号整数按照高 16 位分桶,即最多可能有 2^16=65536 个桶,论文内称为 container。存储数据时,按照数据的高 16 位找到 container,如果找不到就会新建一个,再将低 16 位放入 container 中。也就是说,一个 RBM 就是很多 container 的集合。

 

设计思想

RBM 的主要思想并不复杂,总结来说,有如下几点:

  • 将 32-bit 的范围 ([0, n)) 划分为 2^16 个桶,每一个桶有一个 Container 来存放一个数值的低 16 位;

  • 在存储和查询数值的时候,我们将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16),取高 16 位找到对应的桶,然后在低 16 位存放在相应的 Container 中;

  • 容器的话, RBM 使用三种容器结构:Array ContainerBitmap ContainerRunContainer。Array Container 存放稀疏的数据,Bitmap Container 存放稠密的数据。即,若一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值;RunContainer 则用于存储连续的数据。举个例子,连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被 RLE 压缩为两个二元组 11, 4, 27, 2,表示 11 后面紧跟着 4 个连续递增的值,27 后面跟着 2 个连续递增的值。

 

举例说明

RoaringBitmaps的设计原理是什么  第1张  

如上图,就是官网给出的一个例子,三个容器分别代表了三个数据集:

  • 第一个 1000 存储的是 62 的倍数
  • 第二个是 1-99 的数值
  • 第三个存储的是所有的偶数

上面这个例子只是说明了通过 RBM 可以对数据进行灵活分类,其它的表示形式,你不用较真。另外可能看着上面说的高 16 位存储在数组中,低 16 位存储在 Container 中,猛地一看比较迷瞪,我举个例子你就明白了。

RoaringBitmaps的设计原理是什么  第2张  
  • 821697800 对应的 16 进制数为 30FA1D08, 其中高 16 位为 30FA, 低 16 位为 1D08。

  • 先用二分查找从一级索引(即 Container Array)中找到数值为 30FA 的容器(如果该容器不存在,则新建一个),从图中我们可以看到,该容器是一个 Bitmap 容器。

  • 找到了相应的容器后,看一下低 16 位的数值 1D08,它相当于是 7432,因此在 Bitmap 中找到相应的位置,将其置为 1 即可。

看到这里,你可能仍然会有疑问 一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值。这到底是什么用意呢?

这里之所以使用 4096 这个阈值,大概因为 int 的低 16 位是 2Bit, Arrary Container 中的话就是 2Byte * 4096 = 8KB;对于 Bitmap Container 来讲,2^16 个 bit 也相当于是 8KB。基本上就是相得益彰,相对的分割点。

用过 jdk1.8 HashMap 的都知道在为了对 HashMap 做进一步优化,引入了红黑树。而当链表长度太长(默认超过 8)时,链表就转换为红黑树。我们可以利用红黑树快速增删改查的特 点,提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候,又会将红黑树转化为链 表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显。wcc 的,如果不纠结细节问题,RPM 的实现竟然跟 HashMap 设计思路这么相似?

 

操作转换过程

 

创建

在创建一个新container时,如果只插入一个元素,RBM默认会用ArrayContainer来存储。如果插入的是元素序列的话,则会先根据上面的方法计算ArrayContainer和RunContainer的空间占用大小,并选择较小的那一种进行存储。

 

查找

在查找一个元素的时候,先二分算法查找高16位的ArrayContainer,如果存在且数据量低于4096,继续二分查找特定定数据,否则使用位运算。增删改查的时间复杂度方面,BitmapContainer只涉及到位运算,显然为O(1)。而ArrayContainer和RunContainer都需要用二分查找在有序数组中定位元素,故为O(logN)。

 

转换

仔细阅读文章的话,你可能还有疑问,刚开始的时候只插入一个元素,那肯定是ArrayContainer,随着后面数据量增多了,怎么又有了后面的BitMapContainer?那是因为这个算法本身支持转换,具体请看下文解释。

当ArrayContainer的容量超过4096后,会自动转成BitmapContainer存储。4096是一个阈值,低于它时 ArrayContainer比较省空间,高于它时BitmapContainer也比较省空间。也就是说ArrayContainer存储稀疏数据,BitmapContainer存储稠密数据,可以最大限度地避免内存浪费。

RBM可以通过调用特定的API(名为optimize)比较ArrayContainer/BitmapContainer与等价的 RunContainer的内存占用情况,一旦RunContainer占用较小,就转换。也就是说,上图例子中的第二个ArrayContainer 可以转化为只有一个二元组0, 100的RunContainer,占用空间进一步下降到10200字节。

当然里面还涉及到多个Container之间的比较、合并等运算,例如:两个RBM做集合操作时,不同种类container之间位运算的处理方式,如ArrayContainer AND BitmapContainer,BitmapContainer OR RunContainer等;32位有时会不够用时需要对64位整数的支持;能够将RBM数据写到堆外,即内存映射;支持Kryo序列化等方式。这里面涉及到很多位移运算,复杂的一批,我也没搞明白。

看完上述内容,你们掌握RoaringBitmaps的设计原理是什么的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注蜗牛博客行业资讯频道,感谢各位的阅读!

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:niceseo99@gmail.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

评论

有免费节点资源,我们会通知你!加入纸飞机订阅群

×
天气预报查看日历分享网页手机扫码留言评论Telegram