平衡树：为什么Redis内部实现用跳跃表

怼烎@ 2023-09-30 11:54 2阅读 0赞

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_12_color_FFFFFF_t_70_g_se_x_16][]

本文分享自华为云社区《[5分钟了解Redis的内部实现跳跃表（skiplist）][5_Redis_skiplist]》

跳跃表（skiplist）是一个有序的数据结构，它通过在每个节点维护不同层次指向后续节点的指针，以达到快速访问指定节点的目的。跳跃表在查找指定节点时，平均时间复杂度为O(log n) ，最坏时间复杂度为O(N)。

Redis使用跳跃表（skiplist）作为有序集合（zset）的底层实现之一。当有序集合的元素个数大于等于`zset-max-ziplist-entries`（默认为128个），或者每个元素成员的长度大于等于`zset-max-ziplist-value`（默认为64字节）的时候，使用跳跃表和哈希表作为有序集合的内部实现。

举个例子，我们使用`zadd`命令创建一个以跳跃表为实现的有序集合：

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long
    (integer) 1
    127.0.0.1:6379> zrange one-more-zset 0 -1
    1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
    127.0.0.1:6379> object encoding one-more-zset
    "skiplist"
    复制代码

#### 跳跃表的实现 ####

在Redis中的跳跃表是由`zskiplist`结构表示的，`zskiplist`结构包含由多个跳跃表节点组成的双向链表，每一个跳跃表节点都保存着元素成员和对应的分钟。下面我们一个一个地详细了解一下。

#### zskiplist结构 ####

跳跃表是由`zskiplist`结构表示的，它包含以下几个属性：

*  `header`属性: 指向头部跳跃表节点的指针。
 *  `tail`属性：指向尾部跳跃表节点的指针。
 *  `level`属性：表示跳跃表中层数最大的节点的层数，表头节点的层数不计算在内。
 *  `length`属性：表示跳跃表中的节点总数。

#### 跳跃表节点的结构 ####

跳跃表节点使用`zskiplistNode`结构表示，它包含以下几个属性：

*  `level`属性：表示层的数组，数组中每个项使用`zskiplistLevel`结构表示，它包含以下两个属性：
 *   *  `forward`属性：指向位于表尾方向其他节点的指针。
 *   *  `span`属性：当前节点到`forward`指向的节点跨越了多少个节点。
 *  `backward`属性：指向当前节点的前一个节点的指针。
 *  `obj`属性：指向元素成员的指针。
 *  `score`属性：当前元素成员对应的分数。

#### 图解跳跃表 ####

说了这么多，都比较抽象不容易理解，我们来举个例子：

![format_png][]

这就是一个跳跃表的内部结构，其中有4个元素，键分别是：万、猫、学、社。

#### 为什么不使用平衡树？ ####

跳跃表以有序的方式在层次化的链表中保存元素， 在大多数情况下，跳跃表的效率可以和平衡树媲美，查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。所以在Redis中没有使用平衡树，而是使用了跳跃表。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16][]

原文链接：[平衡树：为什么Redis内部实现用跳跃表 - 掘金][Redis_ -]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5fc70e1ee7da4a649770e4f1ec416d46.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap,size_12,color_FFFFFF,t_70,g_se,x_16
[5_Redis_skiplist]: https://link.juejin.cn/?target=https%3A%2F%2Fbbs.huaweicloud.com%2Fblogs%2F338593%3Futm_source%3Djuejin%26utm_medium%3Dbbs-ex%26utm_campaign%3Dother%26utm_content%3Dcontent
[format_png]: https://img-blog.csdnimg.cn/img_convert/2a6f0c220ac8b0dd9da1fd7290dac630.webp?x-oss-process=image/format,png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/00b670eb235c48b4a52f5988c82fdacb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap,size_20,color_FFFFFF,t_70,g_se,x_16
[Redis_ -]: https://juejin.cn/post/7078487936836059143