如何优雅高效的在海量数据存储与查找
对于这个问题我们首先可能会想到直接去存储这40亿个数据，当然这确实是一种方法。但是我们是否考虑过这样做的后果呢？如果你的解决方案就是上面的那种方法的话，那你可能真的没有考虑过后果。所以你有必要继续往下读。
我们先不管后果是什么，现在我来带大家看一组数据，假设这40亿个数据是4个字节的unsigned int 型的数据。那嘛现在 我们要存储这40亿个数据就需要的空间为：(40 * 10^8) * 4byte = 14.9GB (注意这里所换算机制：1GB=2^10Mb=2^20kb=2^30byte,下面涉及到的计算也是采用这种方式)所以大家看见了后果就是占用了这么大的内存空间，一般计算机上的内存根本就放不下嘛，所以这还怎么干活。。。
该怎么办呢？
那么我们就来看看该怎么办？
假如我们换一种思路不直接去存储这40亿个数据，而是间接的去存储的话是不是就可以解决了？
我们采用位图（bitmap）的方式来存储这40亿个数据，用每一位来表示一个数据这样的话是不是就节省了极大的空间呢？
那我们就来计算一下这样做所占用的空间是多少？
因为这40亿个数据都是位于[0, 2^32 - 1]，所以我们要存储的0～2^32-1这个范围内的所有数据共2^32个。首先大家要明确：每一位指的是一个bit位，而1byte（1字节）是8个bit.这个大家应该都知道。那么就是：2^32bit = 2^29byte = 2^19kbyte=2^9Mb=512Mb。
512Mb 与14.9GB相比是不是远远要少呢。因此我们只需要开辟512M的内存存下2^32个数据，然后把给定的40亿个数据对应位置置为1当我们判断某一个数据是不是在给定的40亿个数据中的时候只需要查看对应位置是不是1即可。
说到这里大家是不是有些感悟呢？可能有些爱问的小伙伴就该问了，这个位操作到底该怎么存储呢？我后面会写一篇关于这个问题的，本篇文章旨在讲清楚具体的原理流程，具体的操作会另出一篇文章的。
嗯，我们继续刚才的话题，读者读到这里就会问了：上面说的都是关于bitmap的跟标题roaringBitMap有啥关系呢？其实讲上面的问题是起到一个抛砖引玉的作用，让大家先了解一下bitmap的用法，对我们学习接下来要讲到roaringBitMap有很大的帮助。
如何更加优雅高效的存储与查找？
我们继续看上面的问题，我们用位图（bitmap）的方式存储了[0, 2^32 - 1]区间上的数据，比直接存储节省了极大的空间。而且在查找的时候使用的是位操作，其时间复杂度为O(1)也是非常高效的。
但是问题又来啦：
在我们使用bitmap的时候，比如某一个软件，我们统计使用该软件的在线人数的时候，在这里用户的id为一个int型数据，当某个用户上线的时候我们就要把位图对应的位置，置为1以此来标记该用户在线。在这里假设用户的id范围在[0, 2^32 - 1]，那么根据上面的计算我们就需要开辟512M的空间来存储这个数据范围。由此看来好像也没什么问题是吧？但是，假如我们只有几个用户在线的时候，还要开辟512M的内存空间是不是就显得大材小用了呢，远远的浪费了空间（注意位图的使用是在一开始的时候就要开辟出所数据范围需要的空间，在这里是512M）。
所以针对上面空间还是无法高效的利用的问题，大佬们提出了位图压缩的方式进一步优化空间利用率，位图压缩的方式有多种，在这里我们来聊一聊roaringBitMap。
roaringBitMap的工作原理
好了现在开始进入我们今天的正题roaringBitmap了，对于学习任何一个新的东西我认为我们都应该带着一下3个问题去学习，今天学习roaringbitmap也是一样即：
- 是什么？ roaringBitmap是个什么东东？
- 什么用？ roaring有什么用处？
- 怎么用？ 怎么用roaingBitMap?
首先我们看一下roaringbitmap是什么？
roaringbitmap属于是位图的一个进化，即压缩位图，不过在roaringbitmap中不只包含bitmap这一种数据结构，而是包涵了多种存储的方式，以此来达到压缩位图的目的，具体的存储方式下面会讲到。
那么roaringbitmap有什么用呢？
在实际的业务当中我们可以使用roaringbitmap来存储用户的属性标签，增删改查这些属性标签等，以及根据这些存储的用户的标签通过并集，交集等方法来筛选出特定的用户，当然也用于其他的一些场景中这里就不一一列举了。
然后在这里写一个例，以便让大家更好的理解roaringbitmap.如下图有一个存储用户性别的roaringbitmap_sex,以及一个存储喜好唱歌的roaringbitmap_like,现在我们需要找出：性别为男并且喜欢唱歌的用户，那么我们便可以求roaringbitmap_sex和roaringbitmap_like的交集即可，结果中二进制为1的位便是我们需要找的用户。(这里的roaringbitmap_sex和roaringbitmap_like是位图，不懂可以先大致看一下就行，下面会讲的)。
roaringbitmap怎么用？
这里要说的怎么样可不只是简单的怎么调用，在这里我们要说的是roaringbitmap的底层工作原理，让大家清楚roaringbitmap底层是如何工作的，这里会从以下几方便来讲解。
roaringbitmap工作原理
- 首先，将 32bit int（无符号的）类型数据 划分为 2^16 个桶（即使用数据的前16位二进制作为桶的编号），每个桶有一个Container（可以理解为容器也可以理解为这个桶，容器和桶在这里可以理解为一个东西，只是说法不一样而已） 来存放一个数值的低16位。
- 在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中。这样说可能比较抽象不易理解，下面以一个例子来帮助大家理解。
比如我们要将31这个数放进roarigbitmap中，它的16进制为：0000001F,前16位为0000，后16为001F。所以我们先需要根据前16位的值：0，找到它对应的通的编号为0，然后根据后16位的值：31，确定这个值应该放到桶中的哪一个位置，如下图所示。
这里的小桶到底是什么大家可以先不必深究，下面会讲的。大家需要注意大桶里面的各个小桶(container)是在需要的时候才会申请开辟的，并不是一开始就全部申请的,而且大桶中小桶都是按序号有序排列在大桶里面的。
roaringbitmap中的四种小桶
在上面我们提到了大桶里装了许多的小桶（其实说container（容器）更标准），那么现在我们就来看一看小桶究竟是什么，在roaringbitmap中共有4种小桶：arraycontainer(数组容器)，bitmapcontainer(位图容器)，runcontainer(行程步长容器)，sharedcontainer(共享容器)。下面我们分别来介绍一下这4种容器。
arraycontiner
在创建一个新container时，如果只插入一个元素，RBM（roaringbitmap）默认会用ArrayContainer来存储。当ArrayContainer（其中每一个元素的类型为 short int 占两个字节,且里面的元素都是按从大到小的顺序排列的）的容量超过4096（这里是指4096个short int即8k）后，会自动转成BitmapContainer(这个所占空间始终都是8k)存储。4096这个阈值很聪明，低于它时ArrayContainer比较省空间，高于它时BitmapContainer比较省空间。也就是说ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费。下面这个图可以很清楚的看懂这种关系。
bitmapcontainer
这个容器其实就是我们最开讲的位图，只不过这里位图的位数为2^16（65536）个，也就是2^16个bit,计算下来起所占内存就是8kb。然后每一位用0，1表示这个数不存在或者存在，如下图：
runcontainer
这是一种利用步长来压缩空间的方法，我们举个例子：
比如连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被 压缩为两个二元组 11, 4, 27, 2 表示：11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值，那么原先16个字节的空间，现在只需要8个字节，是不是节省了很多空间呢。不过这种容器不常用，所以在使用的时候需要我们自行调用相关的转换函数来判断是不是需要将arraycontiner，或bitmapcontainer转换为runcontainer。
sharedcontainer
这种容器它本身是不存储数据的，只是用它来指向arraycontainer,bitmapcontainer或runcontainer,就好比指针的作用一样，这个指针可以被多个对象拥有，但是指针所指针的实质东西是被这多个对象所共享的。在我们进行roaringbitmap之间的拷贝的时候，有时并不需要将一个container拷贝多份，那么我们就可以使用sharedcontainer来指向实际的container，然后把sharedcontainer赋给多个roaringbitmap对象持有，这个roaringbitmap对象就可以根据sharedcontainer找到真正存储数据的container,这可以省去不必要的空间浪费。
这些container之间的关系可以用下面这幅图来表示：
其中的roaring_array是roaringbitmap对象，而途中的sharedcontainer则表示被多个roaring_array里面的小桶共享。
最后我们来将roaringbitmap相比于普通的bitmap的优势总结为以下几点：
内存上：
- bitmap比较适用于数据分布比较稠密的存储场景中，对于原始的Bitmap来说，若要存储uint32类型数据，这就需要2 ^ 32长度的bit数组 通过计算可以发现(2 ^ 32 / 8 bytes = 512MB), 一个普通的Bitmap需要耗费512MB的存储空间。如果我们只存储几个数据的话依然需要占用521M空间，这就有些浪费空间了，因此我们可以采用对位图进行压缩的RoaringBitMap,以此减少内存和提高效率。
性能上：
roaringbitmap除了比bitmap占用内存少之外，其并集和交集操作的速度也要比bitmap的快。原因归结为以下几点：
- 计算上的优化
对于roaringbitmap本质上是将大块的bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，roaringbitmap只需要去计算存在的一些块而不需要像bitmap那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
同时在roaringbitmap中32位长的数据，被分割成高 16 位和低 16 位，高 16 位表示块偏移，低16位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能。
2. 程序逻辑上的优化
（1）roaringbitmap维护了排好序的一级索引，以及有序的arraycontainer当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。
（2）当进行合并的arraycontainer中数据个数相差过大的时候采用基于二分查找的方法对arraycontainer求交集,避免不必要的线性合并花费的时间开销。
（3）roaingbitmap在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的roaringbitmap上即可，不需要遍历容器。
（4）roaringbitmap在合并容器的时候会先预测结果，生成对应的容器，避免不必要的容器转换操作。
