位图
在遇到有关联关系 并且 数据量很大时，会遇到一个很头疼的问题，就是要处理的数据量太大，效率很低。
比如用户画像系统、每天的活跃用户、商品适配、人际关系 等。
以用户画像系统为例，如果用户数 < 500万 并且 标签数 也不多，可以用传统的关系型数据库直接查询。
但是当数据数很多 或者 查询比较复杂时，关系型数据会效率会很低。就得想想其它办法。
- 优化算法
- 数据压缩
- 压缩维度展示(类似数据压缩)
(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
再加入2
再加入1
再加入3
思想比较简单，关键是十进制和二进制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