Adding

例如：添加int = 20

1. 首先，将 int 转为 bit：00000000 00000000 00000000 00010100
2. 划分最高位 MSB = 00000000 00000000 和最低位 MLB = 00000000 00010100
3. 以最高位为 key，用二分查找找到对应的桶 00000000 00000000，以最低位为 value 进行插入操作

RoaringBitmap 的桶划分如下：

按照插入时桶的疏密程度，实际存储时，RoaringBitmap 会进一步将桶区分为不同类型的容器(Container)：

1. 如果插入时，当前桶存储的数据不超过 4096 个，直接有序存储最低位为 Array，称为 ArrayContainer
   • 保存为 short[]。直接存储两字节的最低位，而不是用 Bitmap
   • 存储一个数据占用 2 b，最多存储 4096 个数据。最多占用 8kb
   • 该数组始终有序，保证可以用二分查找
2. 当前桶存储的数据个数超过 4096 个时，存储为 Bitmap，称为 BitmapContainer
   • 保存为 long[]。每个比特位用 1 来表示有，0 来表示无
   • 一个 long 提供 64 位，因此需要 1024 个 long[]
   • 该容器始终占用 $1024 * 64 bit = 8KB$

所有的容器存储为一个数组对(最高位short[] MSB, 容器地址指针Container[] ptr)中，称为 HighLowContainer

动手试一试

用下面的小工具查看在 RoaringBitmap 中添加一项数据时会发生什么