Bitmap
1.位图
用一个bit位来标记一个数字,第N位(从0开始)的bit代表着整数N,1既存在,0既不存在.
2.位图的应用
位图经常用来处理海量数据的压缩,并对其进行排序,去重,查询,并集,交集等操作.
3.位图存在的问题
大小根据最大位决定,也就是说如果里面只存一个数字40亿,那么仍然需要476MB的内存空间去存储,所以只有当数据较为密集的时候使用位图才有优势.
为了解决位图在稀疏数据下的问题,目前有多种压缩方案以减少内存提高效率:WAH、EWAH、CONCISE、RoaringBitmap等.前三种都是采用行程长度编码(Run-length-encoding)进行压缩,RoaringBitmap则是在压缩上更进一步,并且兼顾了性能.
RoaringBitmap
实现思路
RoaringBitmap处理的是int型整数,RoaringBitmap将一个32位的int拆分为高低16位分开处理,高16位作为索引,低16位则实际存储数据.
RoaringBitmap按索引将数据分块存放,每个块中的整数共享高16位,第1个块包含了[0,2^16), 它们的高16位均为0,第2个块包含了[2^16,2x2^16),它们的高16位均为1...以此类推,每个RoaringBitmap中最多可以有2^16个块,每个块中最多可以存放2^16个数据
若不是很理解可以看下面这张图
RoaringBitmap的数据结构
RoaringArray:每个RoaringBitmap都包含了一个RoaringArray(highLowContainer),主要有几个重要属性
keys:short数组,用于存储高16位作为索引
values:Container数组,用来存储低16位数据
size:用来记录当前RBM包含的key-value有效数量
注意:keys数组和values数组是一一对应的,切keys永远保证有序,这是为了之后索引的二分查找.
Container:用于存储低16位的数据,根据数据量以及疏密程度分为一下3个容器
1.ArrayContainer
//ArrayContainer允许的最大数据量
static final int DEFAULT_MAX_SIZE = 4096;// containers with DEFAULT_MAX_SZE or less integers
// should be ArrayContainers
//记录基数
protected int cardinality = 0;
//用short数组存储数据
short[] content;ArrayContainer采用简单的short数组存储低16位数据,content使用有序且不重复,方便二分查找.
可以看出,ArrayContainer并没有采用任何的压缩算法,只是简单的讲低16存储在short[]中,所以ArrayContainer占用的内存空间大小和存储的数据量呈线性关系:short为2字节,因此n个数据位2n字节.随着数据量的增大,ArrayContainer占用的内存空间组件增多,且由于是二分查找,时间复杂度为O(logn),查找效率也会大打折扣,因此ArrayContainer规定最大数据量是4096既8kb.
2.BitmapContainer
//最大容量
protected static final int MAX_CAPACITY = 1 << 16;
//用一个定长的long数组按bit存储数据
final long[] bitmap;
//记录基数
int cardinality;BitmapContainer采用long数组存储低16为数据,这就是一个未压缩的普通位图,每一个bit位置代表一个数字.上面提到Container最多可以处理2^16个数字,基于位图的原理,就需要12^16个bit,每个long是8字节64bit,所以需要12^16/64=1024个long
BitmapContainer构造方法会初始化一个长度为1024的long数组,因此BitmapContainer无论是存多少个数据,都始终占据着8kb的内存空间.同样也就解释了为什么ArrayContainer数据量的最大阈值是4096,由于直接进行位运算,该容器的时间复杂度为O(1)
3.RunContainer
private short[] valueslength;// we interleave values and lengths, so
// that if you have the values 11,12,13,14,15, you store that as 11,4 where 4 means that beyond 11
// itself, there are
// 4 contiguous values that follows.
// Other example: e.g., 1, 10, 20,0, 31,2 would be a concise representation of 1, 2, ..., 11, 20,
// 31, 32, 33
int nbrruns = 0;// how many runs, this number should fit in 16 bits.RunContainer是基于之前提到的RLE算法进行压缩的,主要解决了大量连续数据的问题.
举例说明：3,4,5,10,20,21,22,23这样一组数据会被优化成3,2,10,0,20,3，原理很简单，就是记录初始数字以及连续的数量，并把压缩后的数据记录在short数组中
显而易见，这种压缩方式对于数据的疏密程度非常敏感，举两个最极端的例子：如果这个Container中所有数据都是连续的，也就是[0,1,2.....65535]，压缩后为0,65535，即2个short，4字节。若这个Container中所有数据都是间断的（都是偶数或奇数），也就是[0,2,4,6....65532,65534]，压缩后为0,0,2,0.....65534,0，这不仅没有压缩反而膨胀了一倍，65536个short，即128kb
因此是否选择RunContainer是需要判断的，RBM提供了一个转化方法runOptimize()用于对比和其他两种Container的空间大小，若占据优势则会进行转化
