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

精选留言(7)

• 

  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

  

  15
• 

  陌

  skiplist + hashmap 实现的有序集合和常规的 double linked list + hashmap 所实现的 LRU 有些类似，都是使用链表结构进行核心的流程运转，hashmap 则是辅助链表使得能够在 O(1) 的时间复杂度内获取元素。这种组合式的数据结构还是很值得借鉴的。
  
  leveldb 中也使用了 skiplist 来实现了 Memory Write Buffer，并且使用 CAS 操作实现了一个无锁的 skiplist，感兴趣的小伙伴也可以看看。实现上都差不多，都是使用 array + random 的方式存储和开辟新的层节点。

  2021-08-05

  

  1
• 

  Milittle

  补一条：如果用ziplist存储sorted set，那么zscore也是遍历查询的，这个可以从：void zaddCommand(client *c)一路看下去，这里说一点感想：大家如果不知道一个数据结构的创建，可以从redisCommandTable里面的命令函数一路看下去，可以找到不少东西。

  2021-08-06

  

  
• 

  曾轼麟

  首先回答老师提出的问题，索引机制有哪些不足之处？首先我们知道（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

  

  
• 

  胡玲玲

  评论区都是神仙- -

  2021-08-05

  

  
• 

  冷峰

  双索引要使用更多的内存，只是以内存换时间

  2021-08-05

  

  
• 

  Milittle

  1. 多浪费了存储空间。
  2. 增加了编码的难度。
  3. 有可能会导致一个数据结构的数据更新了，但是另外一个没有更新的问题（可能概率较小，但是也有可能）

  2021-08-05

  

  