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

创作时间:

作者:

@小白创作中心

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

引用

来源

https://cloud.tencent.com/developer/article/2419519

Redis中的跳跃表是一种高效的有序数据结构，它通过多级索引实现快速查找，同时保持了链表的有序性。本文将深入解析跳跃表的原理、实现细节及其在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;