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）两种，当集合中的所有元素的成员长度较短并元素个数较少时，使用压缩列表作为内部实现，否则使用跳跃表和哈希表作为内部实现。当条件不满足时，压缩列表可以转换为跳跃表，但跳跃表不能转换为压缩列表。