为什么 Redis SortedSet 使用跳过列表而不是平衡树？

Question

Redis文档如下：

ZSET 是使用两个数据结构来保存相同元素的有序集合，以便在排序数据结构中进行 O(log(N)) INSERT 和 REMOVE 操作。

这些元素被添加到将 Redis 对象映射到分数的哈希表中。同时，元素被添加到将分数映射到 Redis 对象的跳跃列表中（因此对象在此“视图”中按分数排序）。

我不太明白。有人能给我详细的解释吗？

Answer 1

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

有以下几个原因：

• 它们的内存消耗不是很大。基本上取决于你。更改节点具有给定级别数的概率的参数将使内存消耗比 btree 更少。
• 排序集通常是许多 ZRANGE 或 ZREVRANGE 操作的目标，即将跳跃列表作为链表进行遍历。通过此操作，跳跃列表的缓存局部性至少与其他类型的平衡树一样好。
• 它们更容易实现、调试等。例如，由于跳跃列表的简单性，我收到了一个补丁（已经在 Redis master 中），其中包含在 O(log(N)) 中实现 ZRANK 的增强跳跃列表。它只需要对代码进行少量修改。
  

关于 Append Only 的持久性和速度，我认为以更多代码和更多复杂性为代价来优化 Redis 并不是一个好主意，对于恕我直言，对于 Redis 目标来说应该很少见的用例（每个命令都使用 fsync() ） 。即使对于 ACID SQL 数据库，几乎没有人使用此功能，因为无论如何性能提示都很大。

关于线程：我们的经验表明 Redis 主要受 I/O 限制。我正在使用线程来提供虚拟内存中的内容。利用所有核心的长期解决方案，假设您的链接速度非常快，以至于可以使单个核心饱和，则运行多个 Redis 实例（无锁，几乎完全可随核心数量线性扩展），并使用“Redis 集群” “我计划在未来开发的解决方案。