Redis中有序集合的内部如何实现

有序集合的内部实现

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

以压缩列表作为内部实现

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

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

Redis有序集合内部实现解析

举个例子,我们使用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是一个开源的基于键值对存储的高性能NoSQL数据库,它支持多种数据结构,如字符串、哈希、列表、集合和有序集合等。本文主要介绍Redis中有序集合的内部实现以及与其他数据结构的异同点。
有序集合的概念与用途
有序集合(Sorted Set)是Redis提供的一种类似于集合的数据结构,每个成员都带有一个权重(Score),根据权重进行排序,可以看作是一个映射表,其中每个唯一的成员都与一个浮点数相关联。与集合不同的是,有序集合可以通过成员来查找,也可以根据权重范围来查找成员,具有更加灵活的使用方式。有序集合的常见应用场景包括计数、排行榜、任务队列等。
Redis内部的数据结构
在Redis中,有序集合通过两个Hash表来实现:一个Hash表用于存储元素和对应的权重值,另一个Hash表则用于存储元素和对应的插入时间戳。这两个Hash表的键都是有序集合的名称,唯一的区别是后缀不同(_score、_rank)。
每当有元素加入有序集合时,Redis都会同时将元素插入到这两个Hash表中。这两个Hash表是以内存方式存储的,所以每次对有序集合的操作都可以快速地执行,同时维护有序集合的顺序并且保证数据不会丢失。
与其他数据结构的区别
有序集合的优点
与列表、集合等数据结构不同的是,有序集合不仅可以保留每个元素本身的值,还可以为每个元素赋予一个权重。这使得有序集合可以在非常快的时间内进行排序,这对于排行榜、计数器等应用场景非常有用。
有序集合的局限性
虽然有序集合非常便利,但是它也要面临一些问题。首先,由于有序集合的特殊性质,它会比列表、集合等数据结构占用更多的内存。其次,由于有序集合需要维护成员的排序,因此它的插入、删除操作是比列表、集合等数据结构要慢的。最后,有序集合是基于内存存储的,如果服务器崩溃或者重启,有序集合中的数据是无法持久化的。
结语
总之,有序集合是一种非常实用的数据结构,它可以对各种类型的元素进行排序,并支持按照插入时间和权重两种方案进行排序。虽然有序集合在内存和性能上都有所限制,但在大多数实际应用场景下,这些限制都可以被充分地弥补和改善。对于用户来说,只需要结合自身需求,进行适当的选择和优化即可。