Redis源码剖析——有序集合对象_redis zset 源码剖析-CSDN博客

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/80298343

有序集合对象

有序集合的对象的编码可以为ziplist或者skiplist

ziplist实现有序集合

当满足下面两个条件时，有序集合的底层数据结构为skiplist
1. 元素数量小于128个
2. 所有元素成员的长度都小于64字节

ziplist编码的有序集合使用两个连续的节点来表示键值对，第一个保存成员，第二个保存分值，按分值从小到达排列

创建一个ziplist编码的有序集合对象的函数如下

robj *createZsetZiplistObject(void) {

    unsigned char *zl = ziplistNew();

    robj *o = createObject(REDIS_ZSET,zl);

    o->encoding = REDIS_ENCODING_ZIPLIST;

    return o;
}

举个例子，如执行下列命令
ZADD price 8.5 apple 5.0 banana 6.0 cherry
则内存布局如下图
这里写图片描述

skiplist实现有序集合

其实时同时用skiplist 和 dict 实现有序集合
结构体如下

typedef struct zset {

    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

创建函数如下

robj *createZsetObject(void) {

    zset *zs = zmalloc(sizeof(*zs));

    robj *o;

    zs->dict = dictCreate(&zsetDictType,NULL);
    zs->zsl = zslCreate();

    o = createObject(REDIS_ZSET,zs);

    o->encoding = REDIS_ENCODING_SKIPLIST;

    return o;
}

为什么要同时使用skiplist和dict来实现呢？
因为dict可以实现O(1)的查找，但是dict存储数据时无序的，在执行范围操作时需要排序复杂度为O(NlogN)，而skiplist为顺序结构，在实现范围操作时只需O(N)节省了时间。
skiplist和dict会使用指针来共享相同元素的成员和分值，因而并不会造成很大的内存浪费，而大大提高了时间效率

执行之前的命令后，用skiplist实现的有序集合的内存布局如下图
这里写图片描述