Redis 从跳跃表的源码分析（redis源码跳跃表）

Redis: 从跳跃表的源码分析

Redis是一个高效的内存数据库系统，其内部数据结构扮演了非常重要的角色。其中，跳跃表(Skiplist)就是Redis内部用于实现有序集合的重要数据结构。本文将会从Redis中跳跃表的源码分析入手，详细探究其实现原理。

1. 跳跃表的定义和特点

跳跃表是一种有序数据结构，由多个层次(级别)组成，每个级别都是一个简单的有序链表。可以把它看做是并行的多个链表，其中低层链表作为顶层链表的基础，在顶层链表上形成了“跃迁”的效果，以此提高查询效率。跳跃表最大的优势是在平均时间复杂度O(logN)的情况下，提供了近似于二分查找的性能，并具有快速的插入和删除操作的特点。

Redis跳跃表结构体定义如下：

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, *tl;

unsigned long length;

int level;

} zskiplist;

其中，zskiplistNode表示一个跳跃表的节点，它包含了节点的成员对象(sds ele)和分值(double score)，以及用于指示节点位置的前进指针和后退指针。zskiplist则是跳跃表对象，包含了指向头结点和尾节点的指针，跳跃表中节点的数量和跳跃表的节点层数。

2. 跳跃表的实现原理

跳跃表的插入操作

在Redis跳跃表中，插入操作的基本流程如下：

1. 查找插入位置：从顶层链表开始，依次向下遍历每一层链表，找到插入位置。过程中记录查找路径上每个节点到下一级节点的距离（即跨度），以便构建新节点的跨度表。

2. 添加新节点：创建新节点z，把在上一步中记录的跨度信息中的所有节点都更新，确保它们都能指向新节点z，并使新节点z指向相应跨度表的下一个节点。

3. 更新相邻节点跨度信息：从插入位置出发，依次修改所有相邻节点的跨度信息（在新节点z被插入之后的相邻节点），并把它们更新到跨度表中。

代码实现如下：

zskiplistNode *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–) {

/* store rank that is crossed to reach the insert position */

rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

while (x->level[i].forward &&

(x->level[i].forward->score

(x->level[i].forward->score == score &&

sdscmp(x->level[i].forward->ele,ele)

{

rank[i] += x->level[i].span;

x = x->level[i].forward;

}

update[i] = x;

}

/* we assume the element is not already inside, since we allow duplicated

* scores, reinserting the same element should never happen since the

* caller of zslInsert() should test in the hash table if the element is

* already inside or not. */

level = zslRandomLevel();

if (level > zsl->level) {

for (i = zsl->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

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 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->tl = x;

zsl->length++;

return x;

}

该函数首先定义了一个记录已处理的跳跃表节点、当前插入节点位置和插入节点信息的变量，并遍历所有层的链表找到插入点。随后，它更新跳跃表中所有相邻节点的跨度信息，并更新新节点的前进指针和后退指针，完成插入操作。

跳跃表的删除操作

跳跃表中节点的删除操作，需要涉及到跳跃表节点间的链接关系的更新。基本流程如下：

1. 查找删除节点：从顶层链表开始，依次向下遍历每一层链表，找到要删除的节点。过程中记录查找路径上每个节点到下一级节点的距离和需要删除的节点的层数，以便修改相关节点的跨度表。

2. 修改相邻节点的跨度信息：当找到待删除节点时，依次修改该节点和其前一个节点的跨度信息，把它们更新到跨度表中。

代码实现如下：

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {

int i;

for (i = 0; i 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->tl = x->backward;

}

while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)

zsl->level–;

zsl->length–;

return;

}

该函数首先遍历所有层的链表，找到待删除节点，并记录查找路径上每个节点到下一级节点的距离以及需要删除的节点的层数，便于删除节点。随后，它处理待删除节点和跳跃表中相邻节点的跨度，以便反映节点间的新链接关系。函数减少跳跃表中节点的数量，并返回。

3. 跳跃表的查询操作

跳跃表在查找过程中以O(logN)的时间复杂度，快速找到节点。查找基本流程如下：

1. 从顶层链表开始遍历，高层查找时，若节点x的后退指针不为空，则向后退指

香港服务器首选树叶云，2H2G首月10元开通。
树叶云（www.IDC.Net）提供简单好用，价格厚道的香港/美国云服务器和独立服务器。IDC+ISP+ICP资质。ARIN和APNIC会员。成熟技术团队15年行业经验。