Doris 中 bitmap 原理是什么？

1、Bitmap 索引结构： Bitmap 索引由连续的二进制位组成，每个位代表一个独立的数据点。对于给定的数据集，Doris 将为每个唯一的数据点创建一个位图，位图中的每一位对应数据点的存在或缺失。
2、插入数据： 当需要插入数据时，Doris 将数据映射到相应的位图中，并将对应的位设置为 1，表示该数据点存在于数据集中。
3、数据查询： 当执行查询时，Doris 使用位图算法来确定哪些数据满足查询条件。对于查询条件中的每个数据点，系统会检查相应的位图，并执行位运算（如 AND、OR、NOT 等），以快速地确定满足查询条件的数据点。
4、RoaringBitmap 的优化： Doris 使用 RoaringBitmap 对 Bitmap 索引进行优化。RoaringBitmap 将 32 位无符号整数按照高 16 位分桶，将相应的数据存储在容器（container）中。容器包括 ArrayContainer、BitmapContainer 和 RunContainer，根据数据的基数选择合适的容器类型来存储数据。
5、容器类型：
1）ArrayContainer：用于存储基数不大于 4096 的数据，使用有序数组表示，长度可动态扩展。
2）BitmapContainer：用于存储基数大于 4096 的数据，使用固定长度的位图表示，长度固定为 1024 位。
3）RunContainer：用于存储经过行程长度编码（RLE）压缩的数据，采用可变长度的无符号短整型数组。