BitSet索引学习

近我们在使用druid的过程中使用了BitSet索引。这个邮件是我之前总结的JDK的BitSet实现。非常巧妙。我在这里可以进一步分享一下。

目录

一.总结一下JDK的BitSet

二.Roaring BitSet

三.留些思考问题

四.我的要求

一.总结一下JDK的BitSet

1.long是8个字节，也就是64bit。64个bit可以保存64个数字。

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 表示0

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 表示1

依次类推

2.我们可以将数字[0,n)划分成为

[0,64),[64,2*64),[2*64,3*64).....

这样使用一个long[]数组就能够表示是否存在某个数字。

比如 8 我们可以放在long[0]这个long，使用bit

00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 表示8

二.Roaring BitSet

roaring bitset 是JDK BitSet的升级版本。他考虑了数据的稀疏和稠密这两种情况，采用了灵活的数据结构，来降低内存使用。同时，他也考虑了CPU的缓存，使用佳的内存大小来存储数据。这两方面的优化，让BitSet存储下降，同时运算能力提升。

1.short是2个字节，也就是16bit，long是8个字节，也就是64bit。

2.我们可以将数字[0,n)划分成为

[0,2^16),[2^16,2*2^16),[2*2^16,3*2^16)...

3.对于一个32bit的数字，我们可以将其分为高16位和后16位两部分。相同高位的数据保存在同一个container里面。

4.container会根据数据的稀疏还是稠密选择不一样的数据结构。

当相同高位数据对应的container保存的数据少于4096个时，container采用 short[]数组进行数据的保存，当数据超过4096后采用BitMapContainer进行保存。

bitmapcontainer的数据结构是 long[]数据，他的长度是固定的，1024。1024个long就能保存1024*64个关键字，其大小正好是8 kb。

当同一个高16位key对应的数据少于4096时

当保存的数据超过4096时

三.留些思考问题

1.当存储1~65536个数据时，是JDK的BitSet省内存还是Roaring BitSet省内存？请评估内存占用量。

2.当存储1~10000000000个数据中的随机数据，随机数据取1000000个时，JDK BitSet和Roaring BitSet那个性能更佳？请评估内存占用量。

这些问题需要思考，我还要求要对RLE类型BitMap有深入理解。我不希望只知道写的慢，或者程序告诉我们的，这个数据结构存了什么数据，然后他占用了多少内存。我希望我们能算出来。

四.我的要求

我们是在做大数据。我们要对内存敏感。同时我们要对数据的规律敏感。我们必须要掌握核心技能，才能做到了然于胸。