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