上篇中(click here), 我对跳表的一些基本的概念及其在redis源代码中的定义形式做了一些分析,同时也对跳表为什么能实现“跳跃”功能做了一番介绍。在这篇中,我将重点针对redis中跳表的实现做详细的分析;关于跳表相关的定义以及代码位置,在上篇中已有说明。

我们接着上篇末尾列出的那几个函数定义开始,这几个函数包含了最基本的几种操作,创建、插入、删除、查询;首先,我们看redis中是如何实现跳表的创建的:

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

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;
}  

首先是跳表结构的定义

struct zskiplistNode *header, *tail  

头尾指针,表名是双向链表。

unsigned long length;  

length是表示链表中节点的个数。

int level;  

表示跳表的层数。
然后我们在看zslCreate函数的定义,其中最关键的就是里边的那个循环,

ZSKIPLIST_MAXLEVEL  

宏定义,用于表示这个跳表最多有多少层。在循环内,将指向后边节点的forward指针置为NULL。 zslCreate调用完成后,其实就是创建了跳表的头结点(我们知道所有的链表实现中通常也是需要一个头结点的)。

然后我们再来看如何给跳表插入一个元素,插入元素代码请看t_zset.c,第107行zslInsert函数, 这里不贴出完整的代码,我只取其中比较重要的部分分析。

插入一个元素到跳表中,首先需要确定的是插入元素的位置,插入元素的时候需要保证跳表元素的排列顺序是升序排列;然后确定待插入节点的层数;最后是将节点各层指向正确的后续节点,然后插入元素。

首先请看下述代码段:

zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
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 < 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;
}  

这段代码主要的作用就是查找节点所要插入的位置。首先请看下边这幅图:
跳表图

通常,在跳表中查找元素的时候,不像在链表中查找元素那样需要遍历,而是会从头结点(头结点的下一节点才是元素节点)的最顶层开始,即上述代码的for循环,如果level数组的forward指针指向的节点的score值大于要插入的score,那么就下降一层;否则,就把x前进一个节点,指向到下一个节点,继续比较,即上述代码中while循环所做的工作。最后,当结束for循环时,update数组中保存的节点的forward就是将要插入的节点的level数组中的forward需要的值,并且待插入的节点一定是位于update[0]这个指针所指节点的后边

当新节点需要插入的位置找到后,就需要确定新节点的层数:

level = zslRandomLevel();  

我们知道,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以节点层数的确定当然也是随机的,以上这行代码便是确定节点的层数。

因为在前边查找的时候,是从当前跳表的最高一层开始查找的,如果新节点的层数大于跳表当前的层数,则需要更新跳表的层数并扩展之前的update数组,代码如下:

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;
}  

这里需要指出的是为什么新加的层节点直接用zsl->header赋值呢? 原因是这样的,因为新加入的这层与zsl->header直接肯定是没有其他节点的层的;而下边我们在给初始化新插入节点的level数组的时候,是把update的每一个元素当作其前一个跳跃节点的。

 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;

    /* update span covered by update[i] as x is inserted here */
    x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
    update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}  

综合这几段代码,我们便可以知道update这个数组的作用了;然后便是给backward赋值,以及修改zsl的tail指针:

 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++;  

到这里,基本跳表的创建以及插入元素都分析完毕了,下边,我们看看如何删除一个元素。删除元素的代码位于t_zset.c 第185行zslDelete定义

同插入节点类似,删除节点的时候,同样也是需要先找到需要删除节点的位置,代码如下:

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;
}  

这里,需要特别注意的是,到for循环结束时,update[0]处的指针所指向的是要删除的节点的前一个节点,到这里为止,要删除的节点是否存在并不知道。

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

这里便是将节点往后前进一个位置,便到了我们要寻找的节点的位置,到这里为止,要删除的节点是否存在仍然不知道,下边便是做节点的比较:

if (x && score == x->score && equalStringObjects(x->obj,obj)) {
    zslDeleteNode(zsl, x, update);
    zslFreeNode(x);
    return 1;
} else {
    return 0; /* not found */
}  

只有当score值与节点元素的值全部相等时,才说明要删除的节点是存在的,否则就是不存在的。

最后,节点元素的查找跟之前插入跟删除节点的查找过程是一样的,具体请看redis的实现 t_zset.c unsigned long zslGetRank(zskiplist *zsl, double score, robj *o) 这个函数。