数据结构

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

两种实现方式

1、ziplist 第一个节点保存元素的成员，而第二个节点则保存元素的分值。压缩列表内的集合元素按分支从小到大排序，分值小的元素被放置在靠近表头的方向，分值较大的被放置在靠近表尾的方向。

2、 skiplist实际上，使用 zset 结构对字典和跳跃表进行封装。zset 结构中的 zsl 跳跃表分支按照从小到大保存了所有元素。通过这个跳跃表，程序可以对有序集合进行范围操作，比如 zrank , zrange 等命令都是基于跳跃表来实现的。

ziplist 插入数据

/* Insert (element,score) pair in listpack. This function assumes the element is
 * not yet present in the list. */
unsigned char *zzlInsert(unsigned char *zl, sds ele, double score) {
    unsigned char *eptr = lpSeek(zl,0), *sptr;
    double s;
    
    // 排序的过程
    while (eptr != NULL) {
        sptr = lpNext(zl,eptr);
        serverAssert(sptr != NULL);
        s = zzlGetScore(sptr);

        if (s > score) {
            /* First element with score larger than score for element to be
             * inserted. This means we should take its spot in the list to
             * maintain ordering. */
            // 元素，score
            zl = zzlInsertAt(zl,eptr,ele,score);
            break;
        } else if (s == score) {
            /* Ensure lexicographical ordering for elements. */
            if (zzlCompareElements(eptr,(unsigned char*)ele,sdslen(ele)) > 0) {
                zl = zzlInsertAt(zl,eptr,ele,score);
                break;
            }
        }

        /* Move to next element. */
        eptr = lpNext(zl,sptr);
    }

    /* Push on tail of list when it was not yet inserted. */
    if (eptr == NULL)
        zl = zzlInsertAt(zl,NULL,ele,score);
    return zl;
}

ziplist 压缩列表切换为跳跃表

/* Convert the sorted set object into a listpack if it is not already a listpack
 * and if the number of elements and the maximum element size and total elements size
 * are within the expected ranges. */
void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen, size_t totelelen) {
    if (zobj->encoding == OBJ_ENCODING_LISTPACK) return;
    zset *zset = zobj->ptr;

    if (zset->zsl->length <= server.zset_max_listpack_entries &&
        maxelelen <= server.zset_max_listpack_value &&
        lpSafeToAdd(NULL, totelelen))
    {
        zsetConvert(zobj,OBJ_ENCODING_LISTPACK);
    }
}

注意点

在 skiplist 的基础上，还需要创建 dict 的原因是当需要获取某个元素的 score 时，skiplist 的时候复杂度为 O(logN)，而 dict 时间复杂度为 O(1) , 见（zsetAdd）。需要特别主要的是底层为 ziplist 时，该操作时间复杂度为 O(n)

int zsetScore(robj *zobj, sds member, double *score) {
    if (!zobj || !member) return C_ERR;

    if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
        if (zzlFind(zobj->ptr, member, score) == NULL) return C_ERR;
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        dictEntry *de = dictFind(zs->dict, member);
        if (de == NULL) return C_ERR;
        *score = *(double*)dictGetVal(de);
    } else {
        serverPanic("Unknown sorted set encoding");
    }
    return C_OK;
}
?
unsigned char *zzlFind(unsigned char *lp, sds ele, double *score) {
    unsigned char *eptr, *sptr;
?
    if ((eptr = lpFirst(lp)) == NULL) return NULL;
    eptr = lpFind(lp, eptr, (unsigned char*)ele, sdslen(ele), 1);
    if (eptr) {
        sptr = lpNext(lp,eptr);
        serverAssert(sptr != NULL);
?
        /* Matching element, pull out score. */
        if (score != NULL) *score = zzlGetScore(sptr);
        return eptr;
    }
?
    return NULL;
}

• zkiplist 和 dict 共享元素和分值（指针复制）。
• 由 zkiplist 转 skiplist 的操作是不可逆的
• 两个参数 【zset-max-ziplist-entries】和 【zset-max-ziplist-value】可以在配置文件中修改
• zset 也不允许重复

使用场景

• 优先队列
• 排行榜系统：主要是视频网站需要对用户上传的视频做排行榜，榜单的维度坑是多个方面的：按照时间、按照播放量、按照获取的赞排序
• 添加用户赞数
• zadd user:ranking:2022_02_20 3 mike
• 增加点赞
• zincrby user:ranking:2020_02_20 1 mike
• 取消点赞
• zrem user:ranking:2020_02_20 mike
• 暂时获取点赞数最多的10 个用户
• zrevrang user:rangking:2020_02_20 0 9
• 显示用户信息以及用户分数和排名
• hgetall user:info:tom zscore user:rangking:2020_02_20 mike zrank user:rangking:2020_02_20 mike

常见操作

Redis 对象总结

作者：心城以北
链接：https://juejin.cn/post/7068678429834477605