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

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 作者经过测试和权衡后的设定，我们这里只需要知晓原理就好。

首先回答老师提出的问题，索引机制有哪些不足之处？首先我们知道（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，但是我一直无法理解这一目的，在网上也没找到相应的答案，想问一下这个修改是出于什么样的目的呢？

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

怎么保证一致性的呀

在看这一章的时候要厘清除两种数据结构(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)的寻址。这样虽然新增里一个字段但是带来了更多的好处。 老师帮忙看下， 我这个思路那里有问题吗？为啥没有这样做？

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

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

那么权重发生变化后，跳表如何调整自身的结构，从而保持按权重的有序性？跳表需要维持先按照权重的有序性。

没有讲到，调表如何调整

有一点我不是很理解，如果跳表是按照score排序，我理解，但为什么还要比sds的大小呢？ sds的大小怎么比？ 字符串之间比大小？难道是比字典顺序？