登录
首页 >  数据库 >  Redis

Redis中有序集合的内部实现方式的详细介绍

来源:脚本之家

时间:2023-01-11 15:02:18 480浏览 收藏

IT行业相对于一般传统行业,发展更新速度更快,一旦停止了学习,很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习,精进自己的技术,尤其是初学者。今天golang学习网给大家整理了《Redis中有序集合的内部实现方式的详细介绍》,聊聊Redis有序集合,我们一起来看看吧!

面试官:Redis中基本的数据类型有哪些?

我:Redis的基本数据类型有:字符串(string)、哈希(hash)、列表(list)、集合(set)、有序集合(zset)。

面试官:有序集合的内部实现方式是什么?

我还沉浸在上一个问题的沾沾自喜中,顿时表情凝固了,手心开始冒出冷汗。“这个。。没有太深入了解”,我支支吾吾的说到。

面试官:回去等消息吧。

这句话说的干净利落,然后就没有然后了。失败是成功的妈妈,我不气馁,决定马上恶补一下。

有序集合的内部实现

有序集合的内部实现有两种,分别是:压缩列表(ziplist)和跳跃表(skiplist)。接下来,我们分别进行详细的了解。

以压缩列表作为内部实现

当有序集合的元素个数小于zset-max-ziplist-entries(默认为128个),并且每个元素成员的长度小于zset-max-ziplist-value(默认为64字节)的时候,使用压缩列表作为有序集合的内部实现。

每个集合元素由两个紧挨在一起的两个压缩列表结点组成,其中第一个结点保存元素的成员,第二个结点保存元素的分支。压缩列表中的元素按照分数从小到大依次紧挨着排列,有效减少了内存空间的使用。

举个例子,我们使用zadd命令创建一个以压缩列表为实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

以跳跃表作为内部实现

当有序集合的元素个数大于等于zset-max-ziplist-entries(默认为128个),或者每个元素成员的长度大于等于zset-max-ziplist-value(默认为64字节)的时候,使用跳跃表作为有序集合的内部实现。

此时,在有序集合中其实包含了两个结构,一个是跳跃表,另一个是哈希表。

在跳跃表中,所有元素按照从小到大的顺序排列。跳跃表的结点中的object指针指向元素成员的字符串对象,score保存了元素的分数。通过跳跃表,Redis可以快速地对有序集合进行分数范围、排名等操作。

在哈希表中,为有序集合创建了一个从元素成员到元素分数的映射。键值对中的键指向元素成员的字符串对象,键值对中的值保存了元素的分数。通过哈希表,Redis可以快速查找指定元素的分数。

虽然有序集合同时使用跳跃表和哈希表,但是这两种数据结构都使用指针共享元素中的成员和分数,不会额外的内存浪费。

举个例子,我们使用zadd命令创建一个以跳跃表为实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

内部实现的转换

当一个有序集合是以压缩列表作为内部实现时,再向这个有序集合添加较长的元素成员,或向这个有序集合的元素个数过多时,那么这个有序集合就会转换为以跳跃表作为内部实现。但是,以跳跃表作为内部实现的有序集合不会转换为以压缩列表作为内部实现。

举个例子,我们先创建一个以压缩列表作为内部实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

然后,再向它添加一个较长成员的元素,它就是转换为以跳跃表作为内部实现:

127.0.0.1:6379> zadd one-more-zset 4 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

然后,再把那一个较长成员的元素从有序集合中移除,有序集合依然是以跳跃表作为内部实现:

127.0.0.1:6379> zrem one-more-zset long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

总结

在Redis中,有序集合的内部实现有压缩列表(ziplist)和跳跃表(skiplist)两种,当集合中的所有元素的成员长度较短并元素个数较少时,使用压缩列表作为内部实现,否则使用跳跃表和哈希表作为内部实现。当条件不满足时,压缩列表可以转换为跳跃表,但跳跃表不能转换为压缩列表。

今天关于《Redis中有序集合的内部实现方式的详细介绍》的内容介绍就到此结束,如果有什么疑问或者建议,可以在golang学习网公众号下多多回复交流;文中若有不正之处,也希望回复留言以告知!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>