Redis底层数据结构之ZSkipList

一、概述

ZSkipList是一种有序数据结构，支持平均 O(logN) 复杂度的查找、插入和删除操作。优点:高效的范围查询。使用场景: 存储有序集合数据，例如 Sorted Set 类型。

二、ZSkipList结构

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

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

在这里插入图片描述

ZSkipList:
header:header 是指向zskiplist的第一个节点（也就是跳表的头节点）的指针。它本质上是zskiplist的入口点，所有的操作（插入、查找、删除等）都是从这个节点开始的。header节点包含了多个指向不同层次第一个实际节点的指针，这些层级的指针帮助实现跳表的快速访问特性。
tail:tail 指向zskiplist中的最后一个节点。
length:length 表示zskiplist中节点的总数（不包括header节点）。这个数量随着节点的插入和删除动态变化。通过length可以快速获取到跳表的大小，无需遍历整个结构。
level:level 表示当前zskiplist中最高层级的层数。在跳表中，层级是动态管理的，每次插入新节点时，都会通过一定的随机化算法为其分配一个层数，level保留的是所有节点层数中的最大值。这个值允许zskiplist动态调整自身的索引结构，以适应不同的数据变化情形，同时保持操作的效率。

ZSkipListNode:
ele:ele 是存储在此节点中的实际值，即有序集合的成员。在Redis中，它通常是一个字符串。
score:score是一个浮点数，跟每个元素（即ele）相关联，表示元素在有序集合中的排序分数。按照score从小到大的顺序来为元素排序，同样的score值不会影响元素的位置。
backward:backward 是指向此节点在最低层的前一个节点的指针。这有助于实现从后向前的导航，并可支持有序集合的逆向查询。
level[]:level是一个数组，数组的元素是代表每一层的结构体。每一个结构体包含两个属性：forward和span。

forward:forward是一个指针，指向当前节点在这一层的下一个节点。
span:span表示当前节点到forward指针所指向的节点之间的间距，紧邻的两个结点之间的距离定义为1。

在这里插入图片描述

三、和平衡树和哈希表的对比

有序性：Skip List和平衡树支持元素的有序排列，而哈希表不支持。有序性使得Skip List和平衡树适合于范围查找操作，而哈希表则适用于单个键的快速查找。
范围查找：范围查找在Skip List中实现相当直观和高效，仅需线性遍历链表即可完成。相较之下，平衡树实现范围查找较为复杂，可能需要进行中序遍历来访问指定范围的所有节点。
插入和删除操作：平衡树的插入和删除操作可能导致树结构调整，以保持树的平衡性，逻辑较为复杂。而Skip List在插入和删除时仅需调整相邻节点的指针，操作较为简单且效率较高。
内存占用：Skip List的内存占用相对于平衡树更为灵活，其每个节点包含的指针数量平均为1/(1-p)，具体取决于参数p的大小。相对地，平衡树的每个节点通常包含两个指针（分别指向左右子树）。
查找性能：对于单个键值的查找，Skip List和平衡树的时间复杂度大致相同，都是O(log n)。而哈希表的查找性能在理想情况下接近O(1)，通常更高效。
实现难度：从算法实现上来看，Skip List的实现比平衡树简单许多，这对于开发者来说是一个重要的优势。