为什么Redis SortedSet使用“跳过列表"而不是“平衡树"? [英] Why Redis SortedSet uses Skip List instead of Balanced Tree?

问题描述

Redis文档如下:

The Redis document said as below :

ZSET是使用两个数据结构来保存相同元素的有序集合为了使O(log(N))INSERT和REMOVE操作成一个排序数据结构.

ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.

将元素添加到哈希表，该哈希表将Redis对象映射到分数.同时将元素添加到跳过列表将分数映射到Redis对象(因此，对象按分数排序此视图").

The elements are added to a hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this "view").

我不太了解.有人可以给我详细的解释吗?

I can not understand very much. Could someone give me a detailed explanation?

推荐答案

Antirez说，请参见https://news.ycombinator.com/item?id=1171423

Antirez said, see in https://news.ycombinator.com/item?id=1171423

有几个原因:

• 它们不是非常占用内存的.基本上由您决定.更改有关节点具有给定数量级别的概率的参数将使内存占用量小于btree.
• 排序集通常是许多ZRANGE或ZREVRANGE操作的目标，即，将跳过列表作为链接列表进行遍历.通过此操作，跳过列表的缓存局部性至少与其他类型的平衡树一样好.
• 它们更易于实现，调试等.例如，由于跳过列表的简单性，我收到了一个补丁(已在Redis主服务器中使用)，该补丁具有在O(log(N))中实现ZRANK的增强型跳过列表.它几乎不需要更改代码.
  

关于仅追加"耐久性速度，对于以Redho目标(每个命令使用fsync())很少使用IMHO的用例来说，以更多代码和更多复杂性为代价来优化Redis并不是一个好主意.甚至对于ACID SQL数据库，几乎没有人使用此功能，因为性能提示仍然很大.

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

关于线程:我们的经验表明，Redis主要受I/O约束.我正在使用线程来从虚拟内存中提供服务.利用所有内核的长期解决方案，假设您的链接是如此之快以至于您可以饱和一个内核，正在运行多个Redis实例(无锁，几乎可以完全线性地随内核数线性扩展)，并使用"Redis群集"我计划将来开发的解决方案.

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

这篇关于为什么Redis SortedSet使用“跳过列表"而不是“平衡树"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！