Redis中的Zset是怎么实现的?


一、什么是Zset?

Zset(也叫Sorted Set)是Redis中的一种数据结构,支持传member和score两个字段,同时支持按照score排序。

常见命令:

  • 添加成员zadd <key> <score> <member>
  • 删除成员zrem <key> <member>
  • 查询成员数zcard <key>
  • 增量加分zincrby <key> <increment> <member>
  • 范围查询zrange <key> <start> <stop> [withscores]
  • 查询指定成员排名zrank <key> <member>
  • 查询指定成员分数zscore <key> <member>

使用场景:

  • 排行榜:把用户分数存到score,可以按照分数高低查询(如TopN)
  • 延迟队列:把延迟队列的执行时间戳存到score,可以轮询取出历史延迟队列并消费

二、Zset底层实现

Zset底层实现一般分为跳表(skiplist)和压缩列表(ziplist),但是在Redis 7.0后就不再使用ziplist了,而是用紧凑列表(listpack)替代。

1、使用场景

  • 当Zset数据量比较少时,Redis采用ziplist/listpack实现(通过连续存储元素来节约内存空间)
  • 当Zset数据量比较多时,Redis自动将ziplist/listpack转换为skiplist实现(保证元素的有序性和支持范围查询操作)

2、跳表(skiplist)

skiplist是一种基于并联链表的数据结构,实现简单,插入、删除、查找的复杂度均为O(logN)
具体可参考《什么是跳表?》


文章作者: GaryLee
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 GaryLee !
  目录