RoaringFormatSpec RoaringFormatSpec

roaring bitmap存储格式规范通用格式
文章图片
image.png 说明：

有一个初始化“ cookie头”，它使我们能够识别出位流是一个roaring bitmap，并收集了一些少量的信息。
cookie头后面是描述容器的“描述性头”。
根据cookie头内容，有一个偏移头，可以快速随机访问存储的容器。
头后面是容器，一个一个地序列化。

在整个过程中，我们使用以下常量：
SERIAL_COOKIE_NO_RUNCONTAINER = 12346，
SERIAL_COOKIE = 12347，
NO_OFFSET_THRESHOLD = 4
cookie头、描述头、偏移头、容器存储说明 cookie头

CooKie头大小可以是32位或64位。
如果前32位采用值SERIAL_COOKIE_NO_RUNCONTAINER，则Roaring位图中的任何容器部分都不能为“运行”类型（仅允许使用数组和位集容器）。当cookie具有此特定值时，接下来的32位用于存储表示容器数量的整数。如果位图为空（即它没有容器），则应选择此Cookie头。
32位cookie的低16有效位的值为SERIAL_COOKIE时，其高16位来存储容器数量（具体值是容器数量-1，即如果将cookie右移16并加1，则得到的容器数-size），在最初的32位之后，我们将存储（size + 7）/ 8个字节，以指示每个容器是否是运行容器（位设置为1）（不是位）。第一个字节的第一位对应于第一个存储的容器，依此类推。

扫描cookie头之后，我们知道位图中有多少个容器。
描述头
Cookie标头后跟一个描述性标头。对于每个容器，我们将键（16个最高有效位）与基数减1一起存储。
扫描描述性标头后，我们知道每个容器的类型。的确，如果cookie的值为SERIAL_COOKIE，那么我们有一个位集告诉我们哪些容器是运行容器；否则，我们知道没有运行容器。对于不是运行容器的容器，则使用基数来确定类型：基数最大为4096表示数组容器，而基数大于4096表示位集容器。
偏移头
当且仅当其中之一为真时，我们使用每个4字节存储从cookie头开始的每个容器的位置（字节位单位）。

Cookie的值为SERIAL_COOKIE_NO_RUNCONTAINER
Cookie的值为SERIAL_COOKIE，并且至少有NO_OFFSET_THRESHOLD个容器，

容器存储
容器挨个存储。
对于数组容器，我们存储是该数组容器下的16位无符号整数值的排序列表。因此，如果数组容器中有x个值，则使用2x个字节。
bitmap容器是固定8KB存储，用64位字长（long）数组集合表示位集。因此，如果存在值j，则单词j / 64（从0开始）将其（j％64）最低有效位设置为1（从位0开始）。
【RoaringFormatSpec】运行容器是用16位整数表示指示游程个数，然后是每个游程是由一对16位数值组成，游程是不重叠、且有序的。因此，具有x个游程的运行容器将使用2 + 4 x个字节。每对16位值都包含游程的起始索引，后跟游程长度减去1。也就是说，我们对值和长度进行交织存储。如果您具有值11,12,13,14,15，您将其存储为11,4，其中4表示除11本身外，后面还有4个连续值。其他示例：例如1,10，20,0，31,2将是1，2，...，11，20，31，32，33的简洁表示