Redis 中的 5 种数据结构精讲(2) - 普京集团电子游戏平台

Linux Redis

Redis 中的 5 种数据结构精讲(2)

2019-01-22
68次浏览

命令

下面我们还是和学习其它数据类型一样,我们还是先学习一下 Redis 列表类型的命令。

 

1.添加操作

  • 从右边插入元素



1

rpush key value [value ...]

我们看 rpush 命令在插入时,是有返回值的,返回值的数量就是当前列表中所有元素的个数。

我们也可以用下面的命令从左到右获取当前列表中的所有的元素,也就是如上图所示中那样。


1

lrange 0 -1


  • 从左边插入元素



1

lpush key value [value ...]

lpush 命令的返回值及用法和 rpush 命令一样。通过上面的事例证明了我们前面说的,rpush 命令和 lpush 命令的返回值并不是当前插入元素的个数,而是当前 key 中全部元素的个数,因为当前 key 中已经有了 3 个元素,所以我们在执行插入命令时,返回的就是 6 而不是 3,。

  • 向某个元素前或者后插入元素



1

linsert key BEFORE|AFTER pivot value

linsert 命令在执行的时候首先会从当前列表中查找到 pivot 元素,其次再将这个新元素插入到 pivot 元素的前面或者后面。并且我们通过上图可以知道 linsert 命令在执行成功后也是会有返回值的,返回的结果就是当前列表中元素的个数。

 

2.查找

  • 获取指定范围内的元素列表



1

lrange key start stop

lrange 命令会获取列表中指定索引范围的所有元素。

通过索引获取列表主要有两个特点:

  • 索引下标从左到右分别是 0 到 N-1,从右到左是 -1 到 -N。

  • lrange 命令中的 stop 参数在执行时会包括当前元素,并不是所有的语言都是这样的。我们要获取列表中前两个元素则可以如下图所示:

  • 获取列表中指定索引下标的元素



1

lindex key index

  • 获取列表长度



1

llen key

 

3.删除

  • 从列表左侧弹出元素



1

lpop key

lpop 命令执行成功后会返回当前被删除的元素名称。

  • 从列表右侧弹出元素



1

rpop key

rpop 命令和 lpop 命令的使用方式一样。

  • 删除指定元素



1

lrem key count value

lrem 命令会将列表中等于 value 的元素删除掉,并且会根据 count 参数来决定删除 value 的元素个数。

下面我们看一下 count 参数的使用说明:

count > 0:表示从左到右,最多删除 count 个元素。也就是如下图所示:

我们看上图中的命令中,虽然我们将 count 参数指定的是 5,将 value 参数指定的是 2,但由于当前列表中只有一个 2,所以,当前 lrem 命令最多只能删除 1 个元素,并且 lrem 命令也是有返回值的,也就是当前成功删除元素的个数。

count < 0:从右到左,最多删除 count 个元素。

count = 0:删除所有元素。

  • 按照索引范围修剪列表



1

ltrim key start stop

ltrim 命令会直接保留 start 索引到 stop 索引的之间的元素,并包括当前元素,而之外的元素则都会删除掉,所以该命令也叫修剪列表。

并且有一点要注意,ltrim 命令不会返回当前的列表中元素的个数,而是返回改命令是否成功的状态。

 

4.修改

  • 修改指定索引下标的元素



1

lset key index value

 

5.阻塞操作



1

2

blpop key [key ...] timeout

brpop key [key ...] timeout

blpop 和 brpop 命令是 lpop 和 rpop 命令的阻塞版本,它们除了弹出方向不同以外,使用方法基本相同。

  • key [key …]:可以指定多个列表的键。

  • timeout:阻塞时间(单位:秒)

下面我们看一下该命令的详细使用。

列表为空:如果 timeout=3,则表示客户端等待 3 秒后才能返回结果,如果 timeout=0,则表示客户端会一直等待,也就是会阻塞。

由于我期间向列表中插入了元素,否则上述命令将一直阻塞下去。

列表不为空:如果 timeout=0,并且列表不为空时,则 blpop 和 brpop 命令会立即返回结果,不会阻塞。

下面我们看一下 blpop 和 brpop 命令的注意事项。

如果使用 blpop 和 brpop 命令指定多个键时,blpop 和 brpop 命令会从左到右遍历键,并且一旦有一个键能返回元素,则客户端会立即返回。

当列表为空时,上述命令会阻塞,如果向上述中的任何一个键中插入元素,则上述命令会直接返回该键的元素。

如果多个客户端都对同一个键执行 blpop 或者 brpop 命令,则最先执行该命令的客户端会获取到该键的元素。

我同时启动了 3 个客户端,因为当前列表为空,所以上述命令执行后会阻塞。如果此时我向该列表中插入元素,则只有第一个客户端会有返回结果,因为第一个客户端是第一个执行上述命令的。

 

时间复杂度

下面我们看一下列表中命令的相关时间复杂度。

操作类型 命令 时间复杂度
添加 rpush key value [value …] O(k),k是元素的个数
添加 lpush key value [value …] O(k),k是元素的个数
添加 linsert key BEFORE/AFTER pivot value O(n),n是pivot距离列表头或者尾的距离
查找 lrange key start stop O(s + n),s是start偏移量,n是start到stop的范围
查找 lindex key index O(n),n是索引的偏移量
查找 llen key O(1)
删除 lpop key O(1)
删除 rpop key O(1)
删除 lrem key count value O(n),n是列表长度
删除 ltrim key start stop O(n),n是要裁剪的元素个数
修改 lset key index value O(n),n是索引的偏移量
阻塞操作 blpop/brpop key [key …] timeout O(1)

 

内部编码

列表中的内部编码有两种,它们分别是:

  • ziplist(压缩列表):当列表中元素个数小于 512(默认)个,并且列表中每个元素的值都小于 64(默认)个字节时,Redis 会选择用 ziplist 来作为列表的内部实现以减少内存的使用。当然上述默认值也可以通过相关参数修改:list-max-ziplist-entried(元素个数)、list-max-ziplist-value(元素值)。

  • linkedlist(链表):当列表类型无法满足 ziplist 条件时,Redis 会选择用 linkedlist 作为列表的内部实现。

 

集合类型

Redis 中的集合类型,也就是 set。在 Redis 中 set 也是可以保存多个字符串的,经常有人会分不清 list 与 set,下面我们重点介绍一下它们之间的不同:

  • set 中的元素是不可以重复的,而 list 是可以保存重复元素的。

  • set 中的元素是无序的,而 list 中的元素是有序的。

  • set 中的元素不能通过索引下标获取元素,而 list 中的元素则可以通过索引下标获取元素。

  • 除此之外 set 还支持更高级的功能,例如多个 set 取交集、并集、差集等。

 

命令

下面我们介绍一下 set 中的相关命令。

 

1.集合内操作

  • 添加元素



1

sadd key member [member ...]

sadd 命令也是有返回值的,它的返回值就是当前执行 sadd 命令成功添加元素的个数,因为 set 中不能保存重复元素,所以在执行 sadd setkey c d 命令时,返回的是 1,而不是 2。因为元素 c 已经成功保存到 set 中,不能再保存了,只能将 d 保存到 set 中。

  • 删除元素



1

srem key member [member ...]

srem 命令和 sadd 命令一样也是有返回值的,返回值就是当前删除元素的个数。

  • 计算元素个数



1

scard key

scard 命令的时间复杂度为O(1),scard 命令不会遍历 set 中的所有元素,而是直接使用 Redis 中的内部变量。

  • 判读元素是否在集合中



1

sismember key member

sismember 命令也有返回值,如果返回值为1则表示当前元素在当前 set 中,如果返回 0 则表示当前元素不在 set 中。

  • 随机从 set 中返回指定个数元素



1

srandmember key [count]

srandmember 命令中有一个可选参数 count,count 参数指的是返回元素的个数,如果当前 set 中的元素个数小于 count,则 srandmember 命令返回当前 set 中的所有元素,如果 count 参数等于 0,则不返回任何数据,如果 count 参数小于 0,则随机返回当前 count 个数的元素。

  • 从集合中随机弹出元素



1

spop key [count]

spop 命令也是随机从 set 中弹出元素,并且也支持 count 可选参数,但有一点和 srandmember 命令不同。spop 命令在随机弹出元素之后,会将弹出的元素从 set 中删除。

  • 获取所有元素



1

smembers key

smembers 命令虽然能获取当前 set 中所有的元素,但返回元素的顺序与 sadd 添加元素的顺序不一定相同,这也就是前面提到过的保存在 set 中的元素是无序的。

 

2.集合间操作

  • 集合的交集



1

sinter key [key ...]

  • 集合的并集



1

sunion key [key ...]

  • 集合的差集



1

sdiff key [key ...]

  • 将集合的交集、并集、差集的结果保存



1

2

3

sinterstore destination key [key ...]

sunionstore destination key [key ...]

sdiffstore destination key [key ...]

为什么 Redis 要提供 sinterstore、sunionstore、sdiffstore 命令来将集合的交集、并集、差集的结果保存起来呢?这是因为 Redis 在进行上述比较时,会比较耗费时间,所以为了提高性能可以将交集、并集、差集的结果提前保存起来,这样在需要使用时,可以直接通过 smembers 命令获取。

 

时间复杂度

下面我们看一下 set 中相关命令的时间复杂度。

命令 时间复杂度
sadd key member [member …] O(k),k是元素的个数
srem key member [member …] O(k),k是元素的个数
scard key O(1)
sismember key member O(1)
srandmember key [count] O(count)
spop key [count] O(1)
smembers key O(n),n是元素的总数
sinter key [key …] O(m * k),k是多个集合中元素最少的个数,m是键个数
sunion key [key …] O(k),k是多个元素个数和
sdiff key [key …] O(k),k是多个元素个数和
sinterstore destination key [key …] O(m * k),k是多个集合中元素最少的个数,m是键个数
sunionstore destination key [key …] O(k),k是多个元素个数和
sdiffstore destination key [key …] O(k),k是多个元素个数和

 

内部编码

  • intset(整数集合):当集合中的元素都是整数,并且集合中的元素个数小于 512 个时,Redis 会选用 intset 作为底层内部实现。

  • hashtable(哈希表):当上述条件不满足时,Redis 会采用 hashtable 作为底层实现。

备注:我们可以通过 set-max-intset-entries 参数来设置上述中的默认参数。

下面我们看一下具体的事例,来验证我们上面提到的内部编码。

当元素个数较少并且都是整数时,内部编码为 intset。

当元素不全是整数时,内部编码为 hashtable。

当元素个数超过 512 个时,内部编码为 hashtable。


1

2

3

4

5

6

7

8

9

10

11

import redis

 

r = redis.Redis(host='127.0.0.1', port=6379)

    if r.object('encoding', 'setkey') != None:    

    print('Key为【setkey】的字节编码为【%s】' % r.object('encoding', 'setkey').decode('utf-8'))

for i in range(1, 600):

    r.sadd('setkey', i)

if r.object('encoding', 'setkey') != None:

    print('Key为【setkey】的字节编码为【%s】' % r.object('encoding', 'setkey').decode('utf-8'))

Key为【setkey】的字节编码为【intset】

Key为【setkey】的字节编码为【hashtable】

 

有序集合类型

看名字我们就知道,有序集合也是一种集合,并且这个集合还是有序的。列表也是有序的,那它和有序集合又有什么不同呢?有序集合的有序和列表的有序是不同的。列表中的有序指的的是插入元素的顺序和查询元素的顺序相同,而有序集合中的有序指的是它会为每个元素设置一个分数(score),而查询时可以通过分数计算元素的排名,然后再返回结果。因为有序集合也是集合类型,所以有序集合中也是不插入重复元素的,但在有序集合中分数则是可以重复,那如果在有序集合中有多个元素的分数是相同的,这些重复元素的排名是怎么计算的呢?后边我们再做详细说明。

下面先看一下列表、集合、有序集合三种数据类型之间的区别:

数据结构 是否允许重复元素 是否有序 有序实现方式 应用场景
列表 索引下标 时间轴、消息队列
集合 标签、社交
有序集合 分数 排行榜、社交

 

命令

 

1.集合内操作

  • 添加元素



1

zadd key [NX|XX] [CH] [INCR] score member [score member ...]

zadd 命令也是有返回值的,返回值就是当前 zadd 命令成功添加元素的个数。zadd 命令有很多选填参数:

  • nx: 元素必须不存在时,才可以设置成功。

  • xx: 元素必须存在时,才可以设置成功。

  • ch: 返回此命令执行完成后,有序集合元素和分数发生变化的个数

  • incr: 对 score 做增加。

备注:由于有序集合相比集合提供了排序字段,正是因为如此也付出了相应的代价,sadd 的时间复杂度为 O(1),而 zadd 的时间复杂度为O(log(n))。

  • 计算成员个数



1

zcard key

  • 计算某个成员的分数



1

zscore key member

在使用 zscore 命令时,如果 key 不存在,或者元素不存在时,该命令返回的都是(nil)。

  • 计算成员的排名



1

2

zrank key member

zrevrank key member

zrank 命令是从分数低到高排名,而 zrevrank 命令则恰恰相反,从高到低排名。有一点要特别注意, zrank 和 zrevrank 命令与 zscore 是命令不同的,前者通过分数计算出最后的排名,而后者则是直接返回当前元素的分数。

  • 删除元素



1

zrem key member [member ...]

返回的结果为成功删除元素的个数,因为 zrem 命令是支持批量删除的。

  • 增加元素分数



1

zincrby key increment member

虽然 zincrby 命令是增加元素分数的,但我们也可以指定负数,这样当前元素的分数,则会相减。

  • 返回指定排名范围的元素



1

2

zrange key start stop [WITHSCORES]

zrevrange key start stop [WITHSCORES]

zrange 命令是通过分数从低到高返回数据,而 zrevrange 命令是通过分数从高到低返回数据。如果执行命令时添加了 WITHSCORES 可选参数,则返回数据时会返回当前元素的分数。

  • 返回指定分数范围的元素



1

2

zrangebyscore key min max [WITHSCORES] [LIMIT offset count]

zrevrangebyscore key max min [WITHSCORES] [LIMIT offset count]

min 和 max 参数还支持开区间(小括号)和闭区间(中括号),同时我们还可以用 -inf 和 +inf 参数代表无限小和无限大。

  • 返回指定分数范围元素个数



1

zcount key min max

  • 删除指定排名内的升序元素



1

zremrangebyrank key start stop

  • 删除指定分数范围元素



1

zremrangebyscore key min max

 

2.集合间操作

  • 交集



1

zinterstore destination numkeys key [key ...] [WEIGHTS weight] [AGGREGATE SUM|MIN|MAX]

zinterstore 命令参数比较多:

  • destination:将交集的计算结果,保存到这个键中。

  • numkeys:需要做交集计算键的个数。

  • key [key …]:需要做交集计算的键。

  • WEIGHTS weight:每个键的权重,在做交集计算时,每个键中的分数值都会乘以这个权重,默认每个键的权重为 1。

  • AGGREGATE SUM|MIN|MAX:计算成员交集后,分值可以按照 sum(和)、min(最小值)、max(最大值)做汇总,默认值为  sum。

下面我们将权重设置为 0.5,这样当计算交集后,有序集合中的元素分数将都会减半,并且使用 max 参数汇总。

  • 并集



1

zunionstore destination numkeys key [key ...] [WEIGHTS weight] [AGGREGATE SUM|MIN|MAX]

zunionstore 命令的相关参数和 zinterstore 命令相同。

 

时间复杂度

命令 时间复杂度
zadd key [NX/XX] [CH] [INCR] score member [score member …] O(k*log(n)),k是添加元素的个数,n是当前有序集合元素个数
zcard key O(1)
zscore key member O(1)
zrank key member O(log(n)),n是当前有序集合元素个数
zrevrank key member O(log(n)),n是当前有序集合元素个数
zrem key member [member …] O(k*log(n)),k是删除元素的个数,n是当前有序集合元素个数
zincrby key increment member O(log(n)),n是当前有序集合元素个数
zrange key start stop [WITHSCORES] O(log(n) + k),k是要获取的元素个数,n是当前有序集合个数
zrevrange key start stop [WITHSCORES] O(log(n) + k),k是要获取的元素个数,n是当前有序集合个数
zrangebyscore key min max [WITHSCORES] [LIMIT offset count] O(log(n) + k),k是要获取的元素个数,n是当前有序集合个数
zrevrangebyscore key max min [WITHSCORES] [LIMIT offset count] O(log(n) + k),k是要获取的元素个数,n是当前有序集合个数
zcount key min max O(log(n)),n是当前有序集合元素个数
zremrangebyrank key start stop O(log(n) + k),k是要删除的元素个数,n是当前有序集合个数
zremrangebyscore key min max O(log(n) + k),k是要删除的元素个数,n是当前有序集合个数
zinterstore destination numkeys key [key …] [WEIGHTS weight] [AGGREGATE SUM/MIN/MAX] O(n k) + O(m log(m)),n是元素元素最小的有序集合元素个数,k是有序集合个数,m是结果集中元素个数
zunionstore destination numkeys key [key …] [WEIGHTS weight] [AGGREGATE SUM/MIN/MAX] O(n) + O(m * log(m)),n是所有有序集合元素个数和,m是结果集中元素个数。

 

内部编码

有序集合类型的内部编码有两种,它们分别是:

  • ziplist(压缩列表):当有序集合的元素个数小于 128 个(默认设置),同时每个元素的值都小于 64 字节(默认设置),Redis 会采用 ziplist 作为有序集合的内部实现。

  • skiplist(跳跃表):当上述条件不满足时,Redis 会采用 skiplist 作为内部编码。

备注:上述中的默认值,也可以通过以下参数设置:zset-max-ziplist-entries 和 zset-max-ziplist-value。

下面我们用以下示例来验证上述结论。

当元素个数比较少,并且每个元素也比较小时,内部编码为 ziplist:

当元素个数超过 128 时,内部编码为 skiplist。下面我们将采用 python 动态创建128个元素,下面为源码:


1

2

3

4

5

6

7

8

9

10

11

import redis

 

r = redis.Redis(host='127.0.0.1', port=6379)

if r.object('encoding', 'zsetkey') != None:

    print('Key为【zsetkey】的字节编码为【%s】' % r.object('encoding', 'zsetkey').decode('utf-8'))

for i in range(1, 600):

    r.zadd('zsetkey',i,1)

if r.object('encoding', 'zsetkey') != None:

    print('Key为【zsetkey】的字节编码为【%s】' % r.object('encoding', 'zsetkey').decode('utf-8'))

Key为【zsetkey】的字节编码为【ziplist】

Key为【zsetkey】的字节编码为【skiplist】

当有序集合中有任何一个元素大于 64 个字节时,内部编码为 skiplist。


1

2

3

4

5

6

7

8

9

10

11

12

import redis

 

r = redis.Redis(host='127.0.0.1', port=6379)

if r.object('encoding', 'zsetkey') != None:

    print('Key为【zsetkey】的字节编码为【%s】' % r.object('encoding', 'zsetkey').decode('utf-8'))

value = ''

for i in range(1, 600):

    value += str(i)

r.zadd('zsetkey',value,1)

if r.object('encoding', 'zsetkey') != None:

    print('Key为【zsetkey】的字节编码为【%s】' % r.object('encoding', 'zsetkey').decode('utf-8'))

Key为【zsetkey】的字节编码为【skiplist】


我要点评