作者：YanChang顺风车运营研发团队node和list的定义如下：typedefstructzskiplistNode{sdsele;双倍分数；结构zskiplistNode*向后；结构zskiplistLevel{结构zskiplistNode*转发;无符号整数跨度；}level[];}zskiplistNode;typedefstructzskiplist{structzskiplistNode*header,*tail;无符号长长度；int级别;}zskiplist;1、节点创建：zskiplistNode*zslCreateNode(intlevel,doublescore,sdsele){zskiplistNode*zn=zmalloc(sizeof(*zn)+level*sizeof(structzskiplistLevel));zn->分数=分数；zn->ele=ele;returnzn;}从代码可以看出，创建节点的内存是节点本身的大小+level(structzskiplistLevel)size;2.createListfunction/*创建一个新的skiplist。*/zskiplist*zslCreate(void){intj;zskiplist*zsl;zsl=zmalloc(sizeof(*zsl));zsl->level=1;zsl->长度=0；zsl->header=zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);//新建一个节点，该节点的层级为32，得分为0for(j=0;jheader->level[j].forward=NULL;zsl->header->level[j].span=0;}zsl->header->backward=NULL;zsl->tail=NULL;returnzsl;}创建结果如图：3、zslInsert函数zskiplistNode*zslInsert(zskiplist*zsl,doublescore,sdsele){zskiplistNode*update[ZSKIPLIST_MAXLEVEL],*x;无符号整数等级[ZSKIPLIST_MAXLEVEL]；诠释我，水平；服务器断言（！isnan（分数））；x=zsl->标题；for(i=zsl->level-1;i>=0;i--){/*存储越过到达插入位置的rank*/rank[i]=i==(zsl->level-1）？0：等级[i+1]；while(x->level[i].forward&&(x->level[i].forward->scorelevel[i].forward->score==score&&sdscmp(x->level[i].forward->ele,ele)<0))){rank[i]+=x->level[i].span;x=x->level[i].forward;}更新[i]=x;}/*我们假设元素不在里面，因为我们允许重复*分数，重新插入相同的元素永远不会发生，因为zslInsert()的*调用者应该在哈希表中测试元素是否已经在里面。*/level=zslRandomLevel();如果（级别>zsl->级别）{对于（i=zsl->级别；我<级别；i++）{等级[i]=0；更新[i]=zsl->标题；update[i]->level[i].span=zsl->length;}zsl->级别=级别；}x=zslCreateNode(级别、分数、ele);对于(i=0;ilevel[i].forward=update[i]->level[i].forward;update[i]->level[i].forward=x;/*更新update[i]覆盖的范围，因为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;ilevel;i++){update[i]->level[i].span++;}x->backward=(update[0]==zsl->header)?空值：更新[0]；如果(x->level[0].forward)x->level[0].forward->backward=x;否则zsl->tail=x;zsl->长度++；returnx;}下面详细解释插入过程：1.插入节点：level=1,score=1line138:x=zsl->header,现在赋值x为header，参考图1中的139行：i=zsl->level-1===>0，所以这个for循环可以进入141行一次：i=0，zsl->level-1=0，两个值相等。所以rank[0]=0line142:x->level[0]->forward=NULL,所以这个while不能进入line150:update[0]=x,所以现在update[0]的值就是header了指向的节点是第156行。level=1第157行：zsl->level=1，所以这个if不能进入第165行：创建一个新节点节点x，level=1，score=1第166行：for循环你可以进入第167行一次：x->level[0]->forward=NULL第168行：update[0]->level[0].forward=x第171行：x->level[0].span=update[0]->level[0].span=0第172行：更新[0]->level[0].span=1第176行：for条件不满足180行：x->backward=NULL181行：条件不满足，进入else185行：zsl->length++2.插入level=1,score=2138行：x=zsl->header，现在赋x为header，参考图1中139行：i=zsl->level-1===>0，所以这个for循环可以进入141行一次：i=0,zsl->level-1=0，两个值相等。所以rank[0]=0Line142:x->level[0]->forward不为空，x->level[0].forward->score=1，小于2要插入，所以while可以enterline147：rank[0]=1line148：x=nodeinsertedinthepreviousstepline150：update[0]=nodeinsertedinthepreviousstepline156：level=1line157：zsl->level=1,所以这个if不能进入line165:createanewnodenodex,level=1,score=2line166:forloop可以进入line167once:x->level[0]->forward=NULLLine168:update[0]->level[0].forward=x第171行：x->level[0].span=update[0]->level[0].span=0第172行：update[0]->level[0].span=1line176:forconditionisnotsatisfiedline180:x->backward=update[0]line181:iftheconditionisnotsatisfied,gotoline185ofelse:zsl->length++3.Insertlevel=2,score=3line138:x=zsl->header，现在赋值x为header，参考图1中的139行：i=zsl->level-1===>0，所以这个for循环可以输入一次141行：i=0,zsl->level-1=0，两个值相等。所以rank[0]=0142行：x->level[0]->forward不为空，x->level[0].forward->score=1，小于要插入2，所以while可以进入，又因为x->level[0].forward->level[0]->foreard不为空，所以while可以循环两次147行：第一个while循环，rank[0]=1，第二个while循环，rank[0]=rank[0]+1=2line148:x=nodeinsertedinthepreviousstepline150:update[0]=nodeinsertedinthepreviousstep156Line:level=2Line157:level=2,zsl->level=1,所以这个if可以进入Line158:for循环可以进入一次Line159:rank[1]=0Line160:update[1]=headerline161:update[1]->level[1].span=zsl->length=2line163:zsl->level=2line165:createanewnodenodex,level=2,score=3line166:for循环可以进入两次第一次for循环：第167行：x->level[0]->forward=NULL第168行：update[0]->level[0].forward=x第171行：x->level[0].span=update[0]->level[0].span=0第172行：update[0]->level[0].span=1second第二个for循环：第167行：x->level[1]->forward=NULL第168行：update[1]->level[1].forward=x第171行：x->level[1]。span=update[1]->level[1].span=2第172行：update[1]->level[1].span=3第176行：条件不是满足第180行：update[0]!=zsl->header，所以x->backward=update[0]第181行：如果条件不满足第184行：zsl->header=x第185行：zsl->length++4.Insertlevel=2,score=1.5line138:x=zsl->header,现在赋x为header，参考图1中的139行：i=zsl->level-1===>1，所以这个对于循环可以进入两次第一个for循环第141行：i=1,zsl->level-1=0，两个值相等。所以rank[1]=0line142:x->level[1]->forward不为空，x->level[1].forward->score=3，大于0.5要插入，所以while无法进入line150:update[1]=headersecondforloopLine141:i=0,zsl->level-1=1,两个值不相等。所以rank[0]=rank[1]=0第142行：x->level[0]->forward不为空，x->level[0].forward->score=1，小于1.5为被插入，所以while可以输入line147:header->level[0].span=1,rank[0]+=1,所以rank[0]=1line148:x=header->level[0].forward，由于此时x的score=2，while循环不会进入line150:update[0]=before第一个插入的节点，即score=1的节点line156:level=2line157:level=2,zsl->level=2,所以这个if不能进入line165:createanewnodenodex,level=2,score=1.5line166:forloop可以进入两次firstforloop:line167:x->level[0]->forward=score为2的节点第168行：update[0]->level[0].forward=x第171行：x->level[0].span=update[0]->level[0].span=1第172行：update[0]->level[0].span=1秒for循环：第167行：x->level[1]->forward=score=3最后插入的节点第168行：update[1]->level[1].forward=x第171行：x->level[1].span=update[1]->level[1].span-(1-0)=2第172行：update[1]->level[1].span=(1-0)+1=2Line176:for条件不满足Line180:x->backward=update[0]Line181Line:如果条件满足Line182：score=2的节点的backward指向新生成的节点185行：length++至此我们就了解了跳表的插入过程。待续
