Redis深度解析：跳跃表的原理与应用

一、跳跃表简介

跳跃表SkipList是一种有序的数据结构，是Redis有序集合的底层实现之一。

跳跃表中，数据被存储在节点中，每个节点包含一个数据元素和一组指向其他节点的指针。这些指针分布在不同的层级，用于提升跳跃表的访问性能。

跳跃表支持平均O(log N）、最坏O(N)复杂度的查找性能，并且支持通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为眺跃表的实现比平衡树 要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

二、跳跃表的原理

1. 跳跃表的数据结构

跳跃表是一种扩展的有序链表，它通过维护一个多级索引结构来实现快速查找。在跳跃表中，每个节点包含一个数据元素和一组指向其他节点的指针。这些指针分布在不同的层级，每个层级的指针数量都比下一层级少。最底层（第0层）包含所有的元素，而最高层则只包含少数几个元素。这样，查找操作可以在高层级开始，快速跳过那些不需要的元素。

• 简单的有序链表

在简单的有序列表中，要访问节点节点3需要经过节点1、2、3共3个节点；要访问节点9需要经过节点1、2、3…8、9共9个节点

• 跳跃表

在跳跃表中，要访问节点节点3需要经过节点1、3共2个节点（通过L1索引）；要访问节点9需要经过节点1、7、9共3个节点（通过L3索引）。

可以看到查找的复杂度得到极大提升。

2. 跳跃表的查找、插入和删除操作

• 查找操作 从最高层索引的头节点开始，
  • 如果当前节点的下一个节点的值小于要查找的值，则向右移动；
  • 如果当前节点的下一个节点的值大于要查找的值，则向下移动，
  • 直到找到目标值或者确定目标值不存在。
• 插入操作 首先进行查找操作，找到插入位置。然后随机生成一个层数，根据这个层数在每一层插入新节点。
• 删除操作： 首先进行查找操作，找到要删除的节点。然后在每一层删除这个节点。

3. 跳跃表的时间复杂度分析

由于跳跃表的层级结构，查找、插入和删除操作的平均时间复杂度和最坏时间复杂度都是O(log n)，其中n是跳跃表中元素的数量。这使得跳跃表在处理大量数据时具有很高的效率。同时，跳跃表的空间复杂度是O(n)，因为每个元素都需要存储在跳跃表中。

三、Redis中的跳跃表

1. Redis中跳跃表的实现

Redis中的跳跃表实现与基本的跳跃表有一些不同。在Redis中，跳跃表的每个节点除了包含一个指向下一个节点的指针数组外，还包含一个反向指针，指向前一个节点。这样，Redis的跳跃表可以支持双向遍历。此外，Redis的跳跃表还包含一个header节点和一个tail节点，分别指向跳跃表中的第一个节点和最后一个节点。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

2. Redis中跳跃表的特性

Redis中的跳跃表具有以下特性：

• 支持快速查找：由于跳跃表的多级索引结构，Redis可以在O(log N)的时间复杂度内查找到任意节点。
• 支持范围查找：由于跳跃表的有序性，Redis可以在O(log N)的时间复杂度内找到满足特定范围条件的所有节点。
• 支持双向遍历：由于每个节点都包含一个反向指针，Redis的跳跃表可以支持从任意节点开始的双向遍历。

四、跳跃表与其他数据结构的比较

1. 跳跃表与平衡树

平衡树（如AVL树、红黑树等）和跳跃表都是可以进行快速查找的数据结构，它们的查找、插入和删除操作的时间复杂度都是O(log N)。然而，平衡树的实现通常比跳跃表复杂，需要处理更多的旋转和平衡操作。相比之下，跳跃表的实现更简单，更易于理解和操作。

2. 跳跃表与哈希表

哈希表的查找、插入和删除操作的平均时间复杂度是O(1)，优于跳跃表的O(log N)。然而，哈希表不支持有序操作，例如获取最小值、最大值或者进行范围查找。而跳跃表由于其有序性，可以很好地支持这些操作。

3. 跳跃表与链表

链表是一种基础的数据结构，其查找、插入和删除操作的时间复杂度是O(N)。而跳跃表是对链表的扩展，通过添加多级索引，将查找、插入和删除操作的时间复杂度降低到O(log N)。同时，跳跃表保留了链表的有序性，可以支持一些链表无法支持的有序操作。

五、Redis中跳跃表的应用场景

在Redis中，跳跃表主要被用于实现有序集合Sorted Set。

有序集合是Redis支持的一种数据类型，它不仅可以存储一组元素，还可以为每个元素关联一个分数。通过这个分数，Redis可以快速地获取分数最高或最低的元素，或者获取满足特定分数范围的所有元素。这些操作都是通过跳跃表来实现的。

跳跃表在Redis集群节点中用作内部数据结构。

跳跃表在Redis中仅用于有序集合和集群节点内部数据结构两种场景。

六、跳跃表的优缺点小结

优点：

• 跳跃表的查找、插入和删除操作的时间复杂度都是O(log N)，在处理大量数据时具有很高的效率。
• 跳跃表的实现相对简单，比如相比于平衡树，跳跃表不需要进行复杂的旋转和平衡操作。
• 跳跃表支持有序操作，如获取最小值、最大值或进行范围查找。

缺点：

• 跳跃表的空间复杂度是O(N)，每个元素都需要存储在跳跃表中，这可能会占用较多的内存。
• 跳跃表的性能依赖于随机数生成器，如果随机数生成器的质量不高，可能会影响跳跃表的性能。

我的公众号：海天二路搬砖工