位图

在遇到有关联关系 并且 数据量很大时,会遇到一个很头疼的问题,就是要处理的数据量太大,效率很低。
比如用户画像系统、每天的活跃用户、商品适配、人际关系 等。

以用户画像系统为例,如果用户数 < 500万 并且 标签数 也不多,可以用传统的关系型数据库直接查询。
但是当数据数很多 或者 查询比较复杂时,关系型数据会效率会很低。就得想想其它办法。

  1. 优化算法
  2. 数据压缩
  3. 压缩维度展示(类似数据压缩)

(1) 优化算法

用户画像系统
用户 张三、李四
用户标签 学生、单身、90后、程序员

统计 标签是90后 程序员 的用户
mysql条件查询

统计 标签是90后 或 程序员 的用户个数
mysql 查询 取并集

当 用户数过多 (500万用户) 或 标签过多(10万标签) 时,mysql的效率很低。

假设
user_id int类型,占4字节, 1千万用户 也就是 4 * 40 000 000 byte = 160M
user_name varchar(8) 使用utf-8编码 占24字节 也就是 24 * 40 000 000 byte = 480M

tag_id int类型,占4字节,10万标签 也就是 4 * 100000 byte = 400 000 = 400K

用户 和 标签 是多对多关系,假设有一张 用户标签表, 有1千万行 10万列, 每一行需要 (user_id + 100 000 tag_id ) * 4 byte * 10 000 000 ≈ 4000G

得换一种办法。

bitmap
一个标签对应多个用户
标签id化,用户id化 (倒排索引)

每个标签 一个bitmap ,这个bitmap存储了用户信息,用户是500万,实际存储需要 2^23 bit = 2^23 / 8 byte ≈ 1MB
有 10万标签 100 000 * 1MB = 100 GB

这个算的是所有的用户和标签,实际上可以只处理需要的。可以过滤掉很多用户和标签。
用户数过滤一部分,其实 一个bitmap 实际存储会变成 2^22 bit = 2^22 / 8 byte ≈ 0.5MB
只处理常用的标签,实际常用的大概1000,1000 * 0.5MB = 5G

根据标签查对应用户,拿到结果后 并集 交集 差集

统计 标签是90后 程序员 的用户
根据标签查对应用户,拿到结果后 交集

统计 标签是90后 或 程序员 的用户个数
根据标签查对应用户,拿到结果后 并集

其它

概述

bitmap就是用一个bit位来标记某个元素对应的value,而key即是这个元素。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间

思想

32位机器上,一个整形,比如int a;在内存中占32bit,可以用对应的32个bit位来表示十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询

优点:
效率高,不许进行比较和移位
占用内存少,比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M,如果采用int数组存储,则需要38M多

缺点:
无法对存在重复的数据进行排序和查找

示例:

申请一个int型的内存空间,则有4Byte,32bit。输入 4, 2, 1, 3时:

在32位地址上加入4
URL

再加入2
URL

再加入1
URL

再加入3
URL

思想比较简单,关键是十进制和二进制bit位需要一个map映射表,把10进制映射到bit位上

假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 int a[N/32 + 1].其中a[0]在内存中占32位,依此类推:

bitmap表为:

a[0] ——> 0 - 31

a[1] ——> 32 - 63

a[2] ——> 64 - 95

a[3] ——> 96 - 127

……

下面介绍用位移将十进制数转换为对应的bit位

位移转换
(1) 求十进制数0-N对应的在数组a中的下标

index_loc = N / 32即可,index_loc即为n对应的数组下标。例如n = 76, 则loc = 76 / 32 = 2,因此76在a[2]中。

(2)求十进制数0-N对应的bit位

bit_loc = N % 32即可,例如 n = 76, bit_loc = 76 % 32 = 12

(3)利用移位0-31使得对应的32bit位为1

References

[1] 漫画:什么是Bitmap算法?-程序员小灰