roaring bitmap
https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
elasticsearch的分片，是基于lucene的索引基础上的，将数据分割成一个个小片段(segment)进行存储的， 然后有规律地将这些小片段进行合并。在每个片段里面，每个文档都会有一个从0到2的31次方减1之间的唯一标识。这种结构像是数组的下标一样： 它存储在任何地方，而且足以标识一个条目。文档有序地存储在片段中，而且doc ID就是文档在存储片段中的索引。所以存储片段中的第一篇文档 的doc ID为0，第二篇为1。直到最后一篇文档，它的doc ID和这个存储片段中所有文档的数量减一是一样的。
为什么这些doc ID很有用呢？倒排索引需要把文档列表中的term映射成terms,也就是传入的集合，并且我们刚刚讨论的这些doc IDs 能完美胜任工作，因为它们能被有效压缩。
上的倒排索引：传入的集合被切 分256个doc IDs的数据块中，然后每个数据块都被分离开使用delta编码和位组装压缩:lucene计算每个数据块存储编码过的deltas时所需要的最大的 位数数值。这种编码技术就是很有名的发表在文献中的 Frame Of Reference (FOR)
Roaring bitmaps
这将引导我们进入第二个，也就是lucene所依赖的编码有序整数集合的地方：过滤器缓存。过滤器缓存是一个很有名的能提升一些经常被用到的过滤器的执行速度 的技术。这是一个简单的缓存，它映射了匹配到的doc IDs的集合对应的（过滤器，存储片段）之间的关系对。但是对于倒排索引来说，这个关联就有所不同了：
因为我们仅仅缓存常用的过滤器，压缩率和倒排索引所需要的匹配文档中所有可能的term的需求并不匹配。
无论如何，我们需要缓存过滤器来保证比重新执行一次过滤器速度更快一些，所以使用一种好的数据结构很重要。
缓存过滤器被存放在内存中，投递集合被典型地存放在磁盘中。
出于这些原因，倒排索引和缓存过滤器并不需要使用相同的编码技术。
所以这里我们应该使用的是什么呢？很清楚也很重要的一点就是让有些东西变得更快：如果你的缓存过滤器比重新执行一次filter查询更慢，这就有点本末倒置了， 因为它既占用了内存又把查询变得更慢了。一个编码越复杂，它就越有可能会拖慢编码和解码，因为这将增加cpu的使用，所以让我们来看看我们能用来编码有序数字集 合的简单选择：
选项一：整型数组
可能也是最简单的选项：把doc IDs存储在数组中。这将使得迭带变得很简单，但是压缩变得很差。这种编码技术一个实体需要4个字节，这将使得稠密的过滤器 (数据比较集中，结果集比较大的)变得非常消耗内存。如果你有一个包括100M文档的存储片段，而且有一个匹配大部分文档的过滤器，缓存这个片段上一个单一的过滤器 需要大概400MB的内存。可见，我们还是需要一个对内存利用更有效的选项来解决稠密结果集的问题。
选项二: bitmap
稠密结果集中的整数集是能在bitmaps中使用的一个很好的案例。一个bitmap就是一个每个实体都只占用一个bit(位)的数组，所以它们只可能有两个值：0或者1。为了 知道一个docID是否包含在bitmap中，你需要去读取bitmap中索引的docID的值。0表示这个集合不包括这个docID，1则表示这个集合包括这个docID。迭代要求去统计 连续0的个数，这实际上是比较快的，因为cpu有专门处理这个操作的指令。如果我们与上面的选项一进行比较，在稠密结果集上的内存使用变得好上很多，因为我们现在只需要 100M 的bits也就是大概12.5MB。但是现在我们有另一个问题，在稀疏结果集上，每次匹配结果我们选项一需要4个字节，但是现在却都需要12.5MB的内存，不管实际匹配 的结果集有多大，都需要这些。
很长一段时间以来，lucene都在使用这样一种bitmaps来在内存中缓存过滤器。在lucene 5开始，我们切换到了Daniel Lemire的roaring bitmaps。可以查看Lucene- 5983(https://issues.apache.org/jira/browse/LUCENE-5983)查看更多的背景信息。
- 选项三：roaring bitmaps
Roaring bitmaps 的目标是更好地利用好上面的两个选项。开始的时候我们把投递集合按16位的最大值(65536)来切分成数据块。这也就意味着，第一个数据块可以被0到65535之间的 数值编码，第二个数据块编码范围是65536到131071。然后在每个数据块，我们使用16位最小值(16 lowest bits)来进行独立编码：如果它有少于4096个值，就会使用数组，否则的话就使用bitmap。 这个阶段需要注意的很重要的一点是按照上面说的在数组编码中我们之前一个值需要4个字节，这里数组一个值只需要2个字节的存储空间，因为数据块ID(block ID) 隐示地给了我们 16个字节的最高位。
https://cloud.tencent.com/developer/article/1452030
https://www.cnblogs.com/bonelee/p/6075547.html
