Redis為什么用跳表而不用平衡樹？
Redis里面使用skiplist是為了實現sorted set這種對外的數據結構。sorted
set提供的操作非常豐富僚楞，可以滿足非常多的應用場景吗浩。這也意味著，sorted
set相對來說實現比較復雜旷偿。同時，skiplist這種數據結構對于很多人來說都比較陌生爆侣，因為大部分學校里的算法課都沒有對這種數據結構進行過詳細的介紹萍程。因此，為了介紹得足夠清楚兔仰，本文會比這個系列的其它幾篇花費更多的篇幅茫负。
我們將大體分成三個部分進行介紹：
介紹經典的skiplist數據結構，并進行簡單的算法分析乎赴。這一部分的介紹忍法，與Redis沒有直接關系。我會嘗試盡量使用通俗易懂的語言進行描述榕吼。
討論Redis里的skiplist的具體實現饿序。為了支持sorted set本身的一些要求，在經典的skiplist基礎上羹蚣，Redis里的相應實現做了若干改動原探。
討論sorted set是如何在skiplist, dict和ziplist基礎上構建起來的。
我們在討論中還會涉及到兩個Redis配置（在redis.conf中的ADVANCED CONFIG部分）：
zset-max-ziplist-entries128
zset-max-ziplist-value64
我們在討論中會詳細解釋這兩個配置的含義顽素。
注：本文討論的代碼實現基于Redis源碼的3.2分支咽弦。
skiplist本質上也是一種查找結構，用于解決算法中的查找問題（Searching）胁出，即根據給定的key型型，快速查到它所在的位置（或者對應的value）。
我們在《Redis內部數據結構詳解》系列的第一篇中介紹dict的時候全蝶，曾經討論過：一般查找問題的解法分為兩個大類：一個是基于各種平衡樹闹蒜，一個是基于哈希表寺枉。但skiplist卻比較特殊，它沒法歸屬到這兩大類里面嫂用。
這種數據結構是由William Pugh發(fā)明的型凳，最早出現于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》丈冬。對細節(jié)感興趣的同學可以下載論文原文來閱讀嘱函。
skiplist，顧名思義埂蕊，首先它是一個list往弓。實際上，它是在有序鏈表的基礎上發(fā)展起來的蓄氧。
我們先來看一個有序鏈表函似，如下圖（最左側的灰色節(jié)點表示一個空的頭結點）：
在這樣一個鏈表中，如果我們要查找某個數據喉童，那么需要從頭開始逐個進行比較撇寞，直到找到包含數據的那個節(jié)點，或者找到第一個比給定數據大的節(jié)點為止（沒找到）堂氯。也就是說蔑担，時間復雜度為O(n)。同樣咽白，當我們要插入新數據的時候啤握，也要經歷同樣的查找過程，從而確定插入位置晶框。
假如我們每相鄰兩個節(jié)點增加一個指針排抬，讓指針指向下下個節(jié)點，如下圖：
這樣所有新增加的指針連成了一個新的鏈表授段，但它包含的節(jié)點個數只有原來的一半（上圖中是7, 19,
26）《灼眩現在當我們想查找數據的時候，可以先沿著這個新鏈表進行查找侵贵。當碰到比待查數據大的節(jié)點時届搁，再回到原來的鏈表中進行查找。比如模燥，我們想查找23咖祭，查找的路徑是沿著下圖中標紅的指針所指向的方向進行的：
23首先和7比較，再和19比較蔫骂，比它們都大么翰，繼續(xù)向后比較。
但23和26比較的時候辽旋，比26要小浩嫌，因此回到下面的鏈表（原鏈表）檐迟，與22比較。
23比22要大码耐，沿下面的指針繼續(xù)向后和26比較追迟。23比26小，說明待查數據23在原鏈表中不存在骚腥，而且它的插入位置應該在22和26之間敦间。
在這個查找過程中，由于新增加的指針束铭，我們不再需要與鏈表中每個節(jié)點逐個進行比較了廓块。需要比較的節(jié)點數大概只有原來的一半。
利用同樣的方式契沫，我們可以在上層新產生的鏈表上带猴，繼續(xù)為每相鄰的兩個節(jié)點增加一個指針，從而產生第三層鏈表懈万。如下圖：
在這個新的三層鏈表結構上拴清，如果我們還是查找23，那么沿著最上層鏈表首先要比較的是19会通，發(fā)現23比19大口予，接下來我們就知道只需要到19的后面去繼續(xù)查找，從而一下子跳過了19前面的所有節(jié)點渴语∑煌可以想象，當鏈表足夠長的時候驾凶，這種多層鏈表的查找方式能讓我們跳過很多下層節(jié)點牙甫，大大加快查找的速度。
skiplist正是受這種多層鏈表的想法的啟發(fā)而設計出來的调违。實際上窟哺，按照上面生成鏈表的方式，上面每一層鏈表的節(jié)點個數技肩，是下面一層的節(jié)點個數的一半且轨，這樣查找過程就非常類似于一個二分查找，使得查找的時間復雜度可以降低到O(log
n)虚婿。但是旋奢，這種方法在插入數據的時候有很大的問題。新插入一個節(jié)點之后然痊，就會打亂上下相鄰兩層鏈表上節(jié)點個數嚴格的2:1的對應關系至朗。如果要維持這種對應關系，就必須把新插入的節(jié)點后面的所有節(jié)點（也包括新插入的節(jié)點）重新進行調整剧浸，這會讓時間復雜度重新蛻化成O(n)锹引。刪除數據也有同樣的問題矗钟。
skiplist為了避免這一問題，它不要求上下相鄰兩層鏈表之間的節(jié)點個數有嚴格的對應關系嫌变，而是為每個節(jié)點隨機出一個層數(level)吨艇。比如，一個節(jié)點隨機出的層數是3腾啥，那么就把它鏈入到第1層到第3層這三層鏈表中东涡。為了表達清楚赛不，下圖展示了如何通過一步步的插入操作從而形成一個skiplist的過程（點擊看大圖）：
從上面skiplist的創(chuàng)建和插入過程可以看出槽唾，每一個節(jié)點的層數（level）是隨機出來的，而且新插入一個節(jié)點不會影響其它節(jié)點的層數。因此延柠，插入操作只需要修改插入節(jié)點前后的指針，而不需要對很多節(jié)點都進行調整锣披。這就降低了插入操作的復雜度贞间。實際上，這是skiplist的一個很重要的特性雹仿，這讓它在插入性能上明顯優(yōu)于平衡樹的方案增热。這在后面我們還會提到。
根據上圖中的skiplist結構胧辽，我們很容易理解這種數據結構的名字的由來峻仇。skiplist，翻譯成中文邑商，可以翻譯成“跳表”或“跳躍表”摄咆，指的就是除了最下面第1層鏈表之外，它會產生若干層稀疏的鏈表人断，這些鏈表里面的指針故意跳過了一些節(jié)點（而且越高層的鏈表跳過的節(jié)點越多）吭从。這就使得我們在查找數據的時候能夠先在高層的鏈表中進行查找，然后逐層降低恶迈，最終降到第1層鏈表來精確地確定數據位置涩金。在這個過程中，我們跳過了一些節(jié)點暇仲，從而也就加快了查找速度步做。
剛剛創(chuàng)建的這個skiplist總共包含4層鏈表，現在假設我們在它里面依然查找23奈附，下圖給出了查找路徑：
需要注意的是全度，前面演示的各個節(jié)點的插入過程，實際上在插入之前也要先經歷一個類似的查找過程桅狠，在確定插入位置后讼载，再完成插入操作轿秧。
至此，skiplist的查找和插入操作咨堤，我們已經很清楚了菇篡。而刪除操作與插入操作類似，我們也很容易想象出來一喘。這些操作我們也應該能很容易地用代碼實現出來驱还。
當然，實際應用中的skiplist每個節(jié)點應該包含key和value兩部分凸克。前面的描述中我們沒有具體區(qū)分key和value议蟆，但實際上列表中是按照key進行排序的，查找過程也是根據key在比較萎战。
但是咐容，如果你是第一次接觸skiplist，那么一定會產生一個疑問：節(jié)點插入時隨機出一個層數蚂维，僅僅依靠這樣一個簡單的隨機數操作而構建出來的多層鏈表結構戳粒，能保證它有一個良好的查找性能嗎？為了回答這個疑問虫啥，我們需要分析skiplist的統(tǒng)計性能蔚约。
在分析之前，我們還需要著重指出的是涂籽，執(zhí)行插入操作時計算隨機數的過程苹祟，是一個很關鍵的過程，它對skiplist的統(tǒng)計特性有著很重要的影響评雌。這并不是一個普通的服從均勻分布的隨機數树枫，它的計算過程如下：
首先，每個節(jié)點肯定都有第1層指針（每個節(jié)點都在第1層鏈表里）柳骄。
如果一個節(jié)點有第i層(i>=1)指針（即節(jié)點已經在第1層到第i層鏈表中）团赏，那么它有第(i+1)層指針的概率為p。
節(jié)點最大的層數不允許超過一個最大值耐薯，記為MaxLevel舔清。
這個計算隨機層數的偽碼如下所示：
randomLevel()
level :=1
// random()返回一個[0...1)的隨機數
whilerandom()< pandlevel < MaxLeveldolevel := level +1returnlevel
randomLevel()的偽碼中包含兩個參數，一個是p曲初，一個是MaxLevel体谒。在Redis的skiplist實現中，這兩個參數的取值為：
p =1/4
MaxLevel =32
在這一部分臼婆，我們來簡單分析一下skiplist的時間復雜度和空間復雜度抒痒，以便對于skiplist的性能有一個直觀的了解。如果你不是特別偏執(zhí)于算法的性能分析颁褂，那么可以暫時跳過這一小節(jié)的內容故响。
我們先來計算一下每個節(jié)點所包含的平均指針數目（概率期望）傀广。節(jié)點包含的指針數目，相當于這個算法在空間上的額外開銷(overhead)彩届，可以用來度量空間復雜度伪冰。
根據前面randomLevel()的偽碼，我們很容易看出樟蠕，產生越高的節(jié)點層數贮聂，概率越低。定量的分析如下：
節(jié)點層數至少為1寨辩。而大于1的節(jié)點層數吓懈，滿足一個概率分布。
節(jié)點層數恰好等于1的概率為1-p靡狞。
節(jié)點層數大于等于2的概率為p耻警，而節(jié)點層數恰好等于2的概率為p(1-p)。
節(jié)點層數大于等于3的概率為p2耍攘，而節(jié)點層數恰好等于3的概率為p2(1-p)榕栏。
節(jié)點層數大于等于4的概率為p3，而節(jié)點層數恰好等于4的概率為p3(1-p)蕾各。
......
因此，一個節(jié)點的平均層數（也即包含的平均指針數目）庆揪，計算如下：
現在很容易計算出：
當p=1/2時式曲，每個節(jié)點所包含的平均指針數目為2；
當p=1/4時缸榛，每個節(jié)點所包含的平均指針數目為1.33吝羞。這也是Redis里的skiplist實現在空間上的開銷。
接下來内颗，為了分析時間復雜度钧排，我們計算一下skiplist的平均查找長度。查找長度指的是查找路徑上跨越的跳數均澳，而查找過程中的比較次數就等于查找長度加1恨溜。以前面圖中標出的查找23的查找路徑為例，從左上角的頭結點開始找前，一直到結點22糟袁，查找長度為6。
為了計算查找長度躺盛，這里我們需要利用一點小技巧项戴。我們注意到，每個節(jié)點插入的時候槽惫，它的層數是由隨機函數randomLevel()計算出來的周叮，而且隨機的計算不依賴于其它節(jié)點辩撑，每次插入過程都是完全獨立的。所以仿耽，從統(tǒng)計上來說槐臀，一個skiplist結構的形成與節(jié)點的插入順序無關。
這樣的話氓仲，為了計算查找長度水慨，我們可以將查找過程倒過來看，從右下方第1層上最后到達的那個節(jié)點開始敬扛，沿著查找路徑向左向上回溯晰洒，類似于爬樓梯的過程。我們假設當回溯到某個節(jié)點的時候啥箭，它才被插入谍珊，這雖然相當于改變了節(jié)點的插入順序，但從統(tǒng)計上不影響整個skiplist的形成結構急侥。
現在假設我們從一個層數為i的節(jié)點x出發(fā)砌滞，需要向左向上攀爬k層。這時我們有兩種可能：
如果節(jié)點x有第(i+1)層指針坏怪，那么我們需要向上走贝润。這種情況概率為p。
如果節(jié)點x沒有第(i+1)層指針铝宵，那么我們需要向左走打掘。這種情況概率為(1-p)。
這兩種情形如下圖所示：
用C(k)表示向上攀爬k個層級所需要走過的平均查找路徑長度（概率期望）鹏秋，那么：
C(0)=0
C(k)=(1-p)×(上圖中情況b的查找長度) + p×(上圖中情況c的查找長度)
代入尊蚁，得到一個差分方程并化簡：
C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
C(k)=1/p+C(k-1)
C(k)=k/p
這個結果的意思是，我們每爬升1個層級侣夷，需要在查找路徑上走1/p步横朋。而我們總共需要攀爬的層級數等于整個skiplist的總層數-1。
那么接下來我們需要分析一下當skiplist中有n個節(jié)點的時候百拓，它的總層數的概率均值是多少琴锭。這個問題直觀上比較好理解。根據節(jié)點的層數隨機算法耐版，容易得出：
第1層鏈表固定有n個節(jié)點祠够；
第2層鏈表平均有n*p個節(jié)點；
第3層鏈表平均有n*p2個節(jié)點粪牲；
...
所以古瓤，從第1層到最高層，各層鏈表的平均節(jié)點數是一個指數遞減的等比數列。容易推算出落君，總層數的均值為log1/pn穿香，而最高層的平均節(jié)點數為1/p。
綜上绎速，粗略來計算的話皮获，平均查找長度約等于：
C(log1/pn-1)=(log1/pn-1)/p
即，平均時間復雜度為O(log n)纹冤。
當然洒宝，這里的時間復雜度分析還是比較粗略的。比如萌京，沿著查找路徑向左向上回溯的時候雁歌，可能先到達左側頭結點，然后沿頭結點一路向上知残；還可能先到達最高層的節(jié)點靠瞎，然后沿著最高層鏈表一路向左。但這些細節(jié)不影響平均時間復雜度的最后結果求妹。另外乏盐，這里給出的時間復雜度只是一個概率平均值，但實際上計算一個精細的概率分布也是有可能的制恍。詳情還請參見William
Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》父能。
skiplist和各種平衡樹（如AVL吧趣、紅黑樹等）的元素是有序排列的法竞，而哈希表不是有序的。因此强挫，在哈希表上只能做單個key的查找，不適宜做范圍查找薛躬。所謂范圍查找俯渤，指的是查找那些大小在指定的兩個值之間的所有節(jié)點。
在做范圍查找的時候型宝，平衡樹比skiplist操作要復雜八匠。在平衡樹上，我們找到指定范圍的小值之后趴酣，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點梨树。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現岖寞。而在skiplist上進行范圍查找就非常簡單抡四，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。
平衡樹的插入和刪除操作可能引發(fā)子樹的調整指巡，邏輯復雜淑履，而skiplist的插入和刪除只需要修改相鄰節(jié)點的指針，操作簡單又快速藻雪。
從內存占用上來說秘噪，skiplist比平衡樹更靈活一些。一般來說勉耀，平衡樹每個節(jié)點包含2個指針（分別指向左右子樹）指煎，而skiplist每個節(jié)點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小便斥。如果像Redis里的實現一樣至壤，取p=1/4，那么平均每個節(jié)點包含1.33個指針椭住，比平衡樹更有優(yōu)勢崇渗。
查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)京郑，大體相當宅广；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)些举，性能更高一些跟狱。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現的户魏。
從算法實現難度上來比較驶臊，skiplist比平衡樹要簡單得多。
在這一部分叼丑，我們討論Redis中的skiplist實現关翎。
在Redis中，skiplist被用于實現暴露給外部的一個數據結構：sorted set鸠信。準確地說纵寝，sorted
set底層不僅僅使用了skiplist，還使用了ziplist和dict星立。這幾個數據結構的關系爽茴，我們下一章再討論。現在绰垂，我們先花點時間把sorted
set的關鍵命令看一下室奏。這些命令對于Redis里skiplist的實現，有重要的影響劲装。
sorted set的命令舉例
sorted set是一個有序的數據集合胧沫，對于像類似排行榜這樣的應用場景特別適合昌简。
現在我們來看一個例子，用sorted set來存儲代數課（algebra）的成績表琳袄。原始數據如下：
Alice 87.5
Bob 89.0
Charles 65.5
David 78.0
Emily 93.5
Fred 87.5
這份數據給出了每位同學的名字和分數江场。下面我們將這份數據存儲到sorted set里面去：
對于上面的這些命令，我們需要的注意的地方包括：
前面的6個zadd命令窖逗，將6位同學的名字和分數(score)都輸入到一個key值為algebra的sorted set里面了址否。注意Alice和Fred的分數相同，都是87.5分碎紊。
zrevrank命令查詢Alice的排名（命令中的rev表示按照倒序排列佑附，也就是從大到小）仗考，返回3音同。排在Alice前面的分別是Emily、Bob秃嗜、Fred权均，而排名(rank)從0開始計數，所以Alice的排名是3锅锨。注意叽赊，其實Alice和Fred的分數相同，這種情況下sorted
set會把分數相同的元素必搞，按照字典順序來排列必指。按照倒序，Fred排在了Alice的前面恕洲。
zscore命令查詢了Charles對應的分數塔橡。
zrevrange命令查詢了從大到小排名為0~3的4位同學。
zrevrangebyscore命令查詢了分數在80.0和90.0之間的所有同學霜第，并按分數從大到小排列葛家。
總結一下，sorted set中的每個元素主要表現出3個屬性：
數據本身（在前面的例子中我們把名字存成了數據）泌类。
每個數據對應一個分數(score)惦银。
根據分數大小和數據本身的字典排序，每個數據會產生一個排名(rank)末誓。可以按正序或倒序书蚪。
Redis中skiplist實現的特殊性
我們簡單分析一下前面出現的幾個查詢命令：
zrevrank由數據查詢它對應的排名喇澡，這在前面介紹的skiplist中并不支持。
zscore由數據查詢它對應的分數殊校，這也不是skiplist所支持的晴玖。
zrevrange根據一個排名范圍，查詢排名在這個范圍內的數據。這在前面介紹的skiplist中也不支持呕屎。
zrevrangebyscore根據分數區(qū)間查詢數據集合让簿，是一個skiplist所支持的典型的范圍查找（score相當于key）。
實際上秀睛，Redis中sorted set的實現是這樣的：
當數據較少時尔当，sorted set是由一個ziplist來實現的。
當數據多的時候蹂安，sorted set是由一個dict + 一個skiplist來實現的椭迎。簡單來講，dict用來查詢數據到分數的對應關系田盈，而skiplist用來根據分數查詢數據（可能是范圍查找）畜号。
這里sorted set的構成我們在下一章還會再詳細地討論。現在我們集中精力來看一下sorted set與skiplist的關系允瞧，：
zscore的查詢简软，不是由skiplist來提供的，而是由那個dict來提供的述暂。
為了支持排名(rank)痹升，Redis里對skiplist做了擴展，使得根據排名能夠快速查到數據贸典，或者根據分數查到數據之后视卢，也同時很容易獲得排名。而且廊驼，根據排名的查找据过，時間復雜度也為O(log n)。
zrevrange的查詢妒挎，是根據排名查數據绳锅，由擴展后的skiplist來提供。
zrevrank是先在dict中由數據查到分數酝掩，再拿分數到skiplist中去查找鳞芙，查到后也同時獲得了排名。
前述的查詢過程期虾，也暗示了各個操作的時間復雜度：
zscore只用查詢一個dict原朝，所以時間復雜度為O(1)
zrevrank, zrevrange,
zrevrangebyscore由于要查詢skiplist，所以zrevrank的時間復雜度為O(log n)镶苞，而zrevrange,
zrevrangebyscore的時間復雜度為O(log(n)+M)喳坠，其中M是當前查詢返回的元素個數。
總結起來茂蚓，Redis中的skiplist跟前面介紹的經典的skiplist相比壕鹉，有如下不同：
分數(score)允許重復剃幌，即skiplist的key允許重復。這在最開始介紹的經典skiplist中是不允許的晾浴。
在比較時负乡，不僅比較分數（相當于skiplist的key），還比較數據本身脊凰。在Redis的skiplist實現中抖棘，數據本身的內容唯一標識這份數據，而不是由key來唯一標識笙各。另外钉答，當多個元素分數相同的時候，還需要根據數據內容來進字典排序杈抢。
第1層鏈表不是一個單向鏈表数尿，而是一個雙向鏈表。這是為了方便以倒序方式獲取一個范圍內的元素惶楼。
在skiplist中可以很方便地計算出每個元素的排名(rank)右蹦。
skiplist的數據結構定義
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25
typedefstructzskiplistNode{
? ? robj *obj;
doublescore;
structzskiplistNode*backward;
structzskiplistLevel{
structzskiplistNode*forward;
unsignedintspan;
? ? } level[];
} zskiplistNode;
typedefstructzskiplist{
structzskiplistNode*header, *tail;
unsignedlonglength;
intlevel;
} zskiplist;
這段代碼出自server.h，我們來簡要分析一下：
開頭定義了兩個常量歼捐，ZSKIPLIST_MAXLEVEL和ZSKIPLIST_P何陆，分別對應我們前面講到的skiplist的兩個參數：一個是MaxLevel，一個是p豹储。
zskiplistNode定義了skiplist的節(jié)點結構贷盲。
obj字段存放的是節(jié)點數據，它的類型是一個string
robj剥扣。本來一個string
robj可能存放的不是sds巩剖，而是long型，但zadd命令在將數據插入到skiplist里面之前先進行了解碼钠怯，所以這里的obj字段里存儲的一定是一個sds佳魔。這樣做的目的應該是為了方便在查找的時候對數據進行字典序的比較，而且晦炊，skiplist里的數據部分是數字的可能性也比較小鞠鲜。
score字段是數據對應的分數。
backward字段是指向鏈表前一個節(jié)點的指針（前向指針）断国。節(jié)點只有1個前向指針贤姆，所以只有第1層鏈表是一個雙向鏈表。
level[]存放指向各層鏈表后一個節(jié)點的指針（后向指針）稳衬。每層對應1個后向指針庐氮，用forward字段表示。另外宋彼，每個后向指針還對應了一個span值弄砍，它表示當前的指針跨越了多少個節(jié)點。span用于計算元素排名(rank)输涕，這正是前面我們提到的Redis對于skiplist所做的一個擴展音婶。需要注意的是，level[]是一個柔性數組（flexible
array
member）莱坎，因此它占用的內存不在zskiplistNode結構里面衣式，而需要插入節(jié)點的時候單獨為它分配。也正因為如此檐什，skiplist的每個節(jié)點所包含的指針數目才是不固定的碴卧，我們前面分析過的結論——skiplist每個節(jié)點包含的指針數目平均為1/(1-p)——才能有意義。
zskiplist定義了真正的skiplist結構乃正，它包含：
頭指針header和尾指針tail住册。
鏈表長度length，即鏈表包含的節(jié)點總數瓮具。注意荧飞，新創(chuàng)建的skiplist包含一個空的頭指針，這個頭指針不包含在length計數中名党。
level表示skiplist的總層數叹阔，即所有節(jié)點層數的最大值。
下圖以前面插入的代數課成績表為例传睹，展示了Redis中一個skiplist的可能結構（點擊看大圖）：
注意：圖中前向指針上面括號中的數字耳幢，表示對應的span的值。即當前指針跨越了多少個節(jié)點欧啤，這個計數不包括指針的起點節(jié)點睛藻，但包括指針的終點節(jié)點。
假設我們在這個skiplist中查找score=89.0的元素（即Bob的成績數據）堂油，在查找路徑中修档，我們會跨域圖中標紅的指針，這些指針上面的span值累加起來府框，就得到了Bob的排名(2+2+1)-1=4（減1是因為rank值以0起始）吱窝。需要注意這里算的是從小到大的排名，而如果要算從大到小的排名迫靖，只需要用skiplist長度減去查找路徑上的span累加值院峡，即6-(2+2+1)=1。
可見系宜，在查找skiplist的過程中照激，通過累加span值的方式，我們就能很容易算出排名盹牧。相反俩垃，如果指定排名來查找數據（類似zrange和zrevrange那樣）励幼，也可以不斷累加span并時刻保持累加值不超過指定的排名，通過這種方式就能得到一條O(log
n)的查找路徑口柳。
我們前面提到過苹粟，Redis中的sorted set，是在skiplist, dict和ziplist基礎上構建起來的:
當數據較少時跃闹，sorted set是由一個ziplist來實現的嵌削。
當數據多的時候，sorted set是由一個叫zset的數據結構來實現的望艺，這個zset包含一個dict + 一個skiplist苛秕。dict用來查詢數據到分數(score)的對應關系，而skiplist用來根據分數查詢數據（可能是范圍查找）找默。
在這里我們先來討論一下前一種情況——基于ziplist實現的sorted
set艇劫。在本系列前面關于ziplist的文章里，我們介紹過啡莉，ziplist就是由很多數據項組成的一大塊連續(xù)內存港准。由于sorted
set的每一項元素都由數據和score組成，因此咧欣，當使用zadd命令插入一個(數據,
score)對的時候浅缸，底層在相應的ziplist上就插入兩個數據項：數據在前，score在后魄咕。
ziplist的主要優(yōu)點是節(jié)省內存衩椒，但它上面的查找操作只能按順序查找（可以正序也可以倒序）。因此哮兰，sorted set的各個查詢操作毛萌，就是在ziplist上從前向后（或從后向前）一步步查找，每一步前進兩個數據項喝滞，跨域一個(數據, score)對阁将。
隨著數據的插入，sorted set底層的這個ziplist就可能會轉成zset的實現（轉換過程詳見t_zset.c的zsetConvert）右遭。那么到底插入多少才會轉呢做盅？
還記得本文開頭提到的兩個Redis配置嗎？
zset-max-ziplist-entries128
zset-max-ziplist-value64
這個配置的意思是說窘哈，在如下兩個條件之一滿足的時候吹榴，ziplist會轉成zset（具體的觸發(fā)條件參見t_zset.c中的zaddGenericCommand相關代碼）：
當sorted set中的元素個數，即(數據, score)對的數目超過128的時候滚婉，也就是ziplist數據項超過256的時候图筹。
當sorted set中插入的任意一個數據的長度超過了64的時候。
最后，zset結構的代碼定義如下：
typedefstructzset{dict *dict; zskiplist *zsl; } zset;
在前面我們對于skiplist和平衡樹扣溺、哈希表的比較中，其實已經不難看出Redis里使用skiplist而不用平衡樹的原因了∶袼蓿現在我們看看娇妓，對于這個問題，Redis的作者 @antirez 是怎么說的：
There are a few reasons:
1) They are not very memory intensive. It's up to you basically.
Changing parameters about the probability of a node to have a given
number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations,
that is, traversing the skip list as a linked list. With this operation
the cache locality of skip lists is at least as good as with other kind
of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance
thanks to the skip list simplicity I received a patch (already in Redis
master) with augmented skip lists implementing ZRANK in O(log(N)). It
required little changes to the code.
這里從內存占用活鹰、對范圍查找的支持和實現難易程度這三方面總結的原因，我們在前面其實也都涉及到了只估。
