专栏首页SmartSiRoaring Bitmap更好的位图压缩算法

Roaring Bitmap更好的位图压缩算法

1. 概述

Bitsets(也称为Bitmaps)通常用作快速数据结构。不幸的是,他们可能会占用太多内存。为了降低内存的使用,我们经常会使用压缩的位图。

Roaring Bitmaps 是一种压缩的位图,要优于常规的压缩位图,例如 WAH,EWAH 或者 Concise。在某些情况下,可以比它们快几百倍,并且通常提供更好的压缩。

Roaring Bitmaps 已经被很多重要系统使用:

几乎所有流行的编程语言(Java,C,C ++,Go,C#,Rust,Python ……)都提供了 Roaring Bitmaps。

2. 主要思想

我们以存放 Integer 值的 Bitmap 来举例,RBM 把一个 32 位的 Integer 划分为高 16 位和低 16 位,通过高 16 位找到该数据存储在哪个桶中(高 16 位可以划分 2^16 个桶),把剩余的低 16 位放入该桶对应的 Container 中。

每个桶都有对应的 Container,不同的 Container 存储方式不同。依据不同的场景,主要有 2 种不同的 Container,分别是 Array Container 和 Bitmap Container。Array Container 存放稀疏的数据,Bitmap Container 存放稠密的数据。若一个 Container 里面的元素数量小于 4096,使用 Array Container 来存储。当 Array Container 超过最大容量 4096 时,会转换为 Bitmap Container。

3. Array Container

Array Container 是 Roaring Bitmap 初始化默认的 Container。Array Container 适合存放稀疏的数据,其内部数据结构是一个有序的 Short 数组。数组初始容量为 4,数组最大容量为 4096,所以 Array Container 是动态变化的,当容量不够时,需要扩容,并且当超过最大容量 4096 时,就会转换为 Bitmap Container。由于数组是有序的,存储和查询时都可以通过二分查找快速定位其在数组中的位置。

后面会讲解为什么超过最大容量 4096 时变更 Container 类型。

下面我们具体看一下数据如何被存储的,例如,0x00020032(十进制131122)放入一个 RBM 的过程如下图所示:

0x00020032 的前 16 位是 0002,找到对应的桶 0x0002。在桶对应的 Container 中存储低 16 位,因为 Container 元素个数不足 4096,因此是一个 Array Container。低 16 位为 0032(十进制为50), 在 Array Container 中二分查找找到相应的位置插入即可(如上图50的位置)。

相较于原始的 Bitmap 需要占用 16K (131122/8/1024) 内存来存储这个数,而这种存储实际只占用了4B(桶中占 2 B,Container中占 2 B,不考虑数组的初始容量)。

4. Bitmap Container

第二种 Container 是 Bitmap Container。它的数据结构是一个 Long 数组,数组容量恒定为 1024,和上文的 Array Container 不同,Array Container 是一个动态扩容的数组。Bitmap Container 不用像 Array Container 那样需要二分查找定位位置,而是可以直接通过下标直接寻址。

由于每个 Bitmap Container 需要处理低 16 位数据,也就是需要使用 Bitmap 来存储需要 8192 B(2^16/8), 而一个 Long 值占 8 个 B,所以数组大小为 1024。因此一个 Bitmap Container 固定占用内存 8 KB。

下面我们具体看一下数据如何被存储的,例如,0xFFFF3ACB(十进制4294916811)放入一个 RBM 的过程如下图所示:

0xFFFF3ACB 的前 16 位是 FFFF,找到对应的桶 0xFFFF。在桶对应的 Container 中存储低 16 位,因为 Container 中元素个数已经超过 4096,因此是一个 Bitmap Container。低 16 位为 3ACB(十进制为15051), 因此在 Bitmap Container 中通过下标直接寻址找到相应的位置,将其置为 1 即可(如上图15051的位置)。

可以看到元素个数达到 4096 之前,Array Container 占用的空间比 Bitmap Container 的少,当 Array Container 中元素到 4096 个时,正好等于 Bitmap Container 所占用的 8 KB。当元素个数超过了 4096 时,Array Container 所占用的空间还是继续线性增长,而 Bitmap Container 的内存空间并不会增长,始终还是占用 8 KB,与数据量无关。所以当 Array Container 超过最大容量 4096 会转换为 Bitmap Container。

参考: 不深入而浅出 Roaring Bitmaps 的基本原理

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:http://smartsi.club/复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 一文读懂比BitMap有更好性能的Roaring Bitmap

    1.什么是bitmap?为什么使用bitmap?Roaring bitmap与其他bitmap编码技术相比有哪些优势?2.Roaring bitmap将32位无...

    开发架构二三事
  • 不深入而浅出 Roaring Bitmaps 的基本原理

    木东居士
  • ElasticSearch系列之索引机制学习笔记

    在上一章的学习,我们对ElasticSearch有了比较清晰的理解,然后本博客继续学习ES中比较重要的核心原理和具体实现。相对于MySQL的索引机制,大部分是基...

    SmileNicky
  • Redis 精确去重计数 —— 咆哮位图

    如果要统计一篇文章的阅读量,可以直接使用 Redis 的 incr 指令来完成。如果要求阅读量必须按用户去重,那就可以使用 set 来记录阅读了这篇文章的所有用...

    老钱
  • Elasticsearch 为什么能做到快速检索?

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    kubernetes中文社区
  • 大数据计数原理1+0=1这你都不会算(八)No.60

    今天跟小伙伴们聊聊另外一个统计算法, Roaring BitMaps。 这个该怎么翻译呢??咆哮的位图?s?我翻译不出来,但是小蕉头一歪,就给它起了一个狂拽酷霸...

    大蕉
  • 干掉 SQL 中的 like,我用 es 后,小姐姐们都说好快!

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    终码一生
  • Elasticsearch 如何做到快速检索?和 MySQL 索引完全不同!

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    孙玄@奈学教育
  • Elasticsearch 倒排索引的秘密

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    终码一生
  • Elasticsearch 为什么能做到快速检索?— 倒排索引的秘密

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    架构师修炼
  • 用了 Elasticsearch 后,查询起飞了!

    本文不会关注 ES 里面的分布式技术、相关 API 的使用,而是专注分享下“ES 如何快速检索”这个主题上面。这个也是我在学习之前对 ES 最感兴趣的部分。

    杰哥的IT之旅
  • Clickhouse在大数据分析平台-留存分析上的应用

    你可能听说过Growingio、神策等数据分析平台,所在部门也在构建自己的大数据分析平台MVP(地址:http://mvp.wsd.com),本文主要介绍实现留...

    腾讯云大数据
  • 从一道高大上的面试题来学习位图算法BitMap

    今天我偶然刷到了一篇文章,“华为二面:一个文件里面有5亿个数据,一行一个,没有重复的,进行排序”。不知道又是哪个无良媒体瞎起的标题,夺人眼球。

    秃头哥编程
  • Elasticsearch 如何做到快速检索 - 倒排索引的秘密

    最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一...

    肉眼品世界
  • Clickhouse在大数据分析平台-留存分析上的应用

    导语 | 本文实践了对于千万级别的用户,操作总数达万级别,每日几十亿操作流水的留存分析工具秒级别查询的数据构建方案。同时,除了留存分析,对于用户群分析,事件分...

    腾讯QQ大数据
  • Apache Druid 底层存储设计(列存储与全文检索)

    了解过 Apache Druid 或之前看过本系列前期文章的同学应该都知道 Druid 兼具数据仓库,全文检索和时间序列的能力。那么为什么其可以具有这些能力,D...

    码哥字节
  • Apache Druid 底层的数据存储

    了解过 Apache Druid 或之前看过本系列前期文章的同学应该都知道 Druid 兼具数据仓库,全文检索和时间序列的能力。那么为什么其可以具有这些能力,D...

    码哥字节
  • bitmap算法的PHP实现,快速去重排序,数据压缩储存

    因为电路的逻辑只有0和1两个状态,这里的0和1并不是数字的0和1,0和1是表示两种不同的状态,0表示低电平,1表示高电平。因为计算机是由无数个逻辑电路组成的,只...

    宣言言言

扫码关注腾讯云开发者

领取腾讯云代金券