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.



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