redis进阶之路-面试必问的zset

热心的大肚皮

发布于 2023-02-28 13:58:50

4280

发布于 2023-02-28 13:58:50

大家好，我是热心的大肚皮，皮哥。

what is zset

顺便一下set，上次我们说过，set也是使用dict实现，只不过value是null，所以不过多说了。言归正传，zset是redis中最具有特色的数据结构，类似于java中的SorteddSet和HashMap的结合，首先它有set不可重复的特性，在这个基础上，还可以给value赋予一个score（排序权重）。

那适合什么样的场景呢，举个栗子，可以实现一个书的榜单，value是书名，score是书的评分，如下。

> zadd books 9.0 "think in java"
(integer) 1
> zadd books 8.9 "java concurrency"
(integer) 1
> zadd books 8.7 "java cookbook"
(integer) 1
> zrange books 0 -1 # 根据score排序
"think in java"
"java concurrency"
"java cookbook"
> zrevrange books 0 -1 # 根据score逆序排序
"java cookbook"
"java concurrency"
"think in java"
> zcard books #count
(integer) 3
> zscore books "java concurrency"# score使用double存储，所以有精度问题
"8.9000000000000004" 
> zrank books "java concurrency" # 排名
(integer) 1
> zrangebyscore books 0 8.91 # 根据分值遍历
"java concurrency"
"java cookbook"
> zrangebyscore books -inf 8.91 withscores # 根据分值区间查询 score小于等于8.91
1）"java cookbook"
2）"8.59999999999999996" 
3）"java concurrency"
4）"8.9000000000000004"

how to achieve zset

那么zset怎么实现的呢？zset底层是hash字典加上跳跃链表（skiplist）。上篇说过hash字典，这次主要说跳跃链表。直接上源码。

/**
 * 有序集合结构体
 */
typedef struct zset {
    /*
     * Redis 会将跳跃表中所有的元素和分值组成 
     * key-value 的形式保存在字典中
     * todo：注意：该字典并不是 Redis DB 中的字典，只属于有序集合
     */
    dict *dict;
    /*
     * 底层指向的跳跃表的指针
     */
    zskiplist *zsl;
} zset;
/**
 * 跳跃表结构体
 */
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
/**
 * ZSETs use a specialized version of Skiplists
 * 跳跃表中的数据节点
 */
typedef struct zskiplistNode {
    sds ele;// 具体value
    double score;// 评分
    struct zskiplistNode *backward;// 后退指针
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        /**
         * 跨度实际上是用来计算元素排名(rank)的，
         * 在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，
         * 得到的结果就是目标节点在跳跃表中的排位
         */
        unsigned long span;
    } level[];    // 层
} zskiplistNode;

这么看有点懵逼吧？直接上图。

层数怎么定义呢？

上源码。

int zslRandomLevel(void) {
    int level =1;
    while((random()&0xFFFF)<(ZSKIPLIST_P * 0xFFFF))
        level+= 1;
    return (level<ZSKIPLIST_MAXLEVEL)?level:ZSKIPLIST_MAXLEVEL;
}

每个新加入的节点都调用随机算法分配层数，redis的概率是25%，也就是ZSKIPLIST_P为25%。

查找过程

查找、更新、删除区别不大，就已查找举例了。