Redis 为什么使用skipList 而不是其他平衡树

There are a few reasons:

1) They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

1)它们不是很消耗内存。这基本上取决于你。改变一个节点给定级别数概率的参数,会比btree占用更少的内存。

2)排序后的集合通常是许多ZRANGE或ZREVRANGE操作的目标,即以链表的形式遍历跳跃表。使用这种操作,跳跃表的缓存局部性至少与其他类型的平衡树一样好。

3)它们更容易实现、调试等等。例如,感谢跳跃表的简单性,我收到了一个补丁(已经在Redis master),增强跳跃表实现ZRANK在O(log(N))。它只需要对代码做一点小小的修改。