Hyper の 个人博客

交流技术，分享生活

0%

Redis 原理初探（五）—— 有序集合

发表于 更新于 分类于 ， 阅读次数：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

跳跃表（skiplist）

定义

  • 在每个节点中维持多个指向其他节点的指针以快速访问节点的一种有序数据结构

  • 有序集合键的底层实现之一

适用场景

  • 一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串

  • 在集群节点中用作内部数据结构

跳跃表结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 跳跃表结点
typedef struct zskiplistNode
{
    // 层
    struct zskiplistLevel
    {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

层（Level 数组）

  • 原理：包含多个元素，每个元素包含一个指向其他节点的指针，以加快访问其他节点的速度。一般来说，其访问其他节点的速度与层数正相关。

  • 高度：每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小

前进指针（level [i].forward 属性）

  • def 从表头向表尾方向访问节点的指针

    • 一次可以跳过多个成员

  • 用于执行有序集合的遍历操作

跨度（level [i].span 属性）

  • def 两个节点之间的距离

    • 跨度越大，间距越远

  • 注：指向 Null 的所有前进指针的跨度都为 0，因未连向任何节点

  • 用于计算有序集合中成员的排名（rank）

后退指针（level [i].backward 属性）

  • def 从表尾向表头方向访问节点的指针

    • 每个节点只有一个后退指针，这也意味着每次只能通过顺序回退的方式到达有序集合的前一节点，以向前遍历

分值（level [i].score 属性）

  • def double 类型的浮点数

    • 所有节点按照分值从小到大来排序

成员（level [i].obj 属性）

  • def 指向字符串对象的指针，指向的对象中保存着一个 SDS 值

  • 在同一个跳跃表中，各个节点保存的成员对象必须是唯一的；多个节点保存的分值可以相同

  • 分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）

跳跃表

1
2
3
4
5
6
7
8
9
10
// 跳跃表
typedef struct zskiplist
{
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

执行下述操作的时间复杂度均为 O (1)：

  • 程序定位表头节点和表尾节点：header 和 tail 指针分别指向跳跃表的表头和表尾节点

  • 返回跳跃表的长度：使用 length 属性来记录节点的数量

  • 获取跳跃表中层高最大的那个节点的层数量：使用 level 属性，注：表头节点的层高并不计算在内

有序集合（zset）操作

常用命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import redis

# 创建连接
conn = redis.Redis(host='127.0.0.1', port=6379, password=123456)

# ZADD：向有序集合中添加指定成员及对应分值
# 注：此处Python做法与Redis相反，Redis中应先输入分值再输入成员名称
conn.zadd('zset_key', 'a', 1, 'b', 2, 'c', 3)
# ZCARD：返回有序集合包含的成员数量
conn.zcard('zset_key')
# ZINCRBY：将有序集合中的指定成员的对应分值加上incr量
conn.zincrby('zset_key', 'a', 3)
# ZSCORE：返回指定成员的分值
conn.zscore('zset_key', 'b')
# ZRANK：返回指定成员在有序集合中的排名
# 可以先获取指定成员的排名，再根据排名决定ZRANGE的范围
conn.zrank('zset_key', 'c')
# ZCOUNT：返回有序集合中介于给定最低和最高分值之间的成员数目
conn.zcount('zset_key', 0, 3)
# ZREM：从有序集合中移除指定成员，并返回被移除成员的数目
conn.zrem('zset_key', 'b')
# ZRANGE：返回有序集合中排名介于指定开始与结束位置的成员
# 指定withscores参数为真，则会一并返回成员的对应分值
conn.zrange('zset_key', 0, -1, withscores=True)

范围性数据的获取与删除命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# ZREVRANK：返回有序集合中成员的排名
# 按照分值从大到小排列
# 注：按照逆序处理有序集合，其工作方式与非逆序大体相同
conn.zrevrank('zset_key', 'c')
# ZREVRANGE：返回有序集合给定排名范围内的成员
# 按照分值从大到小排列
conn.zrevrange('zset_key', 0, -1, withscores=True)
# ZRANGEBYSCORE：返回有序集合中分值介于给定最小与较大范围之间的所有成员
conn.zrangebyscore('zset_key', 0, -1)
# ZREVRANGEBYSCORE：获取有序集合中分值介于给定最小与较大范围之间的所有成员
# 按照分值从大到小排列
conn.zrevrangebyscore('zset_key', 0, -1)
# ZREMRANGEBYRANK：移除有序集合中排名介于开始与结束位置之间的所有成员
conn.zremrangebyrank('zset_key', 0, 0)
# ZREMRANGEBYSCORE：移除有序集合中分值介于开始与结束位置之间的所有成员
conn.zremrangebyscore('zset_key', 0, 1)

并集与交集命令

1
2
3
4
5
6
conn.zadd('zset_key2', 'a', 1, 'b', 2, 'c', 3)
conn.zadd('zset_key3', 'a', 3, 'b', 2, 'c', 1)
# ZINTERSCORE：对给定有序集合进行交集运算
# 默认使用sum作为聚合函数，则相当于对各个有序集合中的成员分值做累加操作
conn.zinterstore('zset_key_i', ['zset_key2', 'zset_key3'])

1
2
3
# ZUNIONSTORE：对给定有序集合进行并集运算
# 还可以指定聚合函数为min/max，以适应不同的运算场景
conn.zunionstore('zset_key_u', ['zset_key2', 'zset_key3'], aggregate='min')

【参考】
[1] 《Redis 的设计与实现》

[2] 《Redis 实战》

相关文章：