Redis跳跃表数据结构解析
Redis跳跃表概述
在Redis中，跳跃表（Skip List）是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速查找的目的。跳跃表的平均查找时间复杂度为O(log n)，与平衡二叉树类似，但实现上更加简单和灵活。
跳跃表主要用于实现Redis的有序集合（Sorted Set）数据结构。在有序集合中，每个成员都关联着一个分数（score），通过分数来进行排序。跳跃表可以高效地插入、删除和查找元素，同时还能以O(n)的时间复杂度遍历所有元素。
跳跃表的基本结构
一个跳跃表由多个层（level）组成，每一层都是一个有序的链表。最底层（第0层）包含了所有的元素，而上面的层则是下面层的“快速通道”。每个节点在不同层中可能有不同的跨度（span），跨度表示该节点到下一个节点之间的元素数量。
跳跃表的节点结构如下：
typedef struct zskiplistNode {
sds ele; // 元素值
double score; // 分数
struct zskiplistNode *backward; // 后退指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度
} level[];
} zskiplistNode;
在这个结构中，ele 存储元素的值，score 存储元素的分数，backward 指针指向前一个节点，level 数组则存储了不同层的前进指针和跨度。
跳跃表本身的结构如下：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头节点和尾节点
unsigned long length; // 跳跃表的长度
int level; // 跳跃表的当前层数
} zskiplist;
header 指向跳跃表的头节点，tail 指向尾节点，length 表示跳跃表中节点的数量，level 表示跳跃表当前的层数。
跳跃表的创建与初始化
- 创建节点 创建一个跳跃表节点时，需要随机确定节点的层数。Redis中使用一种简单的随机算法来决定节点的层数，使得层数较高的节点出现的概率较低。
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = sdsdup(ele);
return zn;
}
- 初始化跳跃表 初始化跳跃表时，创建一个头节点，并将层数设置为1。
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_MAXLEVEL 是跳跃表允许的最大层数，通常设置为32。
随机层数生成算法
为了决定一个新插入节点的层数，Redis使用了如下的随机算法：
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
这里 ZSKIPLIST_P 是一个概率参数，通常设置为0.25。该算法使得节点层数为1的概率是75%，层数为2的概率是18.75%，以此类推，层数越高概率越低。
跳跃表的插入操作
- 查找插入位置 在插入一个新节点时，首先需要找到它在跳跃表中的正确位置。这通过从最高层开始，沿着前进指针进行查找，当遇到一个节点的下一个节点的分数大于要插入节点的分数时，就移动到下一层继续查找。
void zslInsert(zskiplist *zsl, double score, sds ele) {
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 &&
sdscmp(x->level[i].forward->ele,ele) < 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,ele);
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++;
跳跃表的删除操作
- 查找要删除的节点 删除节点时，同样从最高层开始查找要删除的节点，并记录下每个层中前一个节点的位置。
int zslDelete(zskiplist *zsl, double score, sds ele, 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 &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
// 省略后续删除节点的代码
}
- 删除节点并更新指针和跨度 找到要删除的节点后，更新相关指针和跨度，并释放节点内存。
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!zsl->header->level[0].forward)
zsl->tail = zsl->header;
while (zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
if (node)
*node = x;
sdsfree(x->ele);
zfree(x);
return 1;
}
return 0;
}
跳跃表的查找操作
查找操作与插入和删除操作类似，从最高层开始沿着前进指针查找，直到找到目标节点或者确定目标节点不存在。
zskiplistNode* zslFind(zskiplist *zsl, double score, sds ele) {
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 &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
}
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0)
return x;
else
return NULL;
}
跳跃表的遍历操作
可以从最底层的头节点开始，通过前进指针依次遍历跳跃表中的所有节点。
void zslTraverse(zskiplist *zsl) {
zskiplistNode *x = zsl->header->level[0].forward;
while (x) {
printf("score: %f, ele: %s\n", x->score, x->ele);
x = x->level[0].forward;
}
}
跳跃表的空间复杂度
跳跃表的空间复杂度取决于节点的数量和每个节点的平均层数。由于节点层数是通过随机算法生成的，平均情况下每个节点的层数为1/(1 - P)，其中P是随机层数生成算法中的概率参数（在Redis中P = 0.25），因此平均每个节点的层数约为1.33。所以跳跃表的空间复杂度为O(n)，其中n是节点的数量。
跳跃表的时间复杂度
- 查找操作 在平均情况下，跳跃表的查找时间复杂度为O(log n)，因为每次查找可以跳过大约一半的节点。在最坏情况下，所有节点都在同一层，此时查找时间复杂度退化为O(n)。
- 插入和删除操作 插入和删除操作都需要先查找插入或删除的位置，因此平均时间复杂度也为O(log n)，最坏情况下为O(n)。
跳跃表与其他数据结构的比较
- 与平衡二叉树的比较
- 实现复杂度：跳跃表的实现相对简单，不需要像平衡二叉树那样进行复杂的旋转操作来保持平衡。
- 查找性能：平均情况下，跳跃表和平衡二叉树的查找时间复杂度都是O(log n)，但跳跃表的常数因子可能更小，因为它的指针结构更简单。
- 插入和删除性能：同样，平均情况下两者性能相似，但跳跃表在插入和删除时不需要调整大量节点的结构，操作更局部化。
- 与普通链表的比较
- 查找性能：普通链表的查找时间复杂度为O(n)，而跳跃表平均为O(log n)，性能有显著提升。
- 插入和删除性能：虽然两者插入和删除操作的时间复杂度在平均情况下都是O(1)（不考虑查找位置的时间），但跳跃表在插入和删除后不需要重新排序，而如果普通链表是有序的，插入和删除后可能需要重新排序。
跳跃表在Redis中的应用
在Redis的有序集合数据结构中，跳跃表用于存储集合中的元素及其分数。通过跳跃表，Redis可以高效地进行插入、删除、查找和范围查询等操作。同时，Redis还结合了哈希表来实现快速的元素存在性检查，以提高整体性能。
例如，在执行 ZADD 命令向有序集合中添加元素时，实际上就是在跳跃表中插入一个新节点。而执行 ZRANGE 命令获取指定范围内的元素时，则是通过跳跃表的查找和遍历操作来实现的。
总结
跳跃表是一种高效的有序数据结构，它以相对简单的实现提供了接近平衡二叉树的查找性能。在Redis中，跳跃表被广泛应用于有序集合的实现，充分发挥了其插入、删除和查找的高效性。通过深入理解跳跃表的数据结构和操作原理，开发者可以更好地优化和使用Redis的有序集合功能，同时也能为设计其他高效的数据结构提供有益的参考。在实际应用中，根据具体的需求和场景，合理选择和使用跳跃表可以显著提升系统的性能和效率。
通过以上对Redis跳跃表数据结构的详细解析，希望读者能够对跳跃表有更深入的理解，并能在实际开发中灵活运用。同时，建议读者结合Redis的源代码进一步研究跳跃表的实现细节，以便更好地掌握这一重要的数据结构。