本文永久链接– https://tonybai.com/2023/02/01/serialize-roaring-bitmap-to-json近期在实现一个数据结构时使用到了位图索引(bitmap index),本文就来粗浅聊聊位图(bitmap)。一. 什么是bitmap位图索引使用位数组(bit array,也有叫bitset的,通常被称为位图(bitmap),以下均使用bitmap这个名称)实现。一个bitmap是一个从某个域(通常是一个整数范围)到集合{0,1}中的值的映射:映射:f(x) -> {0, 1}, x是[0, n)的集合中的元素。以n=8的集合{1, 2, 5}为例:f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 0
f(4) = 0
f(5) = 1
f(6) = 0
f(7) = 0如果用bit来表示映射后得到的值,我们将得到一个二进制数0b00100110(最右侧的bit位上的值指示集合中数值0的存在性),这样我们就可以用一个字节大小的数值0b00100110来表示{1, 2, 5}这个集合中各个位置的数值的存在性了。我们看到相比于使用一个byte数组来表示{1, 2, 5}这个集合(即便是8个数值,也至少要8x8=64个字节),bitmap无疑具有更高的空间利用率。同时,通过bitmap的与、或、异或等操作,我们可以很容
...
继续阅读
(111)