为什么 Redis SortedSet 使用 Skip List 而不是 Balanced Tree？
Why Redis SortedSet uses Skip List instead of Balanced Tree?
Redis文档如下：
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.
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").
我不是很懂。有人可以给我详细的解释吗？
首先，我想我了解了 Redis 文档的内容。 Redis 有序集按照用户指定的元素分数维护元素的顺序。但是当用户使用一些 Redis Zset APIs 时，它只提供元素参数。例如：
ZREM key member [member ...]
ZINCRBY key increment member
...
redis需要知道这个成员（元素）是什么值，所以它使用hashtable维护一个映射，就像文档说的：
The elements are added to a hash table mapping Redis objects to
scores.
当它接收到一个成员时，通过hashtable找到它的值，然后在skip list上进行操作，以维护set的顺序。 redis使用了两个数据结构来维护一个double mapping来满足不同API的需要。
我读了 William Pugh 的论文 Skip Lists: A Probabilistic
替代平衡树，发现跳跃列表比旋转更优雅且更容易实现。
另外，我认为一般的二叉平衡树能够以相同的时间成本完成这项工作。如果我遗漏了什么，请指出。
Antirez 说，见 https://news.ycombinator.com/item?id=1171423
有几个原因：
- 它们不是很占用内存。这基本上取决于你。更改有关节点具有给定级别数的概率的参数将使内存密集度低于 btrees。
- 排序集通常是许多 ZRANGE 或 ZREVRANGE 操作的目标，也就是说，将跳过列表作为 linked 列表遍历。通过此操作，跳跃列表的缓存局部性至少与其他类型的平衡树一样好。
- 它们更易于实施、调试等。例如，由于跳跃列表的简单性，我收到了一个补丁（已经在 Redis master 中），其中包含在 O(log(N)) 中实现 ZRANK 的增强跳跃列表。它只需要对代码进行少量更改。
关于仅附加持久性和速度，我认为以更多代码和更复杂的用例为代价优化 Redis 不是一个好主意，恕我直言，Redis 目标应该很少见（fsync（ ) 在每个命令)。即使使用 ACID SQL 数据库，也几乎没有人使用此功能，因为无论如何性能提示都很大。
关于线程：我们的经验表明 Redis 主要是 I/O 绑定的。我正在使用线程来为虚拟内存提供服务。利用所有核心的长期解决方案，假设你的 link 如此之快以至于你可以使单个核心饱和，是 运行 Redis 的多个实例（无锁，几乎完全可随核心数量线性扩展), 并使用我计划在未来开发的 "Redis Cluster" 解决方案。
Redis文档如下：
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.
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").
我不是很懂。有人可以给我详细的解释吗？
首先，我想我了解了 Redis 文档的内容。 Redis 有序集按照用户指定的元素分数维护元素的顺序。但是当用户使用一些 Redis Zset APIs 时，它只提供元素参数。例如：
ZREM key member [member ...]
ZINCRBY key increment member
...
redis需要知道这个成员（元素）是什么值，所以它使用hashtable维护一个映射，就像文档说的：
The elements are added to a hash table mapping Redis objects to scores.
当它接收到一个成员时，通过hashtable找到它的值，然后在skip list上进行操作，以维护set的顺序。 redis使用了两个数据结构来维护一个double mapping来满足不同API的需要。
我读了 William Pugh 的论文 Skip Lists: A Probabilistic 替代平衡树，发现跳跃列表比旋转更优雅且更容易实现。
另外，我认为一般的二叉平衡树能够以相同的时间成本完成这项工作。如果我遗漏了什么，请指出。
Antirez 说，见 https://news.ycombinator.com/item?id=1171423
有几个原因：
- 它们不是很占用内存。这基本上取决于你。更改有关节点具有给定级别数的概率的参数将使内存密集度低于 btrees。
- 排序集通常是许多 ZRANGE 或 ZREVRANGE 操作的目标，也就是说，将跳过列表作为 linked 列表遍历。通过此操作，跳跃列表的缓存局部性至少与其他类型的平衡树一样好。
- 它们更易于实施、调试等。例如，由于跳跃列表的简单性，我收到了一个补丁（已经在 Redis master 中），其中包含在 O(log(N)) 中实现 ZRANK 的增强跳跃列表。它只需要对代码进行少量更改。
关于仅附加持久性和速度，我认为以更多代码和更复杂的用例为代价优化 Redis 不是一个好主意，恕我直言，Redis 目标应该很少见（fsync（ ) 在每个命令)。即使使用 ACID SQL 数据库，也几乎没有人使用此功能，因为无论如何性能提示都很大。
关于线程：我们的经验表明 Redis 主要是 I/O 绑定的。我正在使用线程来为虚拟内存提供服务。利用所有核心的长期解决方案，假设你的 link 如此之快以至于你可以使单个核心饱和，是 运行 Redis 的多个实例（无锁，几乎完全可随核心数量线性扩展), 并使用我计划在未来开发的 "Redis Cluster" 解决方案。