跳跃表（skiplist）是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
知识点
- 跳跃表是有序集合（zset）的底层实现之一
- redis跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
- 每个跳跃表节点的层高都是1到32之间的随机数
- 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点但成员对象必须是唯一但。
- 跳跃表中的节点按照分值进行大小排序，当分值相同时，节点按照成员对象的字典序大小进行排序。
跳表的搜索
例子：查找元素 117
1.比较 21， 比 21 大，往后面找
2.比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
3.比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
4.比较 85， 比 85 大，从后面找
5.比较 117， 等于 117， 找到了节点。
//跳跃表
typedef struct zskiplist {
// header 指针指向跳跃表头结点，一旦创建后固定不变，tail 指向尾结点（当表为空时值为 NULL）
struct zskiplistNode *header, *tail;
// length 记录整个跳跃表的长度，便于在 O(1) 的时间内获取表长度
unsigned long length;
// level 代表跳跃表的最高层数，初始化为1；
int level;
} zskiplist;
//跳跃表节点
typedef struct zskiplistNode {
//节点对象 是个sds 字符串 对应zset的member
robj *obj;
// 分值 对应zset的score
double score;
//指向跳跃表当前结点的前一个结点的指针
struct zskiplistNode *backward;
//每个跳跃表结点有一个 level 数组，数组最大长度为 32，数组元素类型为 zskiplistLevel 。它记录了每个 level 下当前结点链接到的下一个结点的前进指针 forward ，以及跨度 span
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
每个结点在创建的时候，会随机一个 [1,32] 的数 lv，作为结点的层高，并且创建 lv 个 zskiplistLevel 结构。每个结构会有一个 forward 指针 和 span 跨度
1.创建跳跃表节点
跳跃表的创建调用 zslCreate 接口，默认层数 level 为 1， 跳跃表长度 length 为 0，tail 置NULL， zslCreateNode 为创建一个跳跃表结点的接口，这里用来创建头结点，函数实现在 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;
}
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;
}
2.插入跳跃表结点
跳跃表的插入有点类似链表，首先要找到一个插入位置，生成一个结点，然后修改插入位置的指针进行插入操作。结点插入的 API 为 zslInsert，整个插入过程分为以下四部分：
- 寻找插入位置；
- 随机插入结点层数；
- 生成插入结点并插入；
- 额外信息更新；
- 具体实现在 t_zset.c 中：
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
//寻找插入位置
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;
}
3.删除跳跃表结点
int zslDelete(zskiplist *zsl, double score, robj *obj) {
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)) {
zslDeleteNode(zsl, x, update);
zslFreeNode(x);
return 1;
}
return 0;
}
网友评论