Redis 跳跃表

时隔四年,补课。

Skip List

关键词:链表、多级索引、动态结构

跳表是基于链表建立多级索引的动态数据结构。

在链表的基础之上,跳表利用空间换时间的方法,把单链表的时间复杂度从O(n)降低到跳表的O(log(n))

在跳表索引的构建上,需要维护索引大小平衡性,避免退化为单链表。

Source Code

Redis中ZSET也被称为有序集合(Sorted Set),是通过跳表来实现的。

Redis为什么使用跳表来实现ZSET?

① Redis并不是仅使用跳表来实现;

在数据量比较少时使用ziplist来实现,当数据量比较多的时候才会采用skiplist实现;

② 基于双向链表的跳表很容易实现ZRANGEZRERANGE,而红黑树等树形结构就没这么容易;

③ 跳表节点的插入与删除的复杂度更低,而红黑树等平衡树都需要旋转平衡操作。

在高并发场景下跳表性能更加,不过针对Redis来说单线程的数据变更来说红黑树的平衡旋转应该不是瓶颈。

下面将简单介绍下redis跳表的结构节点插入节点排序以及范围检索

zskiplist

ZSET是通过两部分组成:KV字典(dict)跳表索引(zskiplist)

1
2
3
4
5
/* ZSET结构体 */
typedef struct zset {
dict *dict; // KV字典
zskiplist *zsl; // 跳表索引
} zset;

其中,KV字典(dict)是基于哈希的数据存储的基础结构,跳表索引(zskiplist)是基于跳表的数据遍历搜索结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 跳表节点 */
typedef struct zskiplistNode {
sds ele; // 具体元素
double score; // 用于排序的分值
struct zskiplistNode *backward; // 向后的指针
/* 节点层次 */
struct zskiplistLevel {
struct zskiplistNode *forward; // 向前的指针
unsigned long span; // 当前节点与forward节点之间的节点数
} level[];
} zskiplistNode;

/* 跳表结构体 */
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 跳表的头节点与尾节点
unsigned long length; // 跳表的长度
int level; // 跳表的层次数
} zskiplist;

zslGetRank

zslGetRank是跳表中用于获取指定元素排名的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 获取排名 */
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
/* 从跳表的最高层开始遍历 */
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* 找到当前层级中与目标值最接近的位置 */
while (x->level[i].forward &&
// 当前层有forward的score小于目标值 或 当前层有forward的ele小于目标值
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}

/* x might be equal to zsl->header, so test if obj is non-NULL */
if (x->ele && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}

zslInsert

zslInsert是跳表的插入逻辑。

插入流程大体如下:

  • 位置搜索:从跳表的最高层到最底层开始遍历,记录每层的跳跃节点以及移动位置;
  • 构造新节点:随机生成一个level用于构造带插入节点;
  • 初始化新增层级:如果level大于原有最大层级,则需要对新增的层级初始化;
  • 节点加入到跳跃表:把待插入节点的层级节点加入到跳表层级的每一层,并重新计算span;
  • 更新跳表指针:更新节点的backward。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/* 插入数据 */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL]; // 记录每层插入节点的跳跃位置
unsigned int rank[ZSKIPLIST_MAXLEVEL]; // 记录到达每层跳跃节点的移动位置

/* 从跳表的最高层开始遍历 */
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* 初始化rank,如果是最高层则为0,否则为上一层的值 */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
/* 找到当前层级中与目标值最接近的位置 */
while (x->level[i].forward &&
// 当前层有forward的score小于目标值 或 当前层有forward的ele小于目标值
(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++) {
/* 链表插入(利用update记录的每层插入节点) */
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* span计算(利用rank记录的每层移动位置(从第i层到第0层)) */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}

/* 大于当前层级的span都需要span+1 */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}

/* 更新新增节点的前向指针,如果是链表头节点则忽略,否则更新为0层节点 */
x->backward = (update[0] == zsl->header) ? NULL : update[0];
/* 第0层为正向指针,节点本身带有的反向指针 */
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}

zrangeGenericCommand

zrangeGenericCommand是跳表的范围查询逻辑。

范围查询的流程大体如下:

  • 计算遍历位置以及长度:主要在于startendrangelen的边界条件以及内容计算;
  • 搜索目标范围的起始节点:利用zslGetElementByRank获取正序或倒序序列的起始位置;
  • 以起始节点开始遍历指定范围的节点:基于上一步计算的起始节点开始循环遍历(基于双向链表),需要注意遍历的方向;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* 范围查询 ZRANGE */
void zrangeGenericCommand(client *c, int reverse) {
robj *key = c->argv[1]; // KEY
long start; // 开始位置
long end; // 结束位置
long rangelen; // 扫描范围
...
/* start end 赋值 */
if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) ||
(getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return;

...
llen = zsetLength(zobj); // 跳表长度
...
/* 记录扫描长度 */
rangelen = (end-start)+1;
/* ziplist */
if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
...
/* skiplist */
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
zskiplist *zsl = zs->zsl;
zskiplistNode *ln;
sds ele;

/* 反向 or 正向,利用zslGetElementByRank获取起始节点 */
if (reverse) {
/* 默认从跳表尾部开始 */
ln = zsl->tail;
if (start > 0)
/* zslGetElementByRank仅支持正序排序,则反序起始位置为 llen-start(rank以llen结束) */
ln = zslGetElementByRank(zsl, llen-start);
} else {
/* 默认从跳表头部开始 */
ln = zsl->header->level[0].forward;
if (start > 0)
/* zslGetElementByRank仅支持正序排序,则正序起始位置为 start+1(rank从1开始) */
ln = zslGetElementByRank(zsl,start+1);
}
/* 从起始节点开始,遍历(正向 or 反向)获取所有数据 */
while(rangelen--) {
ele = ln->ele;
addReplyBulkCBuffer(c,ele,sdslen(ele));
if (withscores)
addReplyDouble(c,ln->score);
ln = reverse ? ln->backward : ln->level[0].forward;
}
} else {
serverPanic("Unknown sorted set encoding");
}
}

/* 获取指定排序的元素 */
zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
zskiplistNode *x;
unsigned long traversed = 0; // 记录移动次数
int i;
/* 从跳表的最高层开始遍历 */
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* 如果当前层的移动次数 小于 rank,则继续当前层遍历,否则,进入下一层 */
while (x->level[i].forward && (traversed + x->level[i].span) <= rank)
{
traversed += x->level[i].span;
x = x->level[i].forward;
}
/* 如果遍历到指定排序位置 */
if (traversed == rank) {
return x;
}
}
return NULL;
}

Reference

数据结构和算法-跳表的原理及实现
跳表──没听过但很犀利的数据结构