redis 5.0.2 源码阅读——跳跃表skiplist

本文主要是介绍redis 5.0.2 源码阅读——跳跃表skiplist，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

redis中并没有专门给跳跃表两个文件。在5.0.2的版本中，结构体的声明与定义、接口的声明在server.h中，接口的定义在t_zset.c中，所有开头为zsl的函数。

一、数据结构

单个节点：

 1 /**
 2  * ZSETs use a specialized version of Skiplists
 3  * ZSET 使用专门版本的 Skiplist（跳跃表），跳跃表节点
 4  */
 5 typedef struct zskiplistNode {
 6     //key，唯一
 7     sds ele;
 8     //分值，可重复
 9     double score;
10     //后退指针
11     struct zskiplistNode *backward;
12     //层
13     struct zskiplistLevel {
14         //前进指针
15         struct zskiplistNode *forward;
16         //到本层下一节点的跨度，用于计算rank
17         unsigned long span;
18     } level[];
19 } zskiplistNode;

zskiplistNode定义了跳跃表中每个节点的数据结构，它是一个变长结构体。

 1 /*
 2 +------------------------+
 3 |sds ele                 |     /+-----------------------------+
 4 +------------------------+    / |struct zskiplistNode *forward|
 5 |double score            |   /  +-----------------------------+
 6 +------------------------+  /   |unsigned long span           |
 7 |zskiplistNode * backward| /    +-----------------------------+
 8 +------------------------+/     .                             .
 9 |zskiplistLevel  level[] |      .                             .
10 +------------------------+\     .                             .
11                            \    +-----------------------------+
12                             \   |struct zskiplistNode *forward|
13                              \  +-----------------------------+
14                               \ |unsigned long span           |
15                                \+-----------------------------+
16 */

下面将用以下结构表示

 1 /*
 2 +--------+
 3 |level[1]|
 4 |1(span) |
 5 +--------+
 6 |level[0]|
 7 |1(span) |
 8 +--------+
 9 |backward|
10 +--------+
11 |score   |
12 +--------+
13 |ele     |
14 +--------+
15 */

例如

 1 /*
 2 +--------+                +--------+                +--------+
 3 |level[1]|--------------->|level[1]|--------------->|level[1]|
 4 |2       |                |2       |                |0       |
 5 +--------+   +--------+   +--------+   +--------+   +--------+
 6 |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
 7 |1       |   |1       |   |1       |   |1       |   |0       |
 8 +--------+   +--------+   +--------+   +--------+   +--------+
 9 |backward|<--|backward|<--|backward|<--|backward|<--|backward|
10 +--------+   +--------+   +--------+   +--------+   +--------+
11 |1       |   |2       |   |3       |   |4       |   |5       |
12 +--------+   +--------+   +--------+   +--------+   +--------+
13 |a       |   |b       |   |c       |   |d       |   |e       |
14 +--------+   +--------+   +--------+   +--------+   +--------+
15 */

跳跃表定义

 1 /**
 2  * 跳跃表
 3  */
 4 typedef struct zskiplist {
 5     //头/尾节点
 6     struct zskiplistNode *header, *tail;
 7     //总长度
 8     unsigned long length;
 9     //总层数
10     int level;
11 } zskiplist;

因其头节点固定为空节点，固整体结构：

 1 /*
 2     +--------+                +--------+                +--------+
 3     |level[1]|--------------->|level[1]|--------------->|level[1]|
 4     |2       |                |2       |                |0       |
 5     +--------+   +--------+   +--------+   +--------+   +--------+
 6     |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
 7     |1       |   |1       |   |1       |   |1       |   |0       |
 8     +--------+   +--------+   +--------+   +--------+   +--------+
 9     |backward|<--|backward|<--|backward|<--|backward|<--|backward|
10     +--------+   +--------+   +--------+   +--------+   +--------+
11     |0       |   |2       |   |3       |   |4       |   |5       |
12     +--------+   +--------+   +--------+   +--------+   +--------+
13     |NULL    |   |b       |   |c       |   |d       |   |e       |
14 +-->+--------+   +--------+   +--------+   +--------+   +--------+<--+
15 |                                                                    |
16 |   +--------+                                                       |
17 +---|header  |                                                       |
18     +--------+                                                       |
19     |tail    |-------------------------------------------------------+
20     +--------+
21     |length=4|
22     +--------+
23     |level=2 |
24     +--------+
25 */

每个level层都是一条单身链表，其中level[0]中包含所有元素。

二、创建

根据指定的level，创建一个跳表节点：

 1 /**
 2  * Create a skiplist node with the specified number of levels.
 3  * The SDS string 'ele' is referenced by the node after the call.
 4  * 创建一个跳跃表节点
 5  */
 6 zskiplistNode *zslCreateNode(int level, double score, sds ele) {
 7     //分配内存
 8     zskiplistNode *zn =
 9         zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
10     //设置分数
11     zn->score = score;
12     //key
13     zn->ele = ele;
14     //返回创建的结构
15     return zn;
16 }

创建一个跳表

 1 /**
 2  * Create a new skiplist.
 3  * 创建一个跳跃表
 4  */
 5 zskiplist *zslCreate(void) {
 6     int j;
 7     zskiplist *zsl;
 8 
 9     //分配内存
10     zsl = zmalloc(sizeof(*zsl));
11     //设置初始层为1
12     zsl->level = 1;
13     //跳跃表长度为0
14     zsl->length = 0;
15     //创建并初始化头节点，跳跃表最大层级为64，头节点的key为NULL，分数为0
16     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
17 
18     //初始化头节点中level元素，前进指针为NULL，到本层下一节点的跨度span为0，用于计算rank
19     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
20         zsl->header->level[j].forward = NULL;
21         zsl->header->level[j].span = 0;
22     }
23     zsl->header->backward = NULL;
24     zsl->tail = NULL;
25     //返回创建的跳跃表
26     return zsl;
27 }

redis中定义的最大层数为64层。且在刚创建时，会生成一个空的头节点，这样就可以不用再考虑节点数从0至1或者从1至0时要处理的各种特殊情况。

刚创完的跳表结构（在后面的分析中以4做为最大层数）

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+
 9       |level[1]|-->NULL
10       |0       |
11       +--------+
12       |level[0]|-->NULL
13       |0       |
14       +--------+
15 NULL<-|backward|
16       +--------+
17       |0       |
18       +--------+
19       |NULL    |
20   +-->+--------+
21   |
22   |   +--------+
23   +---|header  |
24       +--------+
25       |tail    |-->NULL
26       +--------+
27       |length=0|
28       +--------+
29       |level=1 |
30       +--------+
31 */

三、插入节点

 1 /**
 2  * Returns a random level for the new skiplist node we are going to create.
 3  * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 4  * (both inclusive), with a powerlaw-alike distribution where higher
 5  * levels are less likely to be returned.
 6  * 跳跃表中用来决定跨越几层的抛硬币算法，正面概率设置为0.25
 7  */
 8 int zslRandomLevel(void) {
 9     int level = 1;
10     /**
11      * #define ZSKIPLIST_P 0.25
12      */
13     while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
14         level += 1;
15     return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
16 }

需要注意的是redis中使用的决定新插入节点层数据的方法是抛硬币法，且“硬币”只有25%的几率是正面。

插入方法：

 1 /**
 2  * Insert a new node in the skiplist. Assumes the element does not already
 3  * exist (up to the caller to enforce that). The skiplist takes ownership
 4  * of the passed SDS string 'ele'.
 5  * 在跳跃表中插入一个新节点，假设该元素尚不存在（由调用者强制保证），跳过列表获得传递的 SDS 字符串“ele”的所有权。
 6  * ele就相当于key
 7  */
 8 zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
 9     //update数组，用于存储查找路径
10     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
11     //rank数组，用于存储每层路径节点的排名
12     unsigned int rank[ZSKIPLIST_MAXLEVEL];
13     int i, level;
14 
15     serverAssert(!isnan(score));
16     x = zsl->header;
17 
18     //先查找插入位置，从最上面的一层开始查找
19     for (i = zsl->level-1; i >= 0; i--) {
20         /* store rank that is crossed to reach the insert position */
21         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
22         /**
23          * 当当前层级的下一个节点不为空并且（下一个节点的分数小于插入节点的分数或者
24          * 二者分数相等但是插入的ele小于下一个节点的ele）就遍历当前层的下一个节点，否者记录查找路径，
25          * 并从当前位置开始遍历下一层，指导遍历到第0层
26          */
27         while (x->level[i].forward &&
28                 (x->level[i].forward->score < score ||
29                     (x->level[i].forward->score == score &&
30                     sdscmp(x->level[i].forward->ele,ele) < 0)))
31         {
32             rank[i] += x->level[i].span;
33             x = x->level[i].forward;
34         }
35         update[i] = x;
36     }
37     /**
38      * we assume the element is not already inside, since we allow duplicated
39      * scores, reinserting the same element should never happen since the
40      * caller of zslInsert() should test in the hash table if the element is
41      * already inside or not.
42      * 利用抛硬币算法的插入元素跨越的层数
43      */
44     level = zslRandomLevel();
45     if (level > zsl->level) {
46         //如果跨越的层数大于当前层，更新查找路径
47         for (i = zsl->level; i < level; i++) {
48             rank[i] = 0;
49             update[i] = zsl->header;
50             update[i]->level[i].span = zsl->length;
51         }
52         //更新当前跳跃表中的实际层数
53         zsl->level = level;
54     }
55 
56     //创建插入的跳跃表节点
57     x = zslCreateNode(level,score,ele);
58     //在跨越的每一层插入创建的节点
59     for (i = 0; i < level; i++) {
60         //插入当前层的链表当中
61         x->level[i].forward = update[i]->level[i].forward;
62         update[i]->level[i].forward = x;
63 
64         /**
65          * update span covered by update[i] as x is inserted here
66          * 更新插入位置相邻两个节点的跨度也就是span
67          */
68         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
69         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
70     }
71 
72     /**
73      * increment span for untouched levels
74      * 当插入元素的跨度小于zsl->level，更新level到zsl->level每一层查找路径中元素的跨度，因为当前层没有元素插入
75      * 所以需要跨度增加了1
76      */
77     for (i = level; i < zsl->level; i++) {
78         update[i]->level[i].span++;
79     }
80 
81     /**
82      * 设置节点的后退指针
83      */
84     x->backward = (update[0] == zsl->header) ? NULL : update[0];
85     if (x->level[0].forward)
86         x->level[0].forward->backward = x;
87     else
88         zsl->tail = x;
89     //更新第0层链表的长度
90     zsl->length++;
91     return x;
92 }

从注释可知，redis的跳表允许同score的情况发生，但是不允许同ele，且是由调用者在外部保证。若插入顺序为e，b，c，d，则插入e时：

step1、定义update数组与rank数组。

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |NULL    |     |0       |
 9 +--------+     +--------+
10 |NULL    |     |0       |
11 +--------+     +--------+
12 */

实际在linux环境运行时，不会默认初始化，应该是一堆脏数据，此处是为了方便处理结构

step2、查找位置后

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |NULL    |     |0       |
 9 +--------+     +--------+
10 |header  |     |0       |
11 +--------+     +--------+
12 */

step3、e的level为2，比跳表的大，故要补齐update与rank数组

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |header  |     |0       |
 9 +--------+     +--------+
10 |header  |     |0       |
11 +--------+     +--------+
12 */

step4、插入节点，与单身链表插入相同，将新节点e各层，插入到update数组中记录的各层节点之后，并使用rank数组，计算跨度

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+   +--------+
 9       |level[1]|-->|level[1]|-->NULL
10       |1       |   |0       |
11       +--------+   +--------+
12       |level[0]|-->|level[0]|-->NULL
13       |1       |   |0       |
14       +--------+   +--------+
15 NULL<-|backward|   |backward|
16       +--------+   +--------+
17       |0       |   |5       |
18       +--------+   +--------+
19       |NULL    |   |e       |
20   +-->+--------+   +--------+
21   |
22   |   +--------+
23   +---|header  |
24       +--------+
25       |tail    |
26       +--------+
27       |length=0|
28       +--------+
29       |level=1 |
30       +--------+
31 */

step5、处理新插入节点的backward指针，与跳表的tail指针

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+   +--------+
 9       |level[1]|-->|level[1]|-->NULL
10       |1       |   |0       |
11       +--------+   +--------+
12       |level[0]|-->|level[0]|-->NULL
13       |1       |   |0       |
14       +--------+   +--------+
15 NULL<-|backward|   |backward|
16       +--------+   +--------+
17       |0       |   |5       |
18       +--------+   +--------+
19       |NULL    |   |e       |
20   +-->+--------+   +--------+<--+
21   |                             |
22   |   +--------+                |
23   +---|header  |                |
24       +--------+                |
25       |tail    |----------------+
26       +--------+
27       |length=1|
28       +--------+
29       |level=2 |
30       +--------+
31 
32 */

此时插入b：

找到位置后的update与rank数组

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |header  |     |0       |
 9 +--------+     +--------+
10 |header  |     |0       |
11 +--------+     +--------+
12 */

插入b节点后：

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+                +--------+
 9       |level[1]|--------------->|level[1]|-->NULL
10       |2       |                |0       |
11       +--------+   +--------+   +--------+
12       |level[0]|-->|level[0]|-->|level[0]|-->NULL
13       |1       |   |1       |   |0       |
14       +--------+   +--------+   +--------+
15 NULL<-|backward|   |backward|<--|backward|
16       +--------+   +--------+   +--------+
17       |0       |   |2       |   |5       |
18       +--------+   +--------+   +--------+
19       |NULL    |   |b       |   |e       |
20   +-->+--------+   +--------+   +--------+<--+
21   |                                          |
22   |   +--------+                             |
23   +---|header  |                             |
24       +--------+                             |
25       |tail    |-----------------------------+
26       +--------+
27       |length=2|
28       +--------+
29       |level=2 |
30       +--------+
31 */

需要注意的是，update数组idx = 1的节点并没有新的插入操作，span要自增，表示本层跨度增加了1。

插入c时的update与rank数组：

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |header  |     |0       |
 9 +--------+     +--------+
10 |b       |     |1       |
11 +--------+     +--------+
12 */

插入c后

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+                +--------+   +--------+
 9       |level[1]|--------------->|level[1]|-->|level[1]|-->NULL
10       |2       |                |1       |   |0       |
11       +--------+   +--------+   +--------+   +--------+
12       |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
13       |1       |   |1       |   |1       |   |0       |
14       +--------+   +--------+   +--------+   +--------+
15 NULL<-|backward|   |backward|<--|backward|<--|backward|
16       +--------+   +--------+   +--------+   +--------+
17       |0       |   |2       |   |3       |   |5       |
18       +--------+   +--------+   +--------+   +--------+
19       |NULL    |   |b       |   |c       |   |e       |
20   +-->+--------+   +--------+   +--------+   +--------+<--+
21   |                                                       |
22   |   +--------+                                          |
23   +---|header  |                                          |
24       +--------+                                          |
25       |tail    |------------------------------------------+
26       +--------+
27       |length=3|
28       +--------+
29       |level=2 |
30       +--------+
31 /*

最后插入d

update与rank数组

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |c       |     |2       |
 9 +--------+     +--------+
10 |c       |     |2       |
11 +--------+     +--------+
12 */

插入d

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+                +--------+                +--------+
 9       |level[1]|--------------->|level[1]|--------------->|level[1]|-->NULL
10       |2       |                |2       |                |0       |
11       +--------+   +--------+   +--------+   +--------+   +--------+
12       |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
13       |1       |   |1       |   |1       |   |1       |   |0       |
14       +--------+   +--------+   +--------+   +--------+   +--------+
15 NULL<-|backward|   |backward|<--|backward|<--|backward|<--|backward|
16       +--------+   +--------+   +--------+   +--------+   +--------+
17       |0       |   |2       |   |3       |   |4       |   |5       |
18       +--------+   +--------+   +--------+   +--------+   +--------+
19       |NULL    |   |b       |   |c       |   |d       |   |e       |
20   +-->+--------+   +--------+   +--------+   +--------+   +--------+<--+
21   |                                                                    |
22   |   +--------+                                                       |
23   +---|header  |                                                       |
24       +--------+                                                       |
25       |tail    |-------------------------------------------------------+
26       +--------+
27       |length=4|
28       +--------+
29       |level=2 |
30       +--------+
31 /*

如果此时要新插入节点a，score为4.5，则update与rank数组分别为

 1 /*
 2 update         rank
 3 +--------+     +--------+
 4 |NULL    |     |0       |
 5 +--------+     +--------+
 6 |NULL    |     |0       |
 7 +--------+     +--------+
 8 |c       |     |2       |
 9 +--------+     +--------+
10 |d       |     |3       |
11 +--------+     +--------+
12 */

四、删除节点

在已经查找到位置，与已知update数组时的删除方法

 1 /**
 2  * Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank
 3  * 被zslDelete, zslDeleteByScore and zslDeleteByRank调用的内部函数，在删除本节点之后，对应路径相应得做处理。
 4  *
 5  * 在level[0]层，使用从单向链表中删除节点的操作，把删除节点移出，
 6  * 再给高于level[0]的update数组中所有成员的span自减，节点少了，跨度要跟着降低。
 7  */
 8 void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
 9     int i;
10     for (i = 0; i < zsl->level; i++) {
11         if (update[i]->level[i].forward == x) {
12             //更新节点的跨度
13             update[i]->level[i].span += x->level[i].span - 1;
14             //更新节点的前进指针
15             update[i]->level[i].forward = x->level[i].forward;
16         } else {
17             update[i]->level[i].span -= 1;
18         }
19     }
20     //设置后退指针
21     if (x->level[0].forward) {
22         x->level[0].forward->backward = x->backward;
23     } else {
24         zsl->tail = x->backward;
25     }
26     //修正跳跃表的实际层数
27     while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
28         zsl->level--;
29     //更新跳跃表的长度
30     zsl->length--;
31 }

删除本节点之后，对应路径相应得做处理。

从跳表中删除指定节点的操作

 1 /* Delete an element with matching score/element from the skiplist.
 2  * The function returns 1 if the node was found and deleted, otherwise
 3  * 0 is returned.
 4  * 删除跳跃表中匹配到的分数和元素，如果该节点被找到且删除返回1，否则返回0
 5  *
 6  * If 'node' is NULL the deleted node is freed by zslFreeNode(), otherwise
 7  * it is not freed (but just unlinked) and *node is set to the node pointer,
 8  * so that it is possible for the caller to reuse the node (including the
 9  * referenced SDS string at node->ele).
10  * 如果node参数为NULL，删除的节点如果被找到，就需要在该函数中释放该节点所占有的内存空间，否者，将找到的该节点
11  * 赋值给*node，从而使得调用者在使用完该节点的时候再调用相应的函数zslFreeNode将其释放
12  */
13 int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
14     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
15     int i;
16 
17     //查找节点并记录路径
18     x = zsl->header;
19     for (i = zsl->level-1; i >= 0; i--) {
20         while (x->level[i].forward &&
21                 (x->level[i].forward->score < score ||
22                     (x->level[i].forward->score == score &&
23                      sdscmp(x->level[i].forward->ele,ele) < 0)))
24         {
25             x = x->level[i].forward;
26         }
27         update[i] = x;
28     }
29     /**
30      * We may have multiple elements with the same score, what we need
31      * is to find the element with both the right score and object.
32      */
33     x = x->level[0].forward;
34     if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
35         //根据准备删除的节点和查找路径对跳跃表做相应的处理
36         zslDeleteNode(zsl, x, update);
37         if (!node)//如果node不为NULL，就直接释放该节点的内存
38             zslFreeNode(x);
39         else
40             *node = x;//利用传出参数被调用者使用
41         return 1;
42     }
43     return 0; /* not found */
44 }

如以下跳表

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+                +--------+                +--------+
 9       |level[1]|--------------->|level[1]|--------------->|level[1]|-->NULL
10       |2       |                |2       |                |0       |
11       +--------+   +--------+   +--------+   +--------+   +--------+
12       |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
13       |1       |   |1       |   |1       |   |1       |   |0       |
14       +--------+   +--------+   +--------+   +--------+   +--------+
15 NULL<-|backward|   |backward|<--|backward|<--|backward|<--|backward|
16       +--------+   +--------+   +--------+   +--------+   +--------+
17       |0       |   |2       |   |3       |   |4       |   |5       |
18       +--------+   +--------+   +--------+   +--------+   +--------+
19       |NULL    |   |b       |   |c       |   |d       |   |e       |
20   +-->+--------+   +--------+   +--------+   +--------+   +--------+<--+
21   |                                                                    |
22   |   +--------+                                                       |
23   +---|header  |                                                       |
24       +--------+                                                       |
25       |tail    |-------------------------------------------------------+
26       +--------+
27       |length=4|
28       +--------+
29       |level=2 |
30       +--------+
31 /*

要删除节点d，生成的update数组为

 1 /*
 2 update
 3 +--------+
 4 |NULL    |
 5 +--------+
 6 |NULL    |
 7 +--------+
 8 |c       |
 9 +--------+
10 |c       |
11 +--------+
12 */

由于d的level为1，故在level[0]层，使用从单向链表中删除节点的操作，把d移出，再给高于level[0]的update数组中所有成员的span自减，节点少了，跨度要跟着降低。

删除d之后的跳表

 1 /*
 2       +--------+
 3       |level[3]|-->NULL
 4       |0       |
 5       +--------+
 6       |level[2]|-->NULL
 7       |0       |
 8       +--------+                +--------+   +--------+
 9       |level[1]|--------------->|level[1]|-->|level[1]|-->NULL
10       |2       |                |1       |   |0       |
11       +--------+   +--------+   +--------+   +--------+
12       |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
13       |1       |   |1       |   |1       |   |0       |
14       +--------+   +--------+   +--------+   +--------+
15 NULL<-|backward|   |backward|<--|backward|<--|backward|
16       +--------+   +--------+   +--------+   +--------+
17       |0       |   |2       |   |3       |   |5       |
18       +--------+   +--------+   +--------+   +--------+
19       |NULL    |   |b       |   |c       |   |e       |
20   +-->+--------+   +--------+   +--------+   +--------+<--+
21   |                                                       |
22   |   +--------+                                          |
23   +---|header  |                                          |
24       +--------+                                          |
25       |tail    |------------------------------------------+
26       +--------+
27       |length=3|
28       +--------+
29       |level=2 |
30       +--------+
31 /*

五、销毁

 1 /**
 2  * Free the specified skiplist node. The referenced SDS string representation
 3  * of the element is freed too, unless node->ele is set to NULL before calling
 4  * this function.
 5  * 释放指定跳跃节点的内存，需要释放成员变量ele的内存，然后再释放node，除非ele被设置为NULL
 6  */
 7 void zslFreeNode(zskiplistNode *node) {
 8     sdsfree(node->ele);
 9     zfree(node);
10 }
11 
12 /* Free a whole skiplist. 释放整个跳跃表*/
13 void zslFree(zskiplist *zsl) {
14     zskiplistNode *node = zsl->header->level[0].forward, *next;
15 
16     zfree(zsl->header);
17     while(node) {
18         next = node->level[0].forward;
19         zslFreeNode(node);
20         node = next;
21     }
22     zfree(zsl);
23 }

销毁操作本身只是在level[0]层遍历所有节点，依次销毁。

参考文章：

　　https://www.cnblogs.com/chinxi/p/12259603.html

这篇关于redis 5.0.2 源码阅读——跳跃表skiplist的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！