Bitmap算法简介

“瓶颈存在于技术的每个角落,突破瓶颈的方法不在技术本身的升级,而往往是在思考的维度提升。” ———— 基德·托可列夫(查无此人)

即将要介绍的内容

bitmap 在这里不是位图的意思,在计算领域,它是一种将某些阈值映射为bit的做法。
接下来内容与存储和运算有关。

bit(位)

计算机系统里的 1 bit(位)可以存储0或1,可以表达两个状态,或者说能对应两个值。
现实中我们用很多个bits来表达“更多”的数据,比如数字“8”,需要4个bits,即“1000”。
以上是对bit的复习。

没有Bitmap的世界

假设统计前端团队每周交博客的人,情况如下:
UUID | Member | Submited | Date
111 | HJW | yes | 12-08
112 | CN | yes | 12-08
113 | YP | yes | 12-08
114 | LKT | no | 12-08
115 | WL | no | 12-08
116 | MZG | yes | 12-08

那么记录12-08这一天登录的用户可以采用这样的存储方法,记录每天登录用户的UUID(唯一用户ID):
“12-08”: [111, 112, 113, 114, 115, 116 …]
相当于每天登录记录需要存储 n 个用户 乘以 UUID长度。

使用Bitmap

换个维度思考,首先这n个用户是可数的,我们构建顺序组,让他们排排坐:
UUID -> 111 | 112 | 113 | 114 | 115 | 116 …
然后按此顺序,创建一个由n个位的数据项
“12-08” -> 1 1 1 0 0 1 …
111001…… 相当于一个n bit的数据,相对于上面提到的通过ID数组来记录,bitmap记录数据的变化很大,从存储来看,大大减少了字节空间占用。
到底节省了多少呢?这取决于数据量,数据量越大,节省的越多。

思考过程

将数据放入一个二维表是常规的思维。而bitmap给了一个全新的思路。
因为采用映射关系,数据逻辑关系被降维。
具体怎么体现呢:
这里我引用一个炒鸡可爱的例子:
第一步,建立个简单的映射关系:

第二步,由ID对应到每条数据的多个属性,转变为每个属性对应到多个ID

此时,维度降低了。从中筛选几个维度,其中一目了然:
是程序员的,对应ID是1、2
00后呢,对应ID是3

Bitmap算法

Bitmap算法是将位运算运用到对数据的逻辑处理。
AND/OR/XOR/NOT,很熟悉吧,曾经的与或非(当然还有亦或)。

还是用上面的例子。
如何查找使用苹果手机的程序员用户?

使用逻辑”与”关系就搞定了!

那么如果是查找所有男性或者00后的用户呢?那么只需要用或运算:
男性用户 | 00后用户 就能得到答案。

Bitmap性能

Bitmap的存储方式已经决定了其存储空间上的优点,大量计算时,系统的I/O消耗和CPU运算都会影响计算性能。
而Bitmap做到了。
首先,采用gzip等压缩技术,可以对Bitmap文件进行压缩,运算之前再解压,省去了中间加载过程的I/O消耗(通常跨系统的输入输出对资源消耗巨大)。
另外,还有一种专门对Bitmap进行压缩的技术RLE(Run Length Encoding)

Bitmap分布式计算

利用代数原理,Bitmap实现分布式计算成为可能。
集合关系如下 (A∩B)∪C = (A∪C)∩(B∪C)
当A、B数据量都非常庞大时,可以分别于C进行运算,分别得到的结果再进行运算。
应用在分布式系统中,复杂的多维交叉运算,可以划分成小的计算单元,运算之后再汇总,就达到了分布计算的效果。

最后再借用一张图,

参考

漫画:什么是bitmap算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注