redis之跳躍表

Redis里面使用skiplist是為了實(shí)現(xiàn)sorted set這種對(duì)外的數(shù)據(jù)結(jié)構(gòu)。sorted set提供的操作非常豐富，可以滿足非常多的應(yīng)用場(chǎng)景。這也意味著绍些，sorted set相對(duì)來說實(shí)現(xiàn)比較復(fù)雜。同時(shí)耀鸦，skiplist這種數(shù)據(jù)結(jié)構(gòu)對(duì)于很多人來說都比較陌生柬批，因?yàn)榇蟛糠謱W(xué)校里的算法課都沒有對(duì)這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行過詳細(xì)的介紹。

我們將大體分成三個(gè)部分進(jìn)行介紹：

介紹經(jīng)典的skiplist數(shù)據(jù)結(jié)構(gòu)袖订，并進(jìn)行簡單的算法分析氮帐。這一部分的介紹，與Redis沒有直接關(guān)系著角。我會(huì)嘗試盡量使用通俗易懂的語言進(jìn)行描述揪漩。
討論Redis里的skiplist的具體實(shí)現(xiàn)旋恼。為了支持sorted set本身的一些要求吏口，在經(jīng)典的skiplist基礎(chǔ)上，Redis里的相應(yīng)實(shí)現(xiàn)做了若干改動(dòng)冰更。
討論sorted set是如何在skiplist, dict和ziplist基礎(chǔ)上構(gòu)建起來的产徊。

我們?cè)谟懻撝羞€會(huì)涉及到兩個(gè)Redis配置（在redis.conf中的ADVANCED CONFIG部分）：

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

我們?cè)谟懻撝袝?huì)詳細(xì)解釋這兩個(gè)配置的含義。

skiplist數(shù)據(jù)結(jié)構(gòu)簡介

skiplist本質(zhì)上也是一種查找結(jié)構(gòu)蜀细，用于解決算法中的查找問題（Searching）舟铜，即根據(jù)給定的key，快速查到它所在的位置（或者對(duì)應(yīng)的value）奠衔。一般查找問題的解法分為兩個(gè)大類：一個(gè)是基于各種平衡樹谆刨，一個(gè)是基于哈希表。但skiplist卻比較特殊归斤，它沒法歸屬到這兩大類里面痊夭。

這種數(shù)據(jù)結(jié)構(gòu)是由William Pugh發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》脏里。對(duì)細(xì)節(jié)感興趣的同學(xué)可以下載論文原文來閱讀她我。

skiplist，顧名思義，首先它是一個(gè)list番舆。實(shí)際上酝碳，它是在有序鏈表的基礎(chǔ)上發(fā)展起來的。

我們先來看一個(gè)有序鏈表恨狈，如下圖（最左側(cè)的灰色節(jié)點(diǎn)表示一個(gè)空的頭結(jié)點(diǎn)）：

image.png

在這樣一個(gè)鏈表中疏哗，如果我們要查找某個(gè)數(shù)據(jù)，那么需要從頭開始逐個(gè)進(jìn)行比較禾怠，直到找到包含數(shù)據(jù)的那個(gè)節(jié)點(diǎn)沃斤，或者找到第一個(gè)比給定數(shù)據(jù)大的節(jié)點(diǎn)為止（沒找到）。也就是說刃宵，時(shí)間復(fù)雜度為O(n)衡瓶。同樣，當(dāng)我們要插入新數(shù)據(jù)的時(shí)候牲证，也要經(jīng)歷同樣的查找過程哮针，從而確定插入位置。

假如我們每相鄰兩個(gè)節(jié)點(diǎn)增加一個(gè)指針坦袍，讓指針指向下下個(gè)節(jié)點(diǎn)十厢，如下圖：

image.png

這樣所有新增加的指針連成了一個(gè)新的鏈表，但它包含的節(jié)點(diǎn)個(gè)數(shù)只有原來的一半（上圖中是7, 19, 26）∥嫫耄現(xiàn)在當(dāng)我們想查找數(shù)據(jù)的時(shí)候蛮放，可以先沿著這個(gè)新鏈表進(jìn)行查找。當(dāng)碰到比待查數(shù)據(jù)大的節(jié)點(diǎn)時(shí)奠宜，再回到原來的鏈表中進(jìn)行查找包颁。比如，我們想查找23压真，查找的路徑是沿著下圖中標(biāo)紅的指針?biāo)赶虻姆较蜻M(jìn)行的：

image.png

23首先和7比較娩嚼，再和19比較，比它們都大滴肿，繼續(xù)向后比較岳悟。
但23和26比較的時(shí)候，比26要小泼差，因此回到下面的鏈表（原鏈表）贵少，與22比較。
23比22要大堆缘，沿下面的指針繼續(xù)向后和26比較滔灶。23比26小，說明待查數(shù)據(jù)23在原鏈表中不存在套啤，而且它的插入位置應(yīng)該在22和26之間宽气。

在這個(gè)查找過程中随常，由于新增加的指針，我們不再需要與鏈表中每個(gè)節(jié)點(diǎn)逐個(gè)進(jìn)行比較了萄涯。需要比較的節(jié)點(diǎn)數(shù)大概只有原來的一半绪氛。

利用同樣的方式，我們可以在上層新產(chǎn)生的鏈表上涝影，繼續(xù)為每相鄰的兩個(gè)節(jié)點(diǎn)增加一個(gè)指針枣察，從而產(chǎn)生第三層鏈表。如下圖

image.png

在這個(gè)新的三層鏈表結(jié)構(gòu)上燃逻，如果我們還是查找23序目，那么沿著最上層鏈表首先要比較的是19，發(fā)現(xiàn)23比19大伯襟，接下來我們就知道只需要到19的后面去繼續(xù)查找猿涨，從而一下子跳過了19前面的所有節(jié)點(diǎn)∧饭郑可以想象叛赚，當(dāng)鏈表足夠長的時(shí)候，這種多層鏈表的查找方式能讓我們跳過很多下層節(jié)點(diǎn)稽揭，大大加快查找的速度俺附。

skiplist正是受這種多層鏈表的想法的啟發(fā)而設(shè)計(jì)出來的。實(shí)際上溪掀，按照上面生成鏈表的方式事镣，上面每一層鏈表的節(jié)點(diǎn)個(gè)數(shù)，是下面一層的節(jié)點(diǎn)個(gè)數(shù)的一半揪胃，這樣查找過程就非常類似于一個(gè)二分查找璃哟，使得查找的時(shí)間復(fù)雜度可以降低到O(log n)。但是只嚣，這種方法在插入數(shù)據(jù)的時(shí)候有很大的問題沮稚。新插入一個(gè)節(jié)點(diǎn)之后，就會(huì)打亂上下相鄰兩層鏈表上節(jié)點(diǎn)個(gè)數(shù)嚴(yán)格的2:1的對(duì)應(yīng)關(guān)系册舞。如果要維持這種對(duì)應(yīng)關(guān)系，就必須把新插入的節(jié)點(diǎn)后面的所有節(jié)點(diǎn)（也包括新插入的節(jié)點(diǎn)）重新進(jìn)行調(diào)整障般，這會(huì)讓時(shí)間復(fù)雜度重新蛻化成O(n)调鲸。刪除數(shù)據(jù)也有同樣的問題。

skiplist為了避免這一問題挽荡，它不要求上下相鄰兩層鏈表之間的節(jié)點(diǎn)個(gè)數(shù)有嚴(yán)格的對(duì)應(yīng)關(guān)系藐石，而是為每個(gè)節(jié)點(diǎn)隨機(jī)出一個(gè)層數(shù)(level)。比如定拟，一個(gè)節(jié)點(diǎn)隨機(jī)出的層數(shù)是3于微，那么就把它鏈入到第1層到第3層這三層鏈表中逗嫡。為了表達(dá)清楚，下圖展示了如何通過一步步的插入操作從而形成一個(gè)skiplist的過程：

image.png

從上面skiplist的創(chuàng)建和插入過程可以看出株依，每一個(gè)節(jié)點(diǎn)的層數(shù)（level）是隨機(jī)出來的驱证，而且新插入一個(gè)節(jié)點(diǎn)不會(huì)影響其它節(jié)點(diǎn)的層數(shù)。因此恋腕，插入操作只需要修改插入節(jié)點(diǎn)前后的指針抹锄，而不需要對(duì)很多節(jié)點(diǎn)都進(jìn)行調(diào)整。這就降低了插入操作的復(fù)雜度荠藤。實(shí)際上伙单，這是skiplist的一個(gè)很重要的特性，這讓它在插入性能上明顯優(yōu)于平衡樹的方案哈肖。這在后面我們還會(huì)提到吻育。

根據(jù)上圖中的skiplist結(jié)構(gòu)，我們很容易理解這種數(shù)據(jù)結(jié)構(gòu)的名字的由來淤井。skiplist扫沼，翻譯成中文，可以翻譯成“跳表”或“跳躍表”庄吼，指的就是除了最下面第1層鏈表之外缎除，它會(huì)產(chǎn)生若干層稀疏的鏈表，這些鏈表里面的指針故意跳過了一些節(jié)點(diǎn)（而且越高層的鏈表跳過的節(jié)點(diǎn)越多）总寻。這就使得我們?cè)诓檎覕?shù)據(jù)的時(shí)候能夠先在高層的鏈表中進(jìn)行查找器罐，然后逐層降低，最終降到第1層鏈表來精確地確定數(shù)據(jù)位置渐行。在這個(gè)過程中轰坊，我們跳過了一些節(jié)點(diǎn)，從而也就加快了查找速度祟印。

剛剛創(chuàng)建的這個(gè)skiplist總共包含4層鏈表肴沫，現(xiàn)在假設(shè)我們?cè)谒锩嬉廊徊檎?3，下圖給出了查找路徑：

image.png

需要注意的是蕴忆，前面演示的各個(gè)節(jié)點(diǎn)的插入過程颤芬，實(shí)際上在插入之前也要先經(jīng)歷一個(gè)類似的查找過程，在確定插入位置后套鹅，再完成插入操作站蝠。

至此，skiplist的查找和插入操作卓鹿，我們已經(jīng)很清楚了菱魔。而刪除操作與插入操作類似，我們也很容易想象出來吟孙。這些操作我們也應(yīng)該能很容易地用代碼實(shí)現(xiàn)出來澜倦。

當(dāng)然聚蝶，實(shí)際應(yīng)用中的skiplist每個(gè)節(jié)點(diǎn)應(yīng)該包含key和value兩部分。前面的描述中我們沒有具體區(qū)分key和value藻治，但實(shí)際上列表中是按照key進(jìn)行排序的碘勉，查找過程也是根據(jù)key在比較。

但是栋艳，如果你是第一次接觸skiplist恰聘，那么一定會(huì)產(chǎn)生一個(gè)疑問：節(jié)點(diǎn)插入時(shí)隨機(jī)出一個(gè)層數(shù)，僅僅依靠這樣一個(gè)簡單的隨機(jī)數(shù)操作而構(gòu)建出來的多層鏈表結(jié)構(gòu)吸占，能保證它有一個(gè)良好的查找性能嗎晴叨？為了回答這個(gè)疑問，我們需要分析skiplist的統(tǒng)計(jì)性能矾屯。

在分析之前兼蕊，我們還需要著重指出的是，執(zhí)行插入操作時(shí)計(jì)算隨機(jī)數(shù)的過程件蚕，是一個(gè)很關(guān)鍵的過程孙技，它對(duì)skiplist的統(tǒng)計(jì)特性有著很重要的影響。這并不是一個(gè)普通的服從均勻分布的隨機(jī)數(shù)排作，它的計(jì)算過程如下：

首先牵啦，每個(gè)節(jié)點(diǎn)肯定都有第1層指針（每個(gè)節(jié)點(diǎn)都在第1層鏈表里）。
如果一個(gè)節(jié)點(diǎn)有第i層(i>=1)指針（即節(jié)點(diǎn)已經(jīng)在第1層到第i層鏈表中）妄痪，那么它有第(i+1)層指針的概率為p哈雏。
節(jié)點(diǎn)最大的層數(shù)不允許超過一個(gè)最大值，記為MaxLevel衫生。

這個(gè)計(jì)算隨機(jī)層數(shù)的偽碼如下所示：

randomLevel()
    level := 1
    // random()返回一個(gè)[0...1)的隨機(jī)數(shù)
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

randomLevel()的偽碼中包含兩個(gè)參數(shù)裳瘪，一個(gè)是p，一個(gè)是MaxLevel罪针。在Redis的skiplist實(shí)現(xiàn)中彭羹，這兩個(gè)參數(shù)的取值為：
p = 1/4
MaxLevel = 32

skiplist的算法性能分析

在這一部分，我們來簡單分析一下skiplist的時(shí)間復(fù)雜度和空間復(fù)雜度泪酱，以便對(duì)于skiplist的性能有一個(gè)直觀的了解派殷。如果你不是特別偏執(zhí)于算法的性能分析，那么可以暫時(shí)跳過這一小節(jié)的內(nèi)容西篓。
我們先來計(jì)算一下每個(gè)節(jié)點(diǎn)所包含的平均指針數(shù)目（概率期望）愈腾。節(jié)點(diǎn)包含的指針數(shù)目，相當(dāng)于這個(gè)算法在空間上的額外開銷(overhead)岂津，可以用來度量空間復(fù)雜度。
根據(jù)前面randomLevel()的偽碼悦即，我們很容易看出吮成，產(chǎn)生越高的節(jié)點(diǎn)層數(shù)橱乱，概率越低。定量的分析如下：

節(jié)點(diǎn)層數(shù)至少為1粱甫。而大于1的節(jié)點(diǎn)層數(shù)泳叠，滿足一個(gè)概率分布。
節(jié)點(diǎn)層數(shù)恰好等于1的概率為1-p茶宵。
節(jié)點(diǎn)層數(shù)大于等于2的概率為p危纫，而節(jié)點(diǎn)層數(shù)恰好等于2的概率為p(1-p)。
節(jié)點(diǎn)層數(shù)大于等于3的概率為p2乌庶，而節(jié)點(diǎn)層數(shù)恰好等于3的概率為p2(1-p)种蝶。
節(jié)點(diǎn)層數(shù)大于等于4的概率為p3，而節(jié)點(diǎn)層數(shù)恰好等于4的概率為p3(1-p)瞒大。
......

因此螃征，一個(gè)節(jié)點(diǎn)的平均層數(shù)（也即包含的平均指針數(shù)目），計(jì)算如下：


image.png

現(xiàn)在很容易計(jì)算出：

當(dāng)p=1/2時(shí)透敌，每個(gè)節(jié)點(diǎn)所包含的平均指針數(shù)目為2盯滚；
當(dāng)p=1/4時(shí)，每個(gè)節(jié)點(diǎn)所包含的平均指針數(shù)目為1.33酗电。這也是Redis里的skiplist實(shí)現(xiàn)在空間上的開銷魄藕。

接下來，為了分析時(shí)間復(fù)雜度撵术，我們計(jì)算一下skiplist的平均查找長度背率。查找長度指的是查找路徑上跨越的跳數(shù)，而查找過程中的比較次數(shù)就等于查找長度加1荷荤。以前面圖中標(biāo)出的查找23的查找路徑為例退渗，從左上角的頭結(jié)點(diǎn)開始，一直到結(jié)點(diǎn)22蕴纳，查找長度為6会油。

為了計(jì)算查找長度，這里我們需要利用一點(diǎn)小技巧古毛。我們注意到翻翩，每個(gè)節(jié)點(diǎn)插入的時(shí)候，它的層數(shù)是由隨機(jī)函數(shù)randomLevel()計(jì)算出來的稻薇，而且隨機(jī)的計(jì)算不依賴于其它節(jié)點(diǎn)嫂冻，每次插入過程都是完全獨(dú)立的。所以塞椎，從統(tǒng)計(jì)上來說桨仿，一個(gè)skiplist結(jié)構(gòu)的形成與節(jié)點(diǎn)的插入順序無關(guān)。

這樣的話案狠，為了計(jì)算查找長度服傍，我們可以將查找過程倒過來看钱雷，從右下方第1層上最后到達(dá)的那個(gè)節(jié)點(diǎn)開始，沿著查找路徑向左向上回溯吹零，類似于爬樓梯的過程罩抗。我們假設(shè)當(dāng)回溯到某個(gè)節(jié)點(diǎn)的時(shí)候，它才被插入灿椅，這雖然相當(dāng)于改變了節(jié)點(diǎn)的插入順序套蒂，但從統(tǒng)計(jì)上不影響整個(gè)skiplist的形成結(jié)構(gòu)。
現(xiàn)在假設(shè)我們從一個(gè)層數(shù)為i的節(jié)點(diǎn)x出發(fā)茫蛹，需要向左向上攀爬k層操刀。這時(shí)我們有兩種可能：

如果節(jié)點(diǎn)x有第(i+1)層指針，那么我們需要向上走麻惶。這種情況概率為p馍刮。
如果節(jié)點(diǎn)x沒有第(i+1)層指針，那么我們需要向左走窃蹋。這種情況概率為(1-p)卡啰。

這兩種情形如下圖所示：

image.png

用C(k)表示向上攀爬k個(gè)層級(jí)所需要走過的平均查找路徑長度（概率期望），那么：

C(0)=0
C(k)=(1-p)×(上圖中情況b的查找長度) + p×(上圖中情況c的查找長度)

代入警没，得到一個(gè)差分方程并化簡：

C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
C(k)=1/p+C(k-1)
C(k)=k/p

這個(gè)結(jié)果的意思是匈辱，我們每爬升1個(gè)層級(jí)，需要在查找路徑上走1/p步杀迹。而我們總共需要攀爬的層級(jí)數(shù)等于整個(gè)skiplist的總層數(shù)-1亡脸。
那么接下來我們需要分析一下當(dāng)skiplist中有n個(gè)節(jié)點(diǎn)的時(shí)候，它的總層數(shù)的概率均值是多少树酪。這個(gè)問題直觀上比較好理解浅碾。根據(jù)節(jié)點(diǎn)的層數(shù)隨機(jī)算法，容易得出：

第1層鏈表固定有n個(gè)節(jié)點(diǎn)续语；
第2層鏈表平均有np個(gè)節(jié)點(diǎn)垂谢；
第3層鏈表平均有np2個(gè)節(jié)點(diǎn)；
...

所以疮茄，從第1層到最高層滥朱，各層鏈表的平均節(jié)點(diǎn)數(shù)是一個(gè)指數(shù)遞減的等比數(shù)列。容易推算出力试，總層數(shù)的均值為log1/pn徙邻，而最高層的平均節(jié)點(diǎn)數(shù)為1/p。
綜上畸裳，粗略來計(jì)算的話缰犁，平均查找長度約等于：

  • C(log1/pn-1)=(log1/pn-1)/p

即，平均時(shí)間復(fù)雜度為O(log n)。

當(dāng)然民鼓，這里的時(shí)間復(fù)雜度分析還是比較粗略的薇芝。比如蓬抄，沿著查找路徑向左向上回溯的時(shí)候丰嘉，可能先到達(dá)左側(cè)頭結(jié)點(diǎn)，然后沿頭結(jié)點(diǎn)一路向上嚷缭；還可能先到達(dá)最高層的節(jié)點(diǎn)饮亏，然后沿著最高層鏈表一路向左。但這些細(xì)節(jié)不影響平均時(shí)間復(fù)雜度的最后結(jié)果阅爽。另外路幸，這里給出的時(shí)間復(fù)雜度只是一個(gè)概率平均值，但實(shí)際上計(jì)算一個(gè)精細(xì)的概率分布也是有可能的付翁。詳情還請(qǐng)參見William Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》简肴。

skiplist與平衡樹、哈希表的比較

  • skiplist和各種平衡樹（如AVL百侧、紅黑樹等）的元素是有序排列的砰识，而哈希表不是有序的。因此佣渴，在哈希表上只能做單個(gè)key的查找辫狼，不適宜做范圍查找。所謂范圍查找辛润，指的是查找那些大小在指定的兩個(gè)值之間的所有節(jié)點(diǎn)膨处。

  • 在做范圍查找的時(shí)候，平衡樹比skiplist操作要復(fù)雜砂竖。在平衡樹上真椿，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點(diǎn)乎澄。如果不對(duì)平衡樹進(jìn)行一定的改造突硝，這里的中序遍歷并不容易實(shí)現(xiàn)。而在skiplist上進(jìn)行范圍查找就非常簡單三圆，只需要在找到小值之后狞换，對(duì)第1層鏈表進(jìn)行若干步的遍歷就可以實(shí)現(xiàn)。

  • 平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整舟肉，邏輯復(fù)雜修噪，而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針，操作簡單又快速路媚。

  • 從內(nèi)存占用上來說黄琼，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個(gè)節(jié)點(diǎn)包含2個(gè)指針（分別指向左右子樹）脏款，而skiplist每個(gè)節(jié)點(diǎn)包含的指針數(shù)目平均為1/(1-p)围苫，具體取決于參數(shù)p的大小。如果像Redis里的實(shí)現(xiàn)一樣撤师，取p=1/4剂府，那么平均每個(gè)節(jié)點(diǎn)包含1.33個(gè)指針，比平衡樹更有優(yōu)勢(shì)剃盾。

  • 查找單個(gè)key腺占，skiplist和平衡樹的時(shí)間復(fù)雜度都為O(log n)，大體相當(dāng)痒谴；而哈希表在保持較低的哈希值沖突概率的前提下衰伯，查找時(shí)間復(fù)雜度接近O(1)，性能更高一些积蔚。所以我們平常使用的各種Map或dictionary結(jié)構(gòu)意鲸，大都是基于哈希表實(shí)現(xiàn)的。

  • 從算法實(shí)現(xiàn)難度上來比較尽爆，skiplist比平衡樹要簡單得多怎顾。

Redis中的skiplist實(shí)現(xiàn)

在Redis中，skiplist被用于實(shí)現(xiàn)暴露給外部的一個(gè)數(shù)據(jù)結(jié)構(gòu)：sorted set教翩。準(zhǔn)確地說杆勇，sorted set底層不僅僅使用了skiplist，還使用了ziplist和dict饱亿。這幾個(gè)數(shù)據(jù)結(jié)構(gòu)的關(guān)系蚜退，我們以后再討論。現(xiàn)在彪笼，我們先花點(diǎn)時(shí)間把sorted set的關(guān)鍵命令看一下钻注。這些命令對(duì)于Redis里skiplist的實(shí)現(xiàn)，有重要的影響配猫。

sorted set的命令舉例
sorted set是一個(gè)有序的數(shù)據(jù)集合幅恋，對(duì)于像類似排行榜這樣的應(yīng)用場(chǎng)景特別適合。

現(xiàn)在我們來看一個(gè)例子泵肄，用sorted set來存儲(chǔ)代數(shù)課（algebra）的成績表捆交。原始數(shù)據(jù)如下：

Alice 87.5
Bob 89.0
Charles 65.5
David 78.0
Emily 93.5
Fred 87.5

這份數(shù)據(jù)給出了每位同學(xué)的名字和分?jǐn)?shù)。下面我們將這份數(shù)據(jù)存儲(chǔ)到sorted set里面去：

image.png

對(duì)于上面的這些命令腐巢，我們需要的注意的地方包括：

  • 前面的6個(gè)zadd命令品追，將6位同學(xué)的名字和分?jǐn)?shù)(score)都輸入到一個(gè)key值為algebra的sorted set里面了。注意Alice和Fred的分?jǐn)?shù)相同冯丙，都是87.5分肉瓦。

  • zrevrank命令查詢Alice的排名（命令中的rev表示按照倒序排列，也就是從大到小）泞莉，返回3哪雕。排在Alice前面的分別是Emily、Bob鲫趁、Fred斯嚎，而排名(rank)從0開始計(jì)數(shù)蹲盘，所以Alice的排名是3蔗彤。注意，其實(shí)Alice和Fred的分?jǐn)?shù)相同，這種情況下sorted set會(huì)把分?jǐn)?shù)相同的元素幽崩，按照字典順序來排列。按照倒序寞钥，F(xiàn)red排在了Alice的前面慌申。

  • zscore命令查詢了Charles對(duì)應(yīng)的分?jǐn)?shù)。

  • zrevrange命令查詢了從大到小排名為0~3的4位同學(xué)理郑。

  • zrevrangebyscore命令查詢了分?jǐn)?shù)在80.0和90.0之間的所有同學(xué)蹄溉，并按分?jǐn)?shù)從大到小排列。

總結(jié)一下您炉，sorted set中的每個(gè)元素主要表現(xiàn)出3個(gè)屬性：

  • 數(shù)據(jù)本身（在前面的例子中我們把名字存成了數(shù)據(jù)）柒爵。
  • 每個(gè)數(shù)據(jù)對(duì)應(yīng)一個(gè)分?jǐn)?shù)(score)。
  • 根據(jù)分?jǐn)?shù)大小和數(shù)據(jù)本身的字典排序赚爵，每個(gè)數(shù)據(jù)會(huì)產(chǎn)生一個(gè)排名(rank)棉胀。可以按正序或倒序冀膝。
Redis中skiplist實(shí)現(xiàn)的特殊性

我們簡單分析一下前面出現(xiàn)的幾個(gè)查詢命令：

  • zrevrank由數(shù)據(jù)查詢它對(duì)應(yīng)的排名唁奢，這在前面介紹的skiplist中并不支持。
  • zscore由數(shù)據(jù)查詢它對(duì)應(yīng)的分?jǐn)?shù)窝剖，這也不是skiplist所支持的麻掸。
  • zrevrange根據(jù)一個(gè)排名范圍，查詢排名在這個(gè)范圍內(nèi)的數(shù)據(jù)赐纱。這在前面介紹的skiplist中也不支持脊奋。
  • zrevrangebyscore根據(jù)分?jǐn)?shù)區(qū)間查詢數(shù)據(jù)集合，是一個(gè)skiplist所支持的典型的范圍查找（score相當(dāng)于key）疙描。

實(shí)際上诚隙，Redis中sorted set的實(shí)現(xiàn)是這樣的：

  • 當(dāng)數(shù)據(jù)較少時(shí)，sorted set是由一個(gè)ziplist來實(shí)現(xiàn)的淫痰。
  • 當(dāng)數(shù)據(jù)多的時(shí)候最楷，sorted set是由一個(gè)dict + 一個(gè)skiplist來實(shí)現(xiàn)的。簡單來講，dict用來查詢數(shù)據(jù)到分?jǐn)?shù)的對(duì)應(yīng)關(guān)系籽孙，而skiplist用來根據(jù)分?jǐn)?shù)查詢數(shù)據(jù)（可能是范圍查找）烈评。

現(xiàn)在我們集中精力來看一下sorted set與skiplist的關(guān)系，：

  • zscore的查詢犯建，不是由skiplist來提供的讲冠，而是由那個(gè)dict來提供的。
  • 為了支持排名(rank)适瓦，Redis里對(duì)skiplist做了擴(kuò)展竿开，使得根據(jù)排名能夠快速查到數(shù)據(jù)，或者根據(jù)分?jǐn)?shù)查到數(shù)據(jù)之后玻熙，也同時(shí)很容易獲得排名否彩。而且，根據(jù)排名的查找嗦随，時(shí)間復(fù)雜度也為O(log n)列荔。
  • zrevrange的查詢，是根據(jù)排名查數(shù)據(jù)枚尼，由擴(kuò)展后的skiplist來提供贴浙。
  • zrevrank是先在dict中由數(shù)據(jù)查到分?jǐn)?shù)，再拿分?jǐn)?shù)到skiplist中去查找署恍，查到后也同時(shí)獲得了排名崎溃。

前述的查詢過程，也暗示了各個(gè)操作的時(shí)間復(fù)雜度：

  • zscore只用查詢一個(gè)dict盯质，所以時(shí)間復(fù)雜度為O(1)
  • zrevrank, zrevrange, zrevrangebyscore由于要查詢skiplist袁串，所以zrevrank的時(shí)間復(fù)雜度為O(log n)，而zrevrange, zrevrangebyscore的時(shí)間復(fù)雜度為O(log(n)+M)唤殴，其中M是當(dāng)前查詢返回的元素個(gè)數(shù)般婆。

總結(jié)起來，Redis中的skiplist跟前面介紹的經(jīng)典的skiplist相比朵逝，有如下不同：

  • 分?jǐn)?shù)(score)允許重復(fù)蔚袍，即skiplist的key允許重復(fù)。這在最開始介紹的經(jīng)典skiplist中是不允許的配名。

  • 在比較時(shí)啤咽，不僅比較分?jǐn)?shù)（相當(dāng)于skiplist的key），還比較數(shù)據(jù)本身渠脉。在Redis的skiplist實(shí)現(xiàn)中宇整，數(shù)據(jù)本身的內(nèi)容唯一標(biāo)識(shí)這份數(shù)據(jù)，而不是由key來唯一標(biāo)識(shí)芋膘。另外鳞青，當(dāng)多個(gè)元素分?jǐn)?shù)相同的時(shí)候霸饲，還需要根據(jù)數(shù)據(jù)內(nèi)容來進(jìn)字典排序。

  • 第1層鏈表不是一個(gè)單向鏈表臂拓，而是一個(gè)雙向鏈表厚脉。這是為了方便以倒序方式獲取一個(gè)范圍內(nèi)的元素。

  • 在skiplist中可以很方便地計(jì)算出每個(gè)元素的排名(rank)胶惰。

skiplist的數(shù)據(jù)結(jié)構(gòu)定義
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

  • 開頭定義了兩個(gè)常量傻工，ZSKIPLIST_MAXLEVEL和ZSKIPLIST_P，分別對(duì)應(yīng)我們前面講到的skiplist的兩個(gè)參數(shù)：一個(gè)是MaxLevel孵滞，一個(gè)是p中捆。

  • zskiplistNode定義了skiplist的節(jié)點(diǎn)結(jié)構(gòu)。

    • obj字段存放的是節(jié)點(diǎn)數(shù)據(jù)坊饶，它的類型是一個(gè)string robj泄伪。本來一個(gè)string robj可能存放的不是sds，而是long型幼东，但zadd命令在將數(shù)據(jù)插入到skiplist里面之前先進(jìn)行了解碼臂容，所以這里的obj字段里存儲(chǔ)的一定是一個(gè)sds。這樣做的目的應(yīng)該是為了方便在查找的時(shí)候?qū)?shù)據(jù)進(jìn)行字典序的比較根蟹，而且，skiplist里的數(shù)據(jù)部分是數(shù)字的可能性也比較小糟秘。

  • score字段是數(shù)據(jù)對(duì)應(yīng)的分?jǐn)?shù)简逮。

  • backward字段是指向鏈表前一個(gè)節(jié)點(diǎn)的指針（前向指針）。節(jié)點(diǎn)只有1個(gè)前向指針尿赚，所以只有第1層鏈表是一個(gè)雙向鏈表散庶。

  • level[]存放指向各層鏈表后一個(gè)節(jié)點(diǎn)的指針（后向指針）。每層對(duì)應(yīng)1個(gè)后向指針凌净，用forward字段表示悲龟。另外，每個(gè)后向指針還對(duì)應(yīng)了一個(gè)span值冰寻，它表示當(dāng)前的指針跨越了多少個(gè)節(jié)點(diǎn)须教。span用于計(jì)算元素排名(rank)，這正是前面我們提到的Redis對(duì)于skiplist所做的一個(gè)擴(kuò)展斩芭。需要注意的是轻腺，level[]是一個(gè)柔性數(shù)組（flexible array member），因此它占用的內(nèi)存不在zskiplistNode結(jié)構(gòu)里面划乖，而需要插入節(jié)點(diǎn)的時(shí)候單獨(dú)為它分配贬养。也正因?yàn)槿绱耍瑂kiplist的每個(gè)節(jié)點(diǎn)所包含的指針數(shù)目才是不固定的琴庵，我們前面分析過的結(jié)論——skiplist每個(gè)節(jié)點(diǎn)包含的指針數(shù)目平均為1/(1-p)——才能有意義误算。

  • zskiplist定義了真正的skiplist結(jié)構(gòu)仰美，它包含：

    • 頭指針header和尾指針tail。
    • 鏈表長度length儿礼，即鏈表包含的節(jié)點(diǎn)總數(shù)咖杂。注意，新創(chuàng)建的skiplist包含一個(gè)空的頭指針蜘犁，這個(gè)頭指針不包含在length計(jì)數(shù)中翰苫。
    • level表示skiplist的總層數(shù)，即所有節(jié)點(diǎn)層數(shù)的最大值这橙。

下圖以前面插入的代數(shù)課成績表為例奏窑，展示了Redis中一個(gè)skiplist的可能結(jié)構(gòu)


image.png

注意：圖中前向指針上面括號(hào)中的數(shù)字，表示對(duì)應(yīng)的span的值屈扎。即當(dāng)前指針跨越了多少個(gè)節(jié)點(diǎn)埃唯，這個(gè)計(jì)數(shù)不包括指針的起點(diǎn)節(jié)點(diǎn)，但包括指針的終點(diǎn)節(jié)點(diǎn)鹰晨。

假設(shè)我們?cè)谶@個(gè)skiplist中查找score=89.0的元素（即Bob的成績數(shù)據(jù)）墨叛，在查找路徑中，我們會(huì)跨域圖中標(biāo)紅的指針模蜡，這些指針上面的span值累加起來漠趁，就得到了Bob的排名(2+2+1)-1=4（減1是因?yàn)閞ank值以0起始）。需要注意這里算的是從小到大的排名忍疾，而如果要算從大到小的排名闯传，只需要用skiplist長度減去查找路徑上的span累加值，即6-(2+2+1)=1卤妒。

可見甥绿，在查找skiplist的過程中，通過累加span值的方式则披，我們就能很容易算出排名共缕。相反，如果指定排名來查找數(shù)據(jù)（類似zrange和zrevrange那樣）士复，也可以不斷累加span并時(shí)刻保持累加值不超過指定的排名图谷，通過這種方式就能得到一條O(log n)的查找路徑。

Redis中的sorted set

我們前面提到過判没，Redis中的sorted set蜓萄，是在skiplist, dict和ziplist基礎(chǔ)上構(gòu)建起來的:

當(dāng)數(shù)據(jù)較少時(shí)，sorted set是由一個(gè)ziplist來實(shí)現(xiàn)的澄峰。
當(dāng)數(shù)據(jù)多的時(shí)候嫉沽，sorted set是由一個(gè)叫zset的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，這個(gè)zset包含一個(gè)dict + 一個(gè)skiplist俏竞。dict用來查詢數(shù)據(jù)到分?jǐn)?shù)(score)的對(duì)應(yīng)關(guān)系绸硕，而skiplist用來根據(jù)分?jǐn)?shù)查詢數(shù)據(jù)（可能是范圍查找）堂竟。

在這里我們先來討論一下前一種情況——基于ziplist實(shí)現(xiàn)的sorted set。
ziplist就是由很多數(shù)據(jù)項(xiàng)組成的一大塊連續(xù)內(nèi)存玻佩。由于sorted set的每一項(xiàng)元素都由數(shù)據(jù)和score組成出嘹，因此，當(dāng)使用zadd命令插入一個(gè)(數(shù)據(jù), score)對(duì)的時(shí)候咬崔，底層在相應(yīng)的ziplist上就插入兩個(gè)數(shù)據(jù)項(xiàng)：數(shù)據(jù)在前税稼，score在后。

ziplist的主要優(yōu)點(diǎn)是節(jié)省內(nèi)存垮斯，但它上面的查找操作只能按順序查找（可以正序也可以倒序）郎仆。因此，sorted set的各個(gè)查詢操作兜蠕，就是在ziplist上從前向后（或從后向前）一步步查找扰肌，每一步前進(jìn)兩個(gè)數(shù)據(jù)項(xiàng)，跨域一個(gè)(數(shù)據(jù), score)對(duì)熊杨。

隨著數(shù)據(jù)的插入曙旭，sorted set底層的這個(gè)ziplist就可能會(huì)轉(zhuǎn)成zset的實(shí)現(xiàn)（轉(zhuǎn)換過程詳見t_zset.c的zsetConvert）。那么到底插入多少才會(huì)轉(zhuǎn)呢晶府？

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

這個(gè)配置的意思是說桂躏，在如下兩個(gè)條件之一滿足的時(shí)候，ziplist會(huì)轉(zhuǎn)成zset（具體的觸發(fā)條件參見t_zset.c中的zaddGenericCommand相關(guān)代碼）：

  • 當(dāng)sorted set中的元素個(gè)數(shù)川陆，即(數(shù)據(jù), score)對(duì)的數(shù)目超過128的時(shí)候沼头，也就是ziplist數(shù)據(jù)項(xiàng)超過256的時(shí)候。
  • 當(dāng)sorted set中插入的任意一個(gè)數(shù)據(jù)的長度超過了64的時(shí)候书劝。

最后，zset結(jié)構(gòu)的代碼定義如下：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Redis為什么用skiplist而不用平衡樹土至？

在前面我們對(duì)于skiplist和平衡樹购对、哈希表的比較中，其實(shí)已經(jīng)不難看出Redis里使用skiplist而不用平衡樹的原因了√找颍現(xiàn)在我們看看骡苞，對(duì)于這個(gè)問題，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.

這里從內(nèi)存占用楷扬、對(duì)范圍查找的支持和實(shí)現(xiàn)難易程度這三方面總結(jié)的原因解幽，我們?cè)谇懊嫫鋵?shí)也都涉及到了。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末烘苹，一起剝皮案震驚了整個(gè)濱河市躲株，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌镣衡，老刑警劉巖霜定，帶你破解...
    沈念sama閱讀 218,607評(píng)論 6贊 507
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件档悠，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡望浩，警方通過查閱死者的電腦和手機(jī)辖所，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,239評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來磨德，“玉大人缘回，你說我怎么就攤上這事〉涮簦” “怎么了酥宴？”我有些...
    開封第一講書人閱讀 164,960評(píng)論 0贊 355
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長搔弄。 經(jīng)常有香客問我幅虑，道長，這世上最難降的妖魔是什么顾犹？ 我笑而不...
    開封第一講書人閱讀 58,750評(píng)論 1贊 294
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任倒庵，我火速辦了婚禮，結(jié)果婚禮上炫刷，老公的妹妹穿的比我還像新娘擎宝。我一直安慰自己，他們只是感情好浑玛，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,764評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布绍申。 她就那樣靜靜地躺著，像睡著了一般顾彰。 火紅的嫁衣襯著肌膚如雪极阅。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,604評(píng)論 1贊 305
  • 城市分裂傳說
    那天涨享，我揣著相機(jī)與錄音筋搏，去河邊找鬼。 笑死厕隧，一個(gè)胖子當(dāng)著我的面吹牛奔脐，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播吁讨，決...
    沈念sama閱讀 40,347評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼髓迎，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了建丧？” 一聲冷哼從身側(cè)響起排龄，我...
    開封第一講書人閱讀 39,253評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎茶鹃，沒想到半個(gè)月后涣雕，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體艰亮，經(jīng)...
    沈念sama閱讀 45,702評(píng)論 1贊 315
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,893評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年挣郭，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了迄埃。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,015評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡兑障，死狀恐怖侄非，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情流译，我是刑警寧澤逞怨，帶...
    沈念sama閱讀 35,734評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站福澡，受9級(jí)特大地震影響叠赦，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜革砸，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,352評(píng)論 3贊 330
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一除秀、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧算利，春花似錦册踩、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,934評(píng)論 0贊 22
  • 一樁弒父案暂吉，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至缎患，卻和暖如春慕的，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背挤渔。 一陣腳步聲響...
    開封第一講書人閱讀 33,052評(píng)論 1贊 270
  • 情欲美人皮
    我被黑心中介騙來泰國打工业稼， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人蚂蕴。 一個(gè)月前我還...
    沈念sama閱讀 48,216評(píng)論 3贊 371
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像俯邓，于是被迫代替她去往敵國和親骡楼。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,969評(píng)論 2贊 355