Redis 跳跃表的独特实现方式解读
Redis 跳跃表基础概念
在深入探讨 Redis 跳跃表的独特实现方式之前，我们先来明确一些基础概念。跳跃表（Skip List）是一种以空间换时间的数据结构，它通过在每个节点中维持多个指向其他节点的指针，来提高查找、插入和删除操作的效率。与传统的链表相比，跳跃表可以在接近对数级别的时间复杂度内完成这些操作。
在跳跃表中，节点按层组织，最底层是一个普通的有序链表，包含所有的元素。每一层都是下一层的“快速通道”，通过跳过一些节点来加速查找过程。例如，在一个多层跳跃表中，如果要查找某个特定元素，我们可以从最高层开始，沿着指针快速移动，当发现当前指针指向的元素大于目标元素时，就下降一层继续查找。这种方式类似于在一个多层索引结构中进行查找，大大减少了需要遍历的节点数量。
Redis 跳跃表的结构设计
- 节点结构
Redis 中跳跃表的节点结构在
redis.h头文件中定义。每个节点包含以下主要部分：
typedef struct zskiplistNode {
// 成员对象，在有序集合中就是要排序的值
robj *obj;
// 分值，用于排序
double score;
// 后退指针，用于从表尾向表头遍历
struct zskiplistNode *backward;
// 层结构数组，每层包含一个前进指针和跨度值
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
其中，obj 用于存储实际的数据对象，在 Redis 的有序集合（Sorted Set）场景下，它可以是一个字符串对象等。score 是排序的依据，通过这个分值来决定节点在跳跃表中的位置。backward 指针允许从后向前遍历跳跃表，这在一些操作中非常有用，比如在删除节点时，需要通过这个指针找到前一个节点来调整链表结构。
level 是一个柔性数组，它的实际大小在运行时根据需要动态分配。每层的 forward 指针指向下一个节点，而 span 记录了从当前节点到 forward 指向节点之间跨越的节点数（不包括自身）。这个跨度值在计算排名等操作时很有帮助。
- 跳跃表结构
Redis 跳跃表整体由
zskiplist结构来表示，定义如下：
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;
header 指向跳跃表的表头节点，tail 指向表尾节点。length 记录了跳跃表中节点的总数，这使得获取跳跃表长度的操作时间复杂度为 O(1)。level 表示当前跳跃表中节点的最大层数，这个值在插入节点时可能会动态变化。
Redis 跳跃表的创建与初始化
- 创建节点
创建跳跃表节点的函数在
t_zset.c文件中，主要代码如下：
zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->obj = obj;
return zn;
}
该函数根据传入的层数 level、分值 score 和对象 obj 分配内存并初始化节点。这里通过 zmalloc 分配了足够的内存空间，不仅包含 zskiplistNode 结构体本身的大小，还加上了 level 层的 zskiplistLevel 结构体数组的大小。
- 创建跳跃表 创建跳跃表的函数如下：
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
在这个函数中，首先为 zskiplist 结构体分配内存，然后初始化一些基本属性。level 初始化为 1，length 初始化为 0。接着创建表头节点 header，表头节点的层数为 ZSKIPLIST_MAXLEVEL（Redis 中定义的最大层数，通常为 32），并将各层的 forward 指针初始化为 NULL，span 初始化为 0。backward 指针也初始化为 NULL，tail 指针同样初始化为 NULL。这样就创建好了一个空的跳跃表。
Redis 跳跃表的插入操作
- 确定插入位置和新节点层数 在插入节点时，首先要确定插入的位置。这通过从最高层开始遍历跳跃表来实现。同时，还需要随机确定新插入节点的层数。Redis 中确定新节点层数的函数如下：
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL)? level : ZSKIPLIST_MAXLEVEL;
}
这里通过随机数来决定层数，ZSKIPLIST_P 是一个概率参数，Redis 中定义为 0.25，意味着大约有 25% 的概率每增加一层。这样的随机化策略使得跳跃表的结构相对平衡，避免了某些层节点过于密集或稀疏的情况。
- 插入节点的具体过程
插入节点的主要函数是
zslInsert，简化后的核心代码如下：
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
rank[i] = i == (zsl->level-1)? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
level = zslRandomLevel();
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level,score,obj);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[0] == zsl->header)? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
首先，通过一个循环从最高层开始遍历跳跃表，找到每个层中插入位置的前驱节点，并记录在 update 数组中，同时记录从表头到该位置的跨越节点数 rank。然后确定新节点的层数 level。如果新节点的层数大于当前跳跃表的最大层数，则需要更新 update 数组和 rank 数组，并调整跳跃表的最大层数。
接着创建新节点，并将新节点插入到跳跃表中。通过调整 forward 指针和 span 值来维护跳跃表的结构。同时，还需要更新 backward 指针以及表尾指针 tail，最后更新跳跃表的长度 length。
Redis 跳跃表的删除操作
- 查找要删除的节点 删除节点首先要找到目标节点。与插入操作类似，从最高层开始遍历跳跃表来定位目标节点。核心查找代码如下：
zskiplistNode *zslDeleteNode(zskiplist *zsl, double score, robj *obj, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
x = x->level[0].forward;
if (x && score == x->score && equalStringObjects(x->obj,obj)) {
if (node) *node = x;
zslDeleteNodeInternal(zsl, x, update);
return 1;
}
return 0;
}
这里通过一个循环从最高层开始，找到每个层中目标节点的前驱节点记录在 update 数组中。然后检查最底层找到的节点是否是目标节点，如果是，则调用 zslDeleteNodeInternal 函数进行实际的删除操作。
- 实际删除节点
zslDeleteNodeInternal函数负责实际删除节点并调整跳跃表结构，核心代码如下：
void zslDeleteNodeInternal(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - 1;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span -= 1;
}
}
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
} else {
zsl->tail = x->backward;
}
while (zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
zfree(x);
}
在这个函数中，通过遍历跳跃表的各层，调整前驱节点的 forward 指针和 span 值，跳过要删除的节点。同时更新 backward 指针和表尾指针 tail。如果删除节点后某些高层不再有实际节点（即表头节点的该层 forward 指针为 NULL），则降低跳跃表的最大层数。最后，释放被删除节点的内存，并更新跳跃表的长度。
Redis 跳跃表的查找操作
- 基本查找过程 Redis 跳跃表的查找操作也是从最高层开始。核心查找代码如下：
zskiplistNode *zslFind(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *x = zsl->header;
int i;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj) < 0)))
{
x = x->level[i].forward;
}
}
x = x->level[0].forward;
if (x && score == x->score && equalStringObjects(x->obj,obj)) {
return x;
}
return NULL;
}
从最高层开始，沿着指针移动，当发现当前指针指向的节点分值大于目标分值或者分值相等但对象不匹配时，就下降一层继续查找。最后在最底层检查是否找到目标节点，如果找到则返回该节点，否则返回 NULL。
- 查找操作的时间复杂度分析 在平均情况下，由于跳跃表的多层结构，查找操作的时间复杂度接近对数级别，即 O(log n)，其中 n 是跳跃表中节点的数量。这是因为在每一层，我们都可以跳过大约一半的节点。在最坏情况下，跳跃表可能退化为一个普通链表，此时查找的时间复杂度为 O(n)，但这种情况由于随机化的层数生成策略，发生的概率非常低。
Redis 跳跃表在有序集合中的应用
在 Redis 的有序集合（Sorted Set）中，跳跃表被广泛应用来实现高效的排序和查找功能。有序集合中的每个元素都有一个分值（score），通过跳跃表可以快速地根据分值进行排序和查找。
例如，在实现 ZSCORE 命令获取有序集合中某个元素的分值时，就可以通过跳跃表的查找操作快速定位到目标节点并返回其分值。在实现 ZRANK 命令获取元素的排名时，利用跳跃表节点中的 span 值可以高效地计算出排名。
同时，跳跃表与哈希表结合使用，在 Redis 的有序集合实现中可以兼顾通过成员查找分值（哈希表的 O(1) 查找优势）和通过分值范围查找成员（跳跃表的高效范围查找优势）的需求，从而为用户提供了强大而灵活的有序集合操作功能。
Redis 跳跃表与其他数据结构的比较
- 与平衡树的比较 平衡树（如 AVL 树、红黑树等）也可以实现高效的查找、插入和删除操作，时间复杂度通常为 O(log n)。与跳跃表相比，平衡树的结构相对复杂，插入和删除操作可能需要进行多次旋转操作来维持平衡。而跳跃表通过随机化的层数生成策略，在实现上相对简单，并且在插入和删除操作时不需要进行复杂的结构调整，只需要局部调整指针和跨度值。
另外，跳跃表在遍历操作上更加灵活，它可以通过 backward 指针方便地从后向前遍历，而平衡树通常只能单向遍历。
- 与普通链表的比较 普通链表在查找操作上时间复杂度为 O(n)，插入和删除操作在已知位置的情况下时间复杂度为 O(1)。而跳跃表通过多层结构大大提高了查找效率，平均时间复杂度为 O(log n)，虽然插入和删除操作在实现上比普通链表复杂，但整体性能在大数据量下有显著提升。同时，跳跃表的空间复杂度相对较高，因为每个节点需要额外存储多层指针，但这是以空间换时间的策略。
综上所述，Redis 跳跃表通过其独特的结构设计和实现方式，在有序集合等场景下提供了高效且灵活的数据存储和操作功能，是 Redis 高性能的重要支撑之一。其设计思想和实现技巧值得我们在开发高性能数据结构时借鉴和学习。