redis——为什么选择了跳表而不是红黑树？

逃离我推掉我的手 2023-06-07 12:07 21阅读 0赞

[跳表是个啥东西][Link 1]请看这个文章。

我们知道，节点插入时随机出一个层数，仅仅依靠一个简单的随机数操作而构建出来的多层链表结构，能保证它有一个良好的查找性能吗？为了回答这个疑问，我们需要分析skiplist的统计性能。

在分析之前，我们还需要着重指出的是，执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：

*  首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
 *  如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
 *  节点最大的层数不允许超过一个最大值，记为MaxLevel。

这个计算随机层数的伪码如下所示：

randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
    level := level + 1
    return level

randomLevel()的伪码中包含两个参数，一个是p，一个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：

p = 1/4
    MaxLevel = 32

### skiplist的算法性能分析 ###

在这一部分，我们来简单分析一下skiplist的时间复杂度和空间复杂度，以便对于skiplist的性能有一个直观的了解。如果你不是特别偏执于算法的性能分析，那么可以暂时跳过这一小节的内容。

我们先来计算一下每个节点所包含的平均指针数目（概率期望）。节点包含的指针数目，相当于这个算法在空间上的额外开销(overhead)，可以用来度量空间复杂度。

根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析如下：

*  节点层数至少为1。而大于1的节点层数，满足一个概率分布。
 *  节点层数恰好等于1的概率为1-p。
 *  节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
 *  节点层数大于等于3的概率为p^2，而节点层数恰好等于3的概率为p^2(1-p)。
 *  节点层数大于等于4的概率为p^3，而节点层数恰好等于4的概率为p^3(1-p)。
 *  ......

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

![format_png][]

现在很容易计算出：

*  当p=1/2时，每个节点所包含的平均指针数目为2；
 *  当p=1/4时，每个节点所包含的平均指针数目为1.33。这也是Redis里的skiplist实现在空间上的开销。

接下来，为了分析时间复杂度，我们计算一下skiplist的平均查找长度。查找长度指的是查找路径上跨越的跳数，而查找过程中的比较次数就等于查找长度加1。以前面图中标出的查找23的查找路径为例，从左上角的头结点开始，一直到结点22，查找长度为6。

为了计算查找长度，这里我们需要利用一点小技巧。我们注意到，每个节点插入的时候，它的层数是由随机函数randomLevel()计算出来的，而且随机的计算不依赖于其它节点，每次插入过程都是完全独立的。所以，从统计上来说，一个skiplist结构的形成与节点的插入顺序无关。

这样的话，为了计算查找长度，我们可以将查找过程倒过来看，从右下方第1层上最后到达的那个节点开始，沿着查找路径向左向上回溯，类似于爬楼梯的过程。我们假设当回溯到某个节点的时候，它才被插入，这虽然相当于改变了节点的插入顺序，但从统计上不影响整个skiplist的形成结构。

现在假设我们从一个层数为i的节点x出发，需要向左向上攀爬k层。这时我们有两种可能：

*  如果节点x有第(i+1)层指针，那么我们需要向上走。这种情况概率为p。
 *  如果节点x没有第(i+1)层指针，那么我们需要向左走。这种情况概率为(1-p)。

![preview][]

用C(k)表示向上攀爬k个层级所需要走过的平均查找路径长度（概率期望），那么：

C(0)=0
    C(k)=(1-p)×(上图中情况b的查找长度) + p×(上图中情况c的查找长度)

代入，得到一个差分方程并化简：

C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
    C(k)=1/p+C(k-1)
    C(k)=k/p

这个结果的意思是，我们每爬升1个层级，需要在查找路径上走1/p步。而我们总共需要攀爬的层级数等于整个skiplist的总层数-1。

那么接下来我们需要分析一下当skiplist中有n个节点的时候，它的总层数的概率均值是多少。这个问题直观上比较好理解。根据节点的层数随机算法，容易得出：

*  第1层链表固定有n个节点；
 *  第2层链表平均有n\*p个节点；
 *  第3层链表平均有n\*p^2个节点；
 *  ...

所以，从第1层到最高层，各层链表的平均节点数是一个指数递减的等比数列。容易推算出，总层数的均值为log1/pn，而最高层的平均节点数为1/p。

综上，粗略来计算的话，平均查找长度约等于：

*  C(log1/pn-1)=(log1/pn-1)/p

即，平均时间复杂度为O(log n)。

当然，这里的时间复杂度分析还是比较粗略的。比如，沿着查找路径向左向上回溯的时候，可能先到达左侧头结点，然后沿头结点一路向上；还可能先到达最高层的节点，然后沿着最高层链表一路向左。但这些细节不影响平均时间复杂度的最后结果。另外，这里给出的时间复杂度只是一个概率平均值，但实际上计算一个精细的概率分布也是有可能的。

详情还请参见[William Pugh][]的论文《[Skip Lists: A Probabilistic Alternative to Balanced Trees][Skip Lists_ A Probabilistic Alternative to Balanced Trees]》。

### skiplist与平衡树、哈希表的比较 ###

*  skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
 *  在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
 *  平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
 *  从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
 *  查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
 *  从算法实现难度上来比较，skiplist比平衡树要简单得多。

### Redis中的skiplist和经典有何不同 ###

*  分数(score)允许重复，即skiplist的key允许重复。这在最开始介绍的经典skiplist中是不允许的。
 *  在比较时，不仅比较分数（相当于skiplist的key），还比较数据本身。在Redis的skiplist实现中，数据本身的内容唯一标识这份数据，而不是由key来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
 *  第1层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。
 *  在skiplist中可以很方便地计算出每个元素的排名(rank)。

# 作者的话 #

最后我们看看，对于这个问题，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.

有几个原因：

1）它们的记忆力不是很强。基本上由你决定。更改有关节点具有给定数量级别的概率的参数将使内存密集度低于btree。

2）排序集通常是许多Zrange或Zrevrange操作的目标，即作为链表遍历跳过列表。通过此操作，跳过列表的缓存区域性至少与其他类型的平衡树一样好。

3）它们易于实现、调试等。例如，由于跳过列表的简单性，我收到了一个补丁（已经在redis master中），其中包含在o（log（n））中实现zrank的扩展跳过列表。它只需要对代码稍作修改。

[Link 1]: https://blog.csdn.net/hebtu666/article/details/89370679
[format_png]: /images/20230601/f5eb4ac408234cb5a1c0c5a76544a231.png
[preview]: /images/20230601/4da1999fd48540ffbd1b96372006c4b4.png
[William Pugh]: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/William_Pugh
[Skip Lists_ A Probabilistic Alternative to Balanced Trees]: https://link.zhihu.com/?target=ftp%3A//ftp.cs.umd.edu/pub/skipLists/skiplists.pdf