然后是编码为SKIPLIST时, 有序集合的内存布局如下:
在使用dict与skiplist实现有序集合时, 跳跃表负责按分数索引, 字典负责按数据索引. 跳跃表按分数来索引, 查找时间复杂度为O(lgn). 字典按数据索引时, 查找时间复杂度为O(1). 设想如果没有字典, 如果想按数据查分数, 就必须进行遍历. 两套底层数据结构均只作为索引使用, 即不直接持有数据本身. 数据被封装在SDS中, 由跳跃表与字典共同持有. 而数据的分数则由跳跃表结点直接持有(double类型数据), 由字典间接持有.
有序集合对象的API接口如下:
分类 API名 功能创建接口 robj *createZsetObject(void) 创建一个有序集合对象
默认内部编码为SKIPLIST, 即内部使用zskiplist与dict来实现有序集合
-- robj *createZsetZiplistObject(void) 创建一个有序集合对象
指定内部编码为ZIPLIST, 即内部使用ziplist来实现有序集合
释放接口 void freeZsetObject(robj *o) 释放一个有序集合对象
编码转换接口 void zsetConvert(robj *zobj, int encoding) 转换有序集合对象的内部编码
可以在ZIPLIST与SKIPLIST两种编码间转换
-- void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen) 判断当前有序集合对象是否有必要将底层编码转换为ZIPLIST, 如果有必要, 就执行转换
读写接口 int zsetScore(robj *zobj, sds member, double *score) 获取有序集合中, 指定数据的得分.
数据由member参数携带, 通过二进制判等的方式匹配
-- int zsetAdd( robj *zobj, double score, sds ele, int *flags, double *newscore) 向有序集合中添加数据, 或更新已存在的数据的得分.
flag是一个in-out参数, 其作为入参, 控制函数的具体行为, 其作为出参, 报告函数执行的结果.
作为入参时, *flags的语义如下:
ZADD_INCR 递增已存在的数据的得分. 如果数据不存在, 则添加数据, 并设置得分. 且若newscore != NULL, 执行操作后, 数据的得分还会赋值给*newscore
ZADD_NX 仅当数据不存在时, 执行添加数据并设置得分, 否则什么也不做
ZADD_XX 仅当数据存在时, 执行重置数据得分. 否则什么也不做
作为出参, *flags的语义如下:
ZADD_NAN 数据的得分不是一个数值, 代表内部出现的异常
ZADD_ADDED 新数据已经添加至集合中
ZADD_UPDATED 数据的得分已经更新
ZADD_NOP 函数什么也没做
-- int zsetDel(robj *zobj, sds ele) 从有序集合中移除一个数据
-- long zsetRank(robj *zobj, sds ele, int reverse) 获取有序集合中, 指定数据的排名.
若reverse==0, 排名以得分升序排列. 否则排名以得分降序排列.
第一个数据的排名为0, 而不是1
-- unsigned int zsetLength(const robj *zobj) 获取有序集合对象中存储的数据个数