Redis为什么使用skiplist来实现zset
Redis为什么使用skiplist来实现zset
提问于 2021-04-01 19:16:44
我研究了Redis的实现，我知道zset背后有两种数据结构(ziplist和ziplist)。我知道skiplist的一些基本思想(保持多个指针更快地访问下一个元素，搜索的平均时间复杂度是O(logN))。
我的问题是：
我读到的信息说，Redis将使用skiplist实现zset有两种情况，第一:在zset中有许多成员，第二：zset中的memebers是long string。
在这两种情况下使用skiplist而不是ziplist有什么好处，为什么这两种情况需要特殊处理？为什么我们不总是使用一种数据结构来实现zset
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-04-02 00:36:28
ziplist搜索和更新的时间复杂度为O(n)，跳过列表为O(logN)
ziplist的唯一好处是内存的使用。由于zip列表由线性内存地址实现，没有指向其他节点的指针，因此可以为Redis节省大量内存空间。
当zset中只有很少的成员时，O(N)和O(logN)将没有显着性差异。但是内存的使用会有很大的不同(假设您有1m键的zset，而每个zset只有10个成员)。
当zset中有很多成员时(比如1m)，时间复杂度是很重要的，因为它会影响并发性能。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66914001
复制相关文章
相似问题
腾讯云开发者
