专栏首页木东居士的专栏不深入而浅出 Roaring Bitmaps 的基本原理

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

0x00 前言

位图索引被广泛用于数据库和搜索引擎中,通过利用位级并行,它们可以显著加快查询速度。但是,位图索引会占用大量的内存,因此我们会更喜欢压缩位图索引。 Roaring Bitmaps 就是一种十分优秀的压缩位图索引,后文统称 RBM。

压缩位图索引有很多种,比如基于 RLE(Run-Length Encoding,运行长度编码)的WAH (Word Aligned Hybrid Compression Scheme) 和 Concise (Compressed ‘n’ Composable Integer Set)。相比较前者, RBM 能提供更优秀的压缩性能和更快的查询效率。

0x01 用途

RBM 的用途和 Bitmap 很差不多(比如说索引),只是说从性能、空间利用率各方面更优秀了。目前 RBM 已经在很多成熟的开源大数据平台中使用,简单列几个作为参考:

  • Apache Lucene and derivative systems such as Solr and Elasticsearch,
  • Metamarkets’ Druid,
  • Apache Spark,
  • Apache Hive,
  • eBay’s Apache Kylin,
  • ……

总之 RBM 很优秀,大家都在用,学一学可能自己写代码用不到,但是对于理解这些常用的开源大数据系统没有坏处。

0x02 原理

一、英文版

原理的话先直接上一段论文的原文,两三段基本把整个 RBM 的设计思想给讲清楚了。不想看英文了可以直接跳过看后面的中文总结。

We partition the range of 32-bit indexes ([0; n)) into chunks of 216 integers sharing the same 16 most significant digits. We use specialized containers to store their 16 least significant bits. When a chunk contains no more than 4096 integers, we use a sorted array of packed 16-bit integers. When there are more than 4096 integers, we use a 216-bit bitmap. Thus, we have two types of containers: an array container for sparse chunks and a bitmap container for dense chunks. The 4096 threshold insures that at the level of the containers, each integer uses no more than 16 bits: we either use 216 bits for more than 4096 integers, using less than 16 bits/integer, or else we use exactly 16 bits/integer. The containers are stored in a dynamic array with the shared 16 most-significant bits: this serves as a first-level index. The array keeps the containers sorted by the 16 most-significant bits.We expect this first-level index to be typically small: when n = 1 000 000, it contains at most 16 entries. Thus it should often remain in the CPU cache. The containers themselves should never use much more than 8 kB.

二、主要思想

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 来存储值。

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

  1. the list of the first 1000 multiples of 62
  2. all integers [216, 216 + 100)
  3. all even numbers in [2216, 3216)

0x03 举个栗子

看完前面的还不知道在说什么?没关系,举个栗子说明就好了。现在我们要将 821697800 这个 32 bit 的整数插入 RBM 中,整个算法流程是这样的:

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

是不是很简单?然后换一个数值插入,比如说 191037,它的 16 进制的数值是 0002EA3D ,插入流程和前面的例子一样,不同的就在于, 高 16 位对应的容器是一个 Array Container,我们仍然用二分查找找到相应的位置再插入即可。

0x04 原理补充

RBM 的基本原理就这些,基于这种设计原理会有一些额外的操作要提一下。

请注意上文提到的一句话:

若一个 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 提供了相应的算法来高效地实现这些操作,比如下图是 Bitmap vs Bitmap,这里暂不再深入讨论,感兴趣的可以看一下论文原文。

0xFF 总结

好了,RBM 的大致原理就这些,不深入也没有简单代码的实现。仅能做一个入门的参考。

本文是参考论文《Better bitmap performance with Roaring bitmaps》,该论文中提到的是 Bitmap 和 Array 两种容器,算是包含了 RBM 的主要思想。然后,在另一篇论文《Consistently faster and smaller compressed bitmaps with Roaring》中会对 RBM 有更深入的探讨,并引入了一种新的容器: Run,感兴趣的童鞋可以深入看一看。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Roaring Bitmap更好的位图压缩算法

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

    smartsi
  • elasticsearch之Roaring Bitmaps的结构

    如果你是刚刚接触搜索引擎,你可能会感到奇怪,构建搜索引擎中存储块的一个很重要的原因是搜索引擎能够有效地压缩和快速解码有序的数字集合。 为什么这个很有用?你可能知...

    开发架构二三事
  • 一文读懂比BitMap有更好性能的Roaring Bitmap

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

    开发架构二三事
  • 大数据计数原理1+0=1这你都不会算(八)No.60

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

    大蕉
  • 用了 Elasticsearch 后,查询起飞了!

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

    杰哥的IT之旅
  • ElasticSearch 查询的秘密

    https://neway6655.github.io/elasticsearch/2015/09/11/elasticsearch-study-notes.h...

    JAVA葵花宝典
  • 深入JavaWeb技术世界15:深入浅出Mybatis基本原理

    本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

    Java技术江湖
  • Elasticsearch 如何做到快速检索 - 倒排索引的秘密

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

    肉眼品世界
  • Elasticsearch 如何做到快速检索?和 MySQL 索引完全不同!

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

    孙玄@奈学教育
  • Elasticsearch 为什么能做到快速检索?— 倒排索引的秘密

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

    架构师修炼
  • Elasticsearch 为什么能做到快速检索?

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

    kubernetes中文社区
  • 深入浅出介绍:GAN的基本原理与入门应用!

    如果你觉得好的话,不妨分享到朋友圈。 摘要:生成对抗网络(GAN)是一类在无监督学习中使用的神经网络,其有助于解决按文本生成图像、提高图片分辨率、药物匹配、检索...

    IT派
  • Apache Druid 底层的数据存储

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

    码哥字节
  • Apache Druid 底层存储设计(列存储与全文检索)

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

    码哥字节
  • Clickhouse在大数据分析平台-留存分析上的应用

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

    腾讯云大数据
  • Clickhouse在大数据分析平台-留存分析上的应用

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

    腾讯QQ大数据
  • 深入搜索之结构化搜索

    结构化搜索是指针对具有内在结构的数据进行检索的过程。比如日期、时间和数字都是结构化的,它们有精确的格式。文本也是可以 格式化的,比如彩色笔的颜色可以有red、g...

    开发架构二三事
  • 详解Elasticsearch 的性能优化

    Elasticsearch(后文简称 ES)的基础是 Lucene,所有的索引和文档数据是存储在本地的磁盘中,具体的路径可在ES 的配置文件../config/...

    烂猪皮
  • 基于源码深入浅出来理解k8s的services工作原理

    k8s 中的 services 就是一组同label类型 pod 的服务抽象,为服务提供了LB和反向代理的能力,集群中表示一个微服务的概念。kube-proxy...

    机械视角

扫码关注云+社区

领取腾讯云代金券