Redis 为什么用 skiplist 而不用平衡树?

首页 / 后端 风急天高猿啸哀 9月前 ⋅ 107 阅读

skiplist 跳跃表:在前面我们对于skiplist和平衡树、哈希表的比较中,其实已经不难看出Redis里使用skiplist而不用平衡树的原因了。现在我们看看,对于这个问题,Redis的作者 @antirez 是怎么说的:

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.


这里从内存占用、对范围查找的支持和实现难易程度这三方面总结的原因。 跳表:

全部评论: 0