面试官:Redis中有序集合的内部实现方式是什么?
source link: https://blog.51cto.com/u_6740480/5446027
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
面试官: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)两种,当集合中的所有元素的成员长度较短并元素个数较少时,使用压缩列表作为内部实现,否则使用跳跃表和哈希表作为内部实现。当条件不满足时,压缩列表可以转换为跳跃表,但跳跃表不能转换为压缩列表。
竟然已经看到这里了,你我定是有缘人,留下你的点赞和关注,他日必成大器。
Recommend
-
7
Map集合、Map集合的基本功能、Map集合的获取功能、Map集合的遍历方式(一)(二)发布于 今天 15:04 一、Map集合public interface Map<K,V>
-
4
一个基于skiplist的有序集合Redis 有一个叫 ZSET 的容器,可以有序的存储数据项,每个数据项通过一个分数来决定先后顺序。这样的特性非常适合于排行类的应用,一些游戏的排行榜就是用 redis 来实现的。ZSET 内部用了一种叫 skiplist 的数据结构,它可...
-
163
搜集全网可用,亲测运行,整理移除重复和失效,去除内置助力,日常更新,一键自动配置内部互助,自动安装所需依赖(需青龙2.8+); 细水长流,低调使用,在精不在多,许多重复或失效的容易黑! ...
-
1
深圳:基本实现社会面动态清零 有序恢复社会生产生活秩序 3 小时前 · 亿欧 深圳市新型冠状病毒肺炎疫情防控指挥部通告:自3月14日以来...
-
3
用集合的方式看待 TypeScript上传日期:2022.04.08本文讲的只是一种思维,一种解题方式。 一道题可以用很多方式来解答,比如鸡兔同笼问题,可以用方程解答,可以用算术方式解答,还有很多表象解法:猜测法、假设法、鸡翅法...
-
7
GitHub 19k Star 的Java工程师成神之路,不来了解一下吗! 由于Java语言的集合框架中(collections, 如list, map, set等)没有提供任何简便的语法结构,这使得在建立常量集合...
-
7
面试官:JavaScript对象属性是有序的吗?更新日期: 2022-07-15阅读: 16标签:
-
9
#yyds干货盘点# 面试必刷TOP101:删除有序链表中重复的元素-II 原创 97的风
-
2
加入有序集合,Java 集合框架变得更加完善
-
4
一个泛型的有序Go Map实现 我们知道, Go内建的map类型对于插入的元素并没有保持它们的插入顺序,遍历的时候也故意设置成
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK