Redis 基础 -- 位图（bitmap）数据结构和 bitmap的常用命令（SETBIT、GETBIT、BITCOUNT、BITPOS、BITOP、BITFIELD）

Redis的位图（bitmap）是由多个二进制位组成的数组，数组中的每个二进制位都有与之对应的偏移量（也称索引），用户通过这些偏移量可以对位图中指定的一个或多个二进制位进行操作。

CodeJiao

4895人浏览 · 2022-05-04 15:06:54

CodeJiao · 2022-05-04 15:06:54 发布

文章目录

1. 位图（bitmap）

1. 位图（bitmap）

下图展示了一个包含8个二进制位的位图示例，这个位图存储的值为10010100。
在这里插入图片描述

1.1 SETBIT：设置二进制位的值

通过使用SETBIT命令，用户可以为位图指定偏移量上的二进制位设置值。

在这里插入图片描述 SETBIT命令在对二进制位进行设置之后，将返回二进制位被设置之前的旧值作为结果。

将位图bitmap001的值设置成10010100：
在这里插入图片描述
下图展示了以上3个命令的执行过程：

1.1.1 位图的扩展

当用户执行SETBIT命令尝试对一个位图进行设置的时候，如果位图不存在，或者位图当前的大小无法满足用户想要执行的设置操作，那么Redis将对被设置的位图进行扩展，使得位图可以满足用户的设置请求。

因为Redis对位图的扩展操作是以字节为单位进行的，所以扩展之后的位图包含的二进制位数量可能会比用户要求的稍微多一些，并且在扩展位图的同时，Redis还会将所有未被设置的二进制位的值初始化为0。

如果用户执行以下命令，对尚未存在的位图bitmap002在偏移量10之上的二进制位进行设置：
在这里插入图片描述
那么Redis创建出的位图并不会只有11个二进制位，而是有两个字节共16个二进制位，如下图所示。

从这个图我们也可以看到，除了偏移量为10的二进制位之外，其他所有未被设置的二进制位都被初始化成了0。

1.1.2 偏移量只能为正数

与一些Redis命令可以使用负数作为偏移量的做法不同，SETBIT命令只能使用正数偏移量，尝试输入负数作为偏移量将引发一个错误：
在这里插入图片描述

1.1.3 时间复杂度说明

复杂度：O(1)。

1.2 GETBIT：获取二进制位的值

使用GETBIT命令，用户可以获取位图指定偏移量上的二进制位的值。

在这里插入图片描述

对于值为10010100的位图bitmap001来说，可以通过执行以下命令，分别获取它在偏移量0、偏移量3、偏移量5以及偏移量7上的二进制位的值：
在这里插入图片描述
下图展示了这4个GETBIT命令对bitmap001进行取值的过程。

如果用户输入的偏移量超过了位图目前拥有的最大偏移量，那么GETBIT命令将返回0作为结果。
在这里插入图片描述

复杂度：O(1)。

1.3 BITCOUNT：统计被设置的二进制位数量

用户可以通过执行BITCOUNT命令统计位图中值为1的二进制位数量。

在这里插入图片描述

默认统计整个位图，可选参数 start 和 end 可以指定被统计的字节范围（包含 start 和 end）。

对于值为10010100的位图bitmap001，可以通过执行以下命令来统计它有多少个二进制位被设置成了1：
在这里插入图片描述
而对于值为0000000000100000的位图bitmap002，可以通过执行以下命令来统计它有多少个二进制位被设置成了1:

1.3.1 只统计位图指定字节范围内的二进制位

在默认情况下，BITCOUNT命令将对位图包含的所有字节中的二进制位进行统计，但在有需要的情况下，用户也可以通过可选的start参数和end参数，让BITCOUNT只对指定字节范围内的二进制位进行统计。

注意start参数和end参数与本章之前介绍的SETBIT命令和GETBIT命令的offset参数并不相同，这两个参数是用来指定字节偏移量而不是二进制位偏移量的。位图的字节偏移量与Redis其他数据结构的偏移量一样，都是从0开始的：位图第一个字节的偏移量为0，第二个字节的偏移量为1，第三个字节的偏移量为2，以此类推。

不要把BITCOUNT的字节偏移量当作二进制位偏移量

对于下面的位图来说：
在这里插入图片描述
统计出它的第一个字节里面有多少个二进制位被设置成了1：

在这里插入图片描述
统计出它的第二个字节里面有多少个二进制位被设置成了1：

统计出它的前二个字节里面有多少个二进制位被设置成了1：

1.3.2 使用负数偏移量定义统计范围

负数索引可以参考这个文章

BITCOUNT命令的start参数和end参数的值除了可以是正数之外，还可以是负数。以下是一些使用负数偏移量对位图bitmap003的指定字节进行统计的例子：
在这里插入图片描述

1.3.3 时间复杂度说明

复杂度：O(N)，其中N为被统计字节的数量。

1.4 BITPOS：查找第一个指定的二进制位值

用户可以通过执行BITPOS命令，在位图中查找第一个被设置为指定值的二进制位（只能是0或者1），并返回这个二进制位的偏移量。

在这里插入图片描述

对于下面的位图来说：
在这里插入图片描述
比如，通过执行以下命令，我们可以知道位图bitmap003第一个被设置为1的二进制位所在的偏移量：

而执行以下命令则可以知道bitmap003第一个被设置为0的二进制位所在的偏移量：

下图展示了以上两个命令的执行过程：
在这里插入图片描述

1.4.1 只在指定的字节范围内进行查找

在默认情况下，BITPOS命令的查找范围将覆盖位图包含的所有二进制位，但在有需要的情况下，用户也可以通过可选的start参数和end参数，让BITPOS命令只在指定字节范围内的二进制位中进行查找。可以参考上面的BITCOUNT。

对于下面的位图来说：
在这里插入图片描述
如果我们想要在位图bitmap003的第二个字节中找到第一个值为1的二进制位所处的偏移量，那么可以执行以下命令：

如果我们想要在位图bitmap003的第二个字节中找到第一个值为0的二进制位所处的偏移量，那么可以执行以下命令：
在这里插入图片描述
如果我们想要在位图bitmap003的前2个字节中找到第一个值为0的二进制位所处的偏移量，那么可以执行以下命令：

1.4.2 使用负数偏移量定义查找范围

与BITCOUNT命令一样，BITPOS命令的start参数和end参数也可以是负数。

以下代码就展示了如何在位图bitmap003的倒数第一个字节中，查找第一个值为0的二进制位：
在这里插入图片描述下图展示了这个命令的执行图示，以及它在执行时的查找范围。

1.4.3 边界情况处理

当用户尝试对一个不存在的位图或者一个所有位都被设置成了0的位图中查找值为1的二进制位时，BITPOS命令将返回-1作为结果。
在这里插入图片描述
如果用户在一个所有位都被设置成1的位图中查找值为0的二进制位，那么BITPOS命令将返回位图最大偏移量加上1作为结果。

举个例子，如果我们在一个包含8个二进制位，并且所有二进制位都被设置成1的位图bitmap-8bits-all-1中查找值为0的二进制位，那么BITPOS命令将返回以下结果：
在这里插入图片描述
这个BITPOS命令之所以会返回8，是因为它在对位图中偏移量从0到7的8个二进制位进行检查之后，都没有找到值为0的二进制位，于是它继续移动指针，尝试去检查偏移量为8的二进制位，但是由于偏移量8已经超出了位图的有效偏移量范围，而Redis又会把位图中不存在的二进制位的值看作0，所以BITPOS命令最后就把偏移量8作为结果返回给用户。

1.4.4 时间复杂度说明

复杂度：O(N)，其中N为查找涉及的字节数量。

1.5 BITOP：执行二进制位运算

用户可以通过BITOP命令，对一个或多个位图执行指定的二进制位运算，并将运算结果存储到指定的键中。

在这里插入图片描述

operation参数的值可以是AND、OR、XOR、NOT中的任意一个，这4个值分别对应逻辑与、逻辑或、逻辑异或和逻辑非4种运算，其中AND、OR、XOR这3种运算允许用户使用任意数量的位图作为输入，而NOT运算只允许使用一个位图作为输入。BITOP命令在将计算结果存储到指定键中之后，会返回被存储位图的字节长度。

对于位图bitmap001、bitmap002和bitmap003：
在这里插入图片描述

在这里插入图片描述

通过执行以下命令，我们可以对位图bitmap001、bitmap002和bitmap003执行逻辑与运算（先对bitmap001、bitmap002进行与运算，然后用他们的结果对bitmap003进行与运算，后同），并将结果存储到键and_result中：
在这里插入图片描述
而执行以下命令则可以将bitmap001、bitmap002和bitmap003的逻辑或运算结果和逻辑异或运算结果分别存储到指定的键中：

最后，通过执行以下命令，我们可以计算出bitmap001的逻辑非结果，并将它存储到not_result键中：
在这里插入图片描述

1.5.1 处理不同长度的位图

当BITOP命令在对两个长度不同的位图执行运算时，会将长度较短的那个位图中不存在的二进制位的值看作0。

1.5.2 时间复杂度说明

复杂度：O(N)，其中N为计算涉及的字节总数量。

1.6 BITFIELD：在位图中存储整数值

BITFIELD命令允许用户在位图中的任意区域（field）存储指定长度的整数值，并对这些整数值执行加法或减法操作。BITFIELD命令支持SET、GET、INCRBY、OVERFLOW这4个子命令，接下来将分别介绍这些子命令。

在这里插入图片描述

1.6.1 根据偏移量对区域进行设置

通过使用BITFIELD命令的SET子命令，用户可以在位图的指定偏移量offset上设置一个type类型的整数值value：
在这里插入图片描述

offset参数用于指定设置的起始偏移量。这个偏移量从0开始计算，偏移量为0表示设置从位图的第1个二进制位开始。如果被设置的值长度不止一位，那么设置将自动延伸至之后的二进制位。
type参数用于指定被设置值的类型，这个参数的值需要以i或者u为前缀，后跟被设置值的位长度，其中i表示被设置的值为有符号整数，而u则表示被设置的值为无符号整数。比如i8表示被设置的值为有符号8位整数，而u16则表示被设置的值为无符号16位整数，诸如此类。BITFIELD的各个子命令目前最大能够对64位长的有符号整数（i64）和63位长的无符号整数（u63）进行操作。
value参数用于指定被设置的整数值，这个值的类型应该和type参数指定的类型一致。如果给定值的长度超过了type参数指定的类型，那么SET命令将根据type参数指定的类型截断给定值。比如，如果用户尝试将整数123（二进制表示为01111011）存储到一个u4类型的区域中，那么命令会先将该值截断为4位长的二进制数字1011（即十进制数字11），然后再进行设置。

SET子命令会返回指定区域被设置之前的旧值作为执行结果。

通过执行以下命令，我们可以从偏移量0开始，设置一个8位长的无符号整数值198（二进制表示为11000110）：
在这里插入图片描述从子命令返回的结果可以看出，该区域被设置之前存储的整数值为0。下图展示了执行设置命令之后的位图：

BITFIELD命令允许用户在一次调用中执行多个子命令，比如，通过在一次BITFIELD调用中使用多个SET子命令，我们可以同时对位图的多个区域进行设置：
在这里插入图片描述

第1个子命令SET u8 0 123从偏移量0开始，设置一个8位长无符号整数值123。
第2个子命令SET i32 20 10086从偏移量20开始，设置一个32位长有符号整数值10086。
第3个子命令SET i64 188 123456789从偏移量188开始，设置一个64位长有符号整数值123456789。

对于这3个子命令，BITFIELD命令返回了一个包含3个元素的数组作为命令的执行结果，这3个元素分别代表3个指定区域被设置之前存储的整数值，比如第一个子命令返回的结果就是我们之前为该区域设置的值198。下图展示了这个BITFIELD命令创建出的位图以及被设置的3个整数值在位图中所处的位偏移量。
在这里插入图片描述
上图也展示了SET子命令的两个特点：

设置可以在位图的任意偏移量上进行，被设置区域之间不必是连续的，也不需要进行对齐（align）。各个区域之间可以有空洞，即未被设置的二进制位，这些二进制位会自动被初始化为0。
在同一个位图中可以存储多个不同类型和不同长度的整数。

虽然这两个特点可以带来很大的灵活性，但是从节约内存、避免发生错误等情况考虑，我们一般还是应该：

以对齐的方式使用位图，并且让位图尽可能地紧凑，避免包含过多空洞。
每个位图只存储同一种类型的整数，并使用int-8bit、unsigned-16bit这样的键名前缀来标识位图中存储的整数类型。

1.6.2 根据索引对区域进行设置

除了根据偏移量对位图进行设置之外，SET子命令还允许用户根据给定类型的位长度，对位图在指定索引上存储的整数值进行设置。
在这里插入图片描述

当位图中存储的都是相同类型的整数值时，使用这种设置方法将给用户带来非常大的便利，因为这种方法允许用户直接对位图指定索引上的整数值进行设置，而不必知道这个整数值具体存储在位图的哪个偏移量上。

假设现在有一个位图，它存储着多个8位长的无符号整数，而我们想要把它的第133个8位无符号整数的值设置为22。如果使用SET子命令的偏移量设置格式，就需要先使用算式(133-1)*8计算出第133个8位无符号整数在位图中的起始偏移量1056，然后再执行以下命令：

BITFIELD bitmap set u8 1056 22

很明显，这种手动计算偏移量然后进行设置的做法非常麻烦也很容易出错。与此相反，如果我们使用的是SET子命令的索引设置格式，那么只需要执行以下命令就可以对位图的第133个8位无符号整数进行设置了：

BITFIELD bitmap set u8 #132 22

注意，因为SET子命令接受的索引是从0开始计算的，所以上面的子命令使用的索引是132而不是133。

1.6.3 获取区域存储的值

通过使用BITFIELD命令的GET子命令，用户可以从给定的偏移量或者索引中取出指定类型的整数值：

在这里插入图片描述 GET子命令各个参数的意义与SET子命令中同名参数的意义完全一样。

对于下面的位图来说：
在这里插入图片描述

我们来获取位图中存储的整数值

又或者根据索引存储和获取值：
在这里插入图片描述
如果用户给定的偏移量或者索引超出了位图的边界，或者给定的位图并不存在，那么GET子命令将返回0作为结果。

1.6.4 执行加法操作或减法操作

除了设置和获取整数值之外，BITFIELD命令还可以对位图存储的整数值执行加法操作或者减法操作，这两个操作都可以通过INCRBY子命令实现。

在这里插入图片描述
BITFIELD命令并没有提供与INCRBY子命令相对应的DECRBY子命令，但是用户可以通过向INCRBY子命令传入负数增量来达到执行减法操作的效果。INCRBY子命令在执行完相应的操作之后会返回整数的当前值作为结果。

以下代码演示了如何对一个存储着整数值10的区域执行加法操作：

在这里插入图片描述以下代码则演示了如何对区域存储的整数值执行减法操作：

1.6.5 处理溢出

BITFIELD命令除了可以使用INCRBY子命令来执行加法操作和减法操作之外，还可以使用OVERFLOW子命令去控制INCRBY子命令在发生计算溢出时的行为。

在这里插入图片描述 OVERFLOW子命令的参数可以是WRAP、SAT或者FAIL中的一个：

WRAP表示使用回绕（wrap around）方式处理溢出，这也是C语言默认的溢出处理方式。在这一模式下，向上溢出的整数值将从类型的最小值开始重新计算，而向下溢出的整数值则会从类型的最大值开始重新计算。
SAT表示使用饱和运算（saturation arithmetic）方式处理溢出，在这一模式下，向上溢出的整数值将被设置为类型的最大值，而向下溢出的整数值则会被设置为类型的最小值。
FAIL表示让INCRBY子命令在检测到计算会引发溢出时拒绝执行计算，并返回空值表示计算失败。

OVERFLOW子命令在执行时将不产生任何回复。此外，如果用户在执行BITFIELD命令时没有指定具体的溢出处理方式，那么INCRBY子命令默认使用WRAP方式处理计算溢出。

需要注意的是，因为OVERFLOW子命令只会对同一个BITFIELD调用中排在它之后的那些INCRBY子命令产生效果，所以用户必须把OVERFLOW子命令放到它想要影响的INCRBY子命令之前。比如对于以下BITFIELD调用来说，最开始的两个INCRBY子命令将使用默认的WRAP方式处理溢出，而之后的两个INCRBY子命令才会使用用户指定的SAT方式处理溢出。
在这里插入图片描述
此外，因为Redis允许在同一个BITFIELD调用中使用多个OVERFLOW子命令，所以用户可以在有需要的情况下，通过使用多个OVERFLOW子命令来灵活地设置计算的溢出处理方式。比如在以下调用中，第一个INCRBY子命令将使用SAT方式处理溢出，第二个INCRBY子命令将使用WRAP方式处理溢出，而最后的INCRBY子命令则会使用FAIL方式处理溢出：
在这里插入图片描述

在u4-nums这个位图中，存储了3个4位长无符号整数，并且它们的值都被设置成了该类型的最大值15：
在这里插入图片描述
如果我们使用INCRBY命令对这3个整数值执行加1计算，那么这3个加1计算都将发生溢出，但是通过为这些计算设置不同的溢出处理方式，这些计算最终将产生不同的结果：

BITFIELD u4-nums overflow wrap incrby u4 #0 1 overflow 
sat incrby u4 #1 1 overflow fail incrby u4 #2 1

在这里插入图片描述

第1个INCRBY子命令以回绕的方式处理溢出，因此整数的值在执行加1操作之后，从原来的类型最大值15回绕到了类型最小值0。因为INCRBY子命令默认就使用WRAP方式处理溢出，所以这里的第一个OVERFLOW子命令实际上是可以省略的。
第2个INCRBY子命令以饱和运算的方式处理溢出，因此整数的值在执行加1操作之后，仍然是类型的最大值15。
第3个INCRBY子命令以FAIL方式处理溢出，因此INCRBY子命令在检测到计算会引发溢出之后就放弃了执行这次计算，并返回一个空值表示计算失败。因为此次INCRBY命令未能成功执行，所以这个整数的值仍然是15。

1.6.6 使用位图存储整数的原因

在一般情况下，当用户使用字符串或者散列去存储整数的时候，Redis都会为被存储的整数分配一个long类型的值（通常为32位长或者64位长），并使用对象去包裹这个值，然后再把对象关联到数据库或者散列中。

与此相反，BITFIELD命令允许用户自行指定被存储整数的类型，并且不会使用对象去包裹这些整数，因此当我们想要存储长度比long类型短的整数，并且希望尽可能地减少对象包裹带来的内存消耗时，就可以考虑使用位图来存储整数。

1.6.7 时间复杂度说明

复杂度：O(N)，其中N为用户给定的子命令数量。

1.7 使用字符串命令对位图进行操作

因为Redis的位图是在字符串的基础上实现的，所以它会把位图键看作一个字符串键。
在这里插入图片描述
因此用户除了可以使用前面介绍的位图命令对位图进行操作之外，还可以使用字符串命令对位图进行操作。

比如，我们可以通过执行GET命令来获取整个位图：
在这里插入图片描述
也可以使用STRLEN命令获取位图的字节长度：

当我们使用字符串命令获取位图的值时，命令返回的是16进制字符串（\x表示十六进制），而不是一个二进制形式的位图：比如GET命令返回的就是字符串"\x80"而不是二进制位图00000100。因此我们在使用字符串命令操作位图的时候，必须先将命令返回的字符串转换回二进制形式，然后再执行具体的二进制操作。

1.8 小结

Redis的位图是由多个二进制位组成的数组，数组中的每个二进制位都有与之对应的偏移量（也称索引），用户通过这些偏移量可以对位图中指定的一个或多个二进制位进行操作。
BITCOUNT命令接受的是字节索引范围，而不是二进制位索引范围，忽略这一点很容易引发程序错误。
BITFIELD命令允许用户自行指定被存储整数的类型，并且不会使用对象去包裹这些整数，因此当我们想要存储长度比long类型短的整数，并且希望尽可能地减少对象包裹带来的内存消耗时，就可以考虑使用位图来存储整数。
因为位图是使用字符串实现的，所以字符串命令也可以用于处理位图命令。但是在使用字符串命令操作位图时，用户必须先把命令返回的字符串值转换成二进制值，然后再进行后续处理。