37源碼5步探索跳躍列表天下無魚

源碼5： 步——探索「跳 Redis的t是?個(gè)復(fù)合結(jié)構(gòu)，???它需要?個(gè)he和scoe的對(duì)應(yīng)關(guān)系，另???需要提供按照sce來排序的功能，還需要能夠指定e的范圍來獲取ezset的實(shí)現(xiàn)是?個(gè)hash字典加?個(gè)跳躍列表(skiplist)。hash結(jié)構(gòu)在講字典結(jié)構(gòu)時(shí)已經(jīng)詳細(xì)分析過了，它很類似于Java語?中的HashMap結(jié)構(gòu)。本節(jié)來講跳躍列表，它?較復(fù)雜，讀者要有?上圖就是跳躍列表的示意圖，圖中只畫了四層，Redis的跳躍表共有64層，容納2^64個(gè)元素應(yīng)該不成問題。每?個(gè)kv塊對(duì)應(yīng)的結(jié)構(gòu)如下?的代碼中的zslnode結(jié)構(gòu)，kvheader也是這個(gè)結(jié)構(gòu)，只不過value字段是null值——?效的，score是?來墊底的。kv之間使?指針串起來形成了雙向鏈表結(jié)構(gòu)，它們是有序排列的，從?到?。不同的kv層?可能不?樣，層數(shù)越?的kvkv會(huì)使?指針串起來。每?個(gè)層元素的遍歷都是從kvheader出發(fā)。structstruct{stringvalue;doublescore;zslnode*[forwards;zslnode*backward;}structzslzslnode*headerintmaxLevelmap<stringzslnode*hthash}位置節(jié)點(diǎn)(定位到最后?個(gè)?「 復(fù)雜度將會(huì)降到O(lg(n))。 要定位到那個(gè)紫?的kv，需要從header的最?層開始遍歷找到第?個(gè)節(jié)點(diǎn)(最后?個(gè)?「 節(jié)點(diǎn)開始降?層再遍歷找到第?個(gè)節(jié)點(diǎn)(最后?個(gè)?「 有了這個(gè)搜索路徑，就可以插?這個(gè)新節(jié)點(diǎn)了。不過這個(gè)插?過理的層數(shù)。直觀上期望的?標(biāo)是50%的Level1，25%的Level2，12.5%的Level3，?直到最頂層2^-63，因?yàn)檫@?每?層的晉升概率是50%。/*Returnsarandomlevelforthenewskiplistnodewearegoingtocreate.Thereturnvalueofthisfunctionisbetween1andZSKIPLIST_MAXLEVEL lusive),withapowerlaw-alikedistributionwherehigherlevelsarelesslikelytobereturned.*/intzslRandomLevel(void){intlevel=while((random()&0xFFFF)<(ZSKIPLIST_P*level+=return(level<ZSKIPLIST_MAXLEVEL)?level:}不過Redis標(biāo)準(zhǔn)源碼中的晉升概率只有25%，也就是代碼中的ZSKIPLIST_P的值。所以官?的跳躍列表更加的扁平化，層?相對(duì)較常浪費(fèi)。跳躍列表會(huì)記錄?下當(dāng)前的最?層數(shù)maxLevel，遍歷時(shí)從這個(gè)maxLevel開始遍歷性能就會(huì)提?很多。/*/*Insertanewnodeintheskiplist.Assumestheelementdoesnotalready*exist(uptothecallertoen that).TheskiplisttakesownershipofthepassedSDSstring'ele'.*/zskiplistNode*zslInsert(zskiplist*zsl,doublescore,sdsele){//搜索路zskiplistNode//經(jīng)過的節(jié)點(diǎn)跨unsignedintinti,x=zsl->header;for(i=zsl->level-1;i>=0;i--)/*storerankthatiscrossedtoreachtheinsertposition*/rank[i]=i==(zsl->level-1)?0:如果score相等，還需要?較while(x->level[i].forwardscore==score>ele,ele)<{

rank[i]+=x->level[i].span;x=x->level[i].forward;}update[i]=}/*weassumetheelementisnotalreadyinside,seweallowduplicatedscores,reinsertingthesameelementshouldneverhappensethecallerofzslInsert()shouldtestinthehashtableiftheelementisalreadyinsideornot.level=if(level>zsl->level)for(i=zsl->level;i<level;{rank[i]=0;update[i]=zsl->header;update[i]->level[i].span=}

}zsl->level=x=for(i=0;i<level;i++)x->level[i].forward=update[i]->level[i].forward=/*updatespancoveredbyupdate[i]asxisinsertedhere*/x->level[i].span=>level[i].span-(rank[0]-rank[i]);update[i]->level[i].span=(rank[0]-rank[i])+ rementspanforuntouchedlevels*/for(i=level;i<zsl->level;i++){x->backward=(update[0]==zsl->header)NULL:if(x-x->level[0].forward->backward=zsl->tail=return 調(diào)?zadd?法時(shí)，如果對(duì)應(yīng)的value不存在，那就是插?過程。如果這個(gè)value已經(jīng)存在了，只是調(diào)整?下score的值，那就需要??個(gè)更新的流程。假設(shè)這個(gè)新的score值不會(huì)帶來排序位置上的改變，那么就不需要調(diào)整位置，直接修改元素的score值就/*Removeandre-insertwhenscorechanges.*/if(score!=curscore){zskiplistNode*node;znode=zslInsert(zs-/*Wereusedthenode->eleSDSthenode ezslInsertcreatedanewone.*/node->ele=NULL; /*Notethatwedidnotremovedtheoriginalelementfromthehashtablerepresentingthesortedset,sowejustupdatethescore.dictGetVal(de)=&znode->score;/*Updatescoreptr.*/*flags|=}return次路徑搜索。Redis就是這么?的。不過Redis遇到score置是否需要調(diào)整，從這點(diǎn)看，Redis的zadd的代碼似乎還有優(yōu)化空如果score在?個(gè)的情況下，zset中所有的score值都是?樣的，zset的查找性能會(huì)為O(n)么？Redis作者?然考慮到了這?點(diǎn)，所以zset的排序元素不只看score值，如果score值相同還需要再?較value值(字符串?較)。 zset可以獲取元素的rank。那這個(gè)rank是如何算出來的？如果僅僅使?上?的結(jié)構(gòu)，rank是不能算出來的。Redis在skiplist的forward指針上進(jìn)?了優(yōu)化，給每?個(gè)forward指針都增加了span屬性，span是「跨度」的意思，表示從前?個(gè)節(jié)點(diǎn)沿著當(dāng)前層的forward指針跳到當(dāng)前這個(gè)節(jié)點(diǎn)中間會(huì)跳過多少個(gè)節(jié)點(diǎn)。Redis在插?刪除操作時(shí)會(huì)??翼翼地更新span值的??。structstruct{zslnode*item;longspan;跨度}struct{Stringvalue;doublescore;zslforward*[forwards;zslnode*backward;} 要計(jì)算?個(gè)元素的時(shí)，只需要將「搜索路徑」上的經(jīng)過的所有節(jié)點(diǎn)的跨度span值進(jìn)?疊加就可以算出元素的最終rank 提到當(dāng)score值的變化微?，不會(huì)帶來位置上的調(diào)整時(shí)，是不是可以直接修改score后就返回？作者Antirez提