Redis 源码剖析与实战
蒋德钧
中科院计算所副研究员
17747 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
Redis 源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

05 | 有序集合为何能同时支持点查询和范围查询?

你好,我是蒋德钧。
有序集合(Sorted Set)是 Redis 中一种重要的数据类型,它本身是集合类型,同时也可以支持集合中的元素带有权重,并按权重排序。
而曾经就有一位从事 Redis 开发的同学问我:为什么 Sorted Set 能同时提供以下两种操作接口,以及它们的复杂度分别是 O(logN)+M 和 O(1) 呢?
ZRANGEBYSCORE:按照元素权重返回一个范围内的元素。
ZSCORE:返回某个元素的权重值。
实际上,这个问题背后的本质是:为什么 Sorted Set 既能支持高效的范围查询,同时还能以 O(1) 复杂度获取元素权重值?
这其实就和 Sorted Set 底层的设计实现有关了。Sorted Set 能支持范围查询,这是因为它的核心数据结构设计采用了跳表,而它又能以常数复杂度获取元素权重,这是因为它同时采用了哈希表进行索引。
那么,你是不是很好奇,Sorted Set 是如何把这两种数据结构结合在一起的?它们又是如何进行协作的呢?今天这节课,我就来给你介绍下 Sorted Set 采用的双索引的设计思想和实现。理解和掌握这种双索引的设计思想,对于我们实现数据库系统是具有非常重要的参考价值的。
好,接下来,我们就先来看看 Sorted Set 的基本结构。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

Redis中的Sorted Set是一种重要的数据类型,支持元素带权重并按权重排序。本文深入探讨了Sorted Set的设计思想和实现细节。文章详细介绍了Sorted Set的核心数据结构设计采用了跳表,以及如何以常数复杂度获取元素权重,同时采用哈希表进行索引。跳表的设计与实现、结点查询和层数设置方法也得到了详细阐述。此外,文章还探讨了Sorted Set如何将跳表和哈希表组合起来使用,并保持这两个索引结构中的数据一致性。总之,本文对于理解数据库系统的设计思路具有重要的参考价值。 Sorted Set通过组合使用跳表和哈希表的双索引机制,实现了高效的范围查询和单点查询。跳表作为有序链表,通过多层结构实现高效的查询操作,而哈希表则提升了单点查询的效率。文章还指出了这种双索引机制的不足之处,即在维护两种索引结构的一致性方面可能存在一定的开销。 总的来说,本文深入剖析了Sorted Set数据类型的底层实现,展示了跳表和哈希表的组合使用,以及它们在实现高效查询和数据一致性方面的优势和局限性。这对于读者快速了解Sorted Set的技术特点和应用场景具有重要的参考意义。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Redis 源码剖析与实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(20)

  • 最新
  • 精选
  • Kaito
    1、ZSet 当数据比较少时,采用 ziplist 存储,每个 member/score 元素紧凑排列,节省内存 2、当数据超过阈值(zset-max-ziplist-entries、zset-max-ziplist-value)后,转为 hashtable + skiplist 存储,降低查询的时间复杂度 3、hashtable 存储 member->score 的关系,所以 ZSCORE 的时间复杂度为 O(1) 4、skiplist 是一个「有序链表 + 多层索引」的结构,把查询元素的复杂度降到了 O(logN),服务于 ZRANGE/ZREVRANGE 这类命令 5、skiplist 的多层索引,采用「随机」的方式来构建,也就是说每次添加一个元素进来,要不要对这个元素建立「多层索引」?建立「几层索引」?都要通过「随机数」的方式来决定 6、每次随机一个 0-1 之间的数,如果这个数小于 0.25(25% 概率),那就给这个元素加一层指针,持续随机直到大于 0.25 结束,最终确定这个元素的层数(层数越高,概率越低,且限制最多 64 层,详见 t_zset.c 的 zslRandomLevel 函数) 7、这个预设「概率」决定了一个跳表的内存占用和查询复杂度:概率设置越低,层数越少,元素指针越少,内存占用也就越少,但查询复杂会变高,反之亦然。这也是 skiplist 的一大特点,可通过控制概率,进而控制内存和查询效率 8、skiplist 新插入一个节点,只需修改这一层前后节点的指针,不影响其它节点的层数,降低了操作复杂度(相比平衡二叉树的再平衡,skiplist 插入性能更优) 关于 Redis 的 ZSet 为什么用 skiplist 而不用平衡二叉树实现的问题,原因是: - skiplist 更省内存:25% 概率的随机层数,可通过公式计算出 skiplist 平均每个节点的指针数是 1.33 个,平衡二叉树每个节点指针是 2 个(左右子树) - skiplist 遍历更友好:skiplist 找到大于目标元素后,向后遍历链表即可,平衡树需要通过中序遍历方式来完成,实现也略复杂 - skiplist 更易实现和维护:扩展 skiplist 只需要改少量代码即可完成,平衡树维护起来较复杂 课后题:在使用跳表和哈希表相结合的双索引机制时,在获得高效范围查询和单点查询的同时,你能想到有哪些不足之处么? 这种发挥「多个数据结构」的优势,来完成某个功能的场景,最大的特点就是「空间换时间」,所以内存占用多是它的不足。 不过也没办法,想要高效率查询,就得牺牲内存,鱼和熊掌不可兼得。 不过 skiplist 在实现时,Redis 作者应该也考虑到这个问题了,就是上面提到的这个「随机概率」,Redis 后期维护可以通过调整这个概率,进而达到「控制」查询效率和内存平衡的结果。当然,这个预设值是固定写死的,不可配置,应该是 Redis 作者经过测试和权衡后的设定,我们这里只需要知晓原理就好。
    2021-08-05
    8
    63
  • 曾轼麟
    首先回答老师提出的问题,索引机制有哪些不足之处?首先我们知道(zset = dict + skiplist),那么可能会存在以下几个问题: 1、首先zset空间利用肯定是一大不足之处,毕竟是空间换时间 2、由于引入了dict,而dict底层是链式hash,当发生扩容的时候,对于整个zset其实是一种开销。 3、当zset进行大范围“有序”删除的时候开销会很大,跳表本身范围删除可以很快,本质可以只修改指针。但是当跳表删除后,还需要同步删除dict里面的数据,这时就会导致大开销了。(此外删除的时候有可能也会触发缩容rehash) 每次阅读老师的文章,都能有意外收获,本次阅读我得出以下的几个观点和结论: 1、redis作为一款优化到极致的中间件,不会单纯使用一种数据类型去实现一个功能,而会根据当前的情况选择最合适的数据结构,比如zset就是dict + skiplist,甚至当元素较少的时候zsetAdd方法会优先选择ziplist而不直接使用skiplist,以到达节约内存的效果(当小key泛滥的时候很有效果),当一种数据结构存在不足的情况下,可以通过和其它数据结构搭配来弥补自身的不足(软件设计没有银弹,只有最合适)。 2、redis仰仗c语言指针的特性,通过层高level数组实现的skiplist从内存和效率上来说都是非常优秀的,我对比了JDK的ConcurrentSkipListMap的实现(使用了大量引用和频繁的new操作),指针的优势无疑显现出来了 3、很多时候让我们感到惊艳的功能设计,可能本质只是一个很简单的原理,比如skiplist的随机率层高。既保证每层的数量相对为下一层的一半,又保证了代码执行效率 最后借着评论我提出一个我发现的疑问: 我本次在阅读redis skiplist源码的时候,发现skiplist的最大层高上限,曾经在2020-02-02被 Murillo 大神修改过,从64修改成了32,但是我一直无法理解这一目的,在网上也没找到相应的答案,想问一下这个修改是出于什么样的目的呢?
    2021-08-06
    3
    7
  • Milittle
    补一条:如果用ziplist存储sorted set,那么zscore也是遍历查询的,这个可以从:void zaddCommand(client *c)一路看下去,这里说一点感想:大家如果不知道一个数据结构的创建,可以从redisCommandTable里面的命令函数一路看下去,可以找到不少东西。
    2021-08-06
    5
  • Mo
    怎么保证一致性的呀
    2021-08-16
    2
    1
  • lzh2nix
    在看这一章的时候要厘清除两种数据结构(skiplist/dict)的关系,怎样将两种数据结构给关联起来。 在dict是 key---> score的关系,在skiplist中是按score排序的skiplist。score 做range操作的时候先O(logN)找到score在skiplist中位置,然后正向/反向的遍历。 不过我这里有个大胆的想法dict中不止记录key-->score的关系,可以再加一个字段score 对应的skiplistNode地址,也就是key--->{score, &skiplistNode{score}}, 这样查找score再skiplist中位置就是O(1)了, 各种range操作也会简化成是O(M)了,完全可以省去O(logN)的寻址。这样虽然新增里一个字段但是带来了更多的好处。 老师帮忙看下, 我这个思路那里有问题吗?为啥没有这样做?
    2021-08-08
    1
    1
  • skiplist + hashmap 实现的有序集合和常规的 double linked list + hashmap 所实现的 LRU 有些类似,都是使用链表结构进行核心的流程运转,hashmap 则是辅助链表使得能够在 O(1) 的时间复杂度内获取元素。这种组合式的数据结构还是很值得借鉴的。 leveldb 中也使用了 skiplist 来实现了 Memory Write Buffer,并且使用 CAS 操作实现了一个无锁的 skiplist,感兴趣的小伙伴也可以看看。实现上都差不多,都是使用 array + random 的方式存储和开辟新的层节点。
    2021-08-05
    1
  • Milittle
    1. 多浪费了存储空间。 2. 增加了编码的难度。 3. 有可能会导致一个数据结构的数据更新了,但是另外一个没有更新的问题(可能概率较小,但是也有可能)
    2021-08-05
    1
  • 飞鱼
    那么权重发生变化后,跳表如何调整自身的结构,从而保持按权重的有序性?跳表需要维持先按照权重的有序性。
    2023-11-02归属地:湖北
  • Geek_2a9ed1
    没有讲到,调表如何调整
    2023-05-23归属地:北京
  • 张三丰
    有一点我不是很理解,如果跳表是按照score排序,我理解,但为什么还要比sds的大小呢? sds的大小怎么比? 字符串之间比大小?难道是比字典顺序?
    2022-12-24归属地:北京
收起评论
显示
设置
留言
20
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部