数据结构
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 对象总结
| 数据类型 | 使用场景 | 备注 |
| 字符串（string） | 缓存；计数器；分布式锁 | 简单型的，比如 set strnum studentinfo. 计数器如限流 |
| 列表（list） | lpush + lpop = Stack (栈) lpush + rpop = Queue （队列） lpush + ltrim = Capped Collection （有限集合） lpush + brpop = Message Queue (消息队列) | 如阻塞队列，关注列表 |
| 哈希（hash） | 对象属性（尤其不定长） | 如缓存 studentinfo hmset setnum setnum 1 stuname dinghaijun age 33 |
| 集合（set） | 适用于社交场景/推荐场景 | 点赞、粉丝、共同爱好/喜好、推送 |
| 有序集合（zset） | 排行榜；优先队列；缓存相关的元数据（比如按照排序的挑战） |
