为啥 redis 使用跳表 (skiplist) 而不是使用 red-black？

一个会写诗的程序员

发布于 2021-03-23 12:09:29

1.5K0

发布于 2021-03-23 12:09:29

基本结论

1、实现简单。 2、区间查找快。跳表可以做到O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。 3、并发环境优势。红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，需要锁住的节点更少，因此在这样的情况下性能好一些。

I was looking at Redis yesterday and noticed this. Is there any particular reason you chose skip list instead of btrees except for simplicity? Skip lists consume more memory in pointers and are generally slower than btrees because of poor memory locality so traversing them means lots of cache misses.

Antirez (Redis之父) 的回答

Antirez (Redis之父) on March 6, 2010:

There are a few reasons:

有几个原因：

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.

它们不是记忆密集型的。基本上由你决定。改变一个节点的这个参数：拥有给定级别数的概率（？），将使其比btree占用更少的内存。

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.

排序集，通常是许多 ZRANGE 或 ZREVRANGE 操作的目标，即作为链表遍历跳表。使用此操作，跳表的缓存局部性，至少与其他类型的平衡树一样好。

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.

它们更易于实现、调试等。例如，由于skip list的简单性，我收到了一个补丁（已经在Redis master中了），其中包含了在 O（log（N）） 中实现 ZRANK 的扩展 skip list。它只需要对代码稍作修改。

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

关于 Append-Only 持久性和速度，我不认为以牺牲更多代码，和更复杂的代价，来优化Redis是一个好主意。因为 IMHO 应该很少用于Redis目标（每个命令都是 fsync() ）。几乎没有人使用这个特性，即使是 ACID-SQL 数据库，因为性能提示很大。

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

关于线程：我们的经验表明Redis主要是I/O操作。我正在使用线程来服务虚拟内存中的东西。利用所有 CPU cores 的长期解决方案。假设你的链接速度很快，你可以运行多个Redis实例（没有锁，几乎完全可以线性扩展的核心数），来充分利用CPU cores，我计划在未来开发 “Redis集群” 的解决方案。

跳表SkipList简介

跳表具有如下性质：

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

跳表的搜索

例子：查找元素 117

(1) 比较 21，比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85，比 85 大，从后面找

(5) 比较 117，等于 117，找到了节点。

C代码：

/* 如果存在 x, 返回 x 所在的节点， 
 * 否则返回 x 的后继节点 */  
find(x)   
{  
    p = top;  
    while (1) {  
        while (p->next->key < x)  
            p = p->next;  
        if (p->down == NULL)   
            return p->next;  
        p = p->down;  
    }  
}