大家好，我是小林。

之前寫過(guò)一篇 Redis 數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：為了拿捏 Redis 數(shù)據(jù)結(jié)構(gòu)，我畫了 40 張圖

其中提到，ZSet 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)之一是跳表。

然后，有讀者就問(wèn)：為什么不使用平衡樹（如紅黑樹、AVL 樹）？

我們先來(lái)了解下跳表，再來(lái)回答這個(gè)問(wèn)題。

跳表

Redis 只有 Zset 對(duì)象的底層實(shí)現(xiàn)用到了跳表，跳表的優(yōu)勢(shì)是能支持平均 O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

zset 結(jié)構(gòu)體里有兩個(gè)數(shù)據(jù)結(jié)構(gòu)：一個(gè)是跳表，一個(gè)是哈希表。這樣的好處是既能進(jìn)行高效的范圍查詢，也能進(jìn)行高效單點(diǎn)查詢。

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

Zset 對(duì)象在執(zhí)行數(shù)據(jù)插入或是數(shù)據(jù)更新的過(guò)程中，會(huì)依次在跳表和哈希表中插入或更新相應(yīng)的數(shù)據(jù)，從而保證了跳表和哈希表中記錄的信息一致。

Zset 對(duì)象能支持范圍查詢（如 ZRANGEBYSCORE 操作），這是因?yàn)樗臄?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用了跳表，而又能以常數(shù)復(fù)雜度獲取元素權(quán)重（如 ZSCORE 操作），這是因?yàn)樗瑫r(shí)采用了哈希表進(jìn)行索引。

可能很多人會(huì)奇怪，為什么我開頭說(shuō) Zset 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)是「壓縮列表」或者「跳表」，而沒(méi)有說(shuō)哈希表呢？

Zset 對(duì)象在使用跳表作為數(shù)據(jù)結(jié)構(gòu)的時(shí)候，是使用由「哈希表+跳表」組成的 struct zset，但是我們討論的時(shí)候，都會(huì)說(shuō)跳表是 Zset 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)，而不會(huì)提及哈希表，是因?yàn)?struct zset 中的哈希表只是用于以常數(shù)復(fù)雜度獲取元素權(quán)重，大部分操作都是跳表實(shí)現(xiàn)的。

接下來(lái)，詳細(xì)的說(shuō)下跳表。

跳表結(jié)構(gòu)設(shè)計(jì)

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎?，所以查詢效率非常低，時(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過(guò)來(lái)的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長(zhǎng)什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級(jí)為 3 的跳表。

圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級(jí)的節(jié)點(diǎn)，然后每個(gè)層級(jí)的節(jié)點(diǎn)都通過(guò)指針連接起來(lái)：

• L0 層級(jí)共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；
• L1 層級(jí)共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；
• L2 層級(jí)只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級(jí)跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過(guò)程就是在多個(gè)層級(jí)上跳來(lái)跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

那跳表節(jié)點(diǎn)是怎么實(shí)現(xiàn)多層級(jí)的呢？這就需要看「跳表節(jié)點(diǎn)」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef struct zskiplistNode { //Zset 對(duì)象的元素值 sds ele; //元素權(quán)重值 double score; //后向指針 struct zskiplistNode *backward; //節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度 struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span;
    } level[];
} zskiplistNode;

Zset 對(duì)象要同時(shí)保存「元素」和「元素的權(quán)重」，對(duì)應(yīng)到跳表節(jié)點(diǎn)結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個(gè)跳表節(jié)點(diǎn)都有一個(gè)后向指針（struct zskiplistNode *backward），指向前一個(gè)節(jié)點(diǎn)，目的是為了方便從跳表的尾節(jié)點(diǎn)開始訪問(wèn)節(jié)點(diǎn)，這樣倒序查找時(shí)很方便。

跳表是一個(gè)帶有層級(jí)關(guān)系的鏈表，而且每一層級(jí)可以包含多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)通過(guò)指針連接起來(lái)，實(shí)現(xiàn)這一特性就是靠跳表節(jié)點(diǎn)結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。

level 數(shù)組中的每一個(gè)元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個(gè)跳表節(jié)點(diǎn)的指針」和「跨度」，跨度時(shí)用來(lái)記錄兩個(gè)節(jié)點(diǎn)之間的距離。

比如，下面這張圖，展示了各個(gè)節(jié)點(diǎn)的跨度。

第一眼看到跨度的時(shí)候，以為是遍歷操作有關(guān)，實(shí)際上并沒(méi)有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。

跨度實(shí)際上是為了計(jì)算這個(gè)節(jié)點(diǎn)在跳表中的排位。具體怎么做的呢？因?yàn)樘碇械墓?jié)點(diǎn)都是按序排列的，那么計(jì)算某個(gè)節(jié)點(diǎn)排位的時(shí)候，從頭節(jié)點(diǎn)點(diǎn)到該結(jié)點(diǎn)的查詢路徑上，將沿途訪問(wèn)過(guò)的所有層的跨度累加起來(lái)，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。

舉個(gè)例子，查找圖中節(jié)點(diǎn) 3 在跳表中的排位，從頭節(jié)點(diǎn)開始查找節(jié)點(diǎn) 3，查找的過(guò)程只經(jīng)過(guò)了一個(gè)層（L2），并且層的跨度是 3，所以節(jié)點(diǎn) 3 在跳表中的排位是 3。

另外，圖中的頭節(jié)點(diǎn)其實(shí)也是 zskiplistNode 跳表節(jié)點(diǎn)，只不過(guò)頭節(jié)點(diǎn)的后向指針、權(quán)重、元素值都沒(méi)有用到，所以圖中省略了這部分。

問(wèn)題來(lái)了，由誰(shuí)定義哪個(gè)跳表節(jié)點(diǎn)是頭節(jié)點(diǎn)呢？這就介紹「跳表」結(jié)構(gòu)體了，如下所示：

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

跳表結(jié)構(gòu)里包含了：

• 跳表的頭尾節(jié)點(diǎn)，便于在O(1)時(shí)間復(fù)雜度內(nèi)訪問(wèn)跳表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)；
• 跳表的長(zhǎng)度，便于在O(1)時(shí)間復(fù)雜度獲取跳表節(jié)點(diǎn)的數(shù)量；
• 跳表的最大層數(shù)，便于在O(1)時(shí)間復(fù)雜度獲取跳表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量；

跳表節(jié)點(diǎn)查詢過(guò)程

查找一個(gè)跳表節(jié)點(diǎn)的過(guò)程時(shí)，跳表會(huì)從頭節(jié)點(diǎn)的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點(diǎn)時(shí)，會(huì)用跳表節(jié)點(diǎn)中的 SDS 類型的元素和元素的權(quán)重來(lái)進(jìn)行判斷，共有兩個(gè)判斷條件：

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「小于」要查找的權(quán)重時(shí)，跳表就會(huì)訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)。
• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「等于」要查找的權(quán)重時(shí)，并且當(dāng)前節(jié)點(diǎn)的 SDS 類型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時(shí)，跳表就會(huì)訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)。

如果上面兩個(gè)條件都不滿足，或者下一個(gè)節(jié)點(diǎn)為空時(shí)，跳表就會(huì)使用目前遍歷到的節(jié)點(diǎn)的 level 數(shù)組里的下一層指針，然后沿著下一層指針繼續(xù)查找，這就相當(dāng)于跳到了下一層接著查找。

舉個(gè)例子，下圖有個(gè) 3 層級(jí)的跳表。

如果要查找「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，查找的過(guò)程是這樣的：

• 先從頭節(jié)點(diǎn)的最高層開始，L2 指向了「元素：abc，權(quán)重：3」節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的權(quán)重比要查找節(jié)點(diǎn)的小，所以要訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)；
• 但是該層的下一個(gè)節(jié)點(diǎn)是空節(jié)點(diǎn)（ leve[2]指向的是空節(jié)點(diǎn)），于是就會(huì)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[1];
• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的  leve[1] 的下一個(gè)指針指向了「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)，然后將其和要查找的節(jié)點(diǎn)比較。雖然「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)的權(quán)重和要查找的權(quán)重相同，但是當(dāng)前節(jié)點(diǎn)的 SDS 類型數(shù)據(jù)「大于」要查找的數(shù)據(jù)，所以會(huì)繼續(xù)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[0]；
• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的 leve[0] 的下一個(gè)指針指向了「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，該節(jié)點(diǎn)正是要查找的節(jié)點(diǎn)，查詢結(jié)束。

跳表節(jié)點(diǎn)層數(shù)設(shè)置

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量的比例會(huì)影響跳表的查詢性能。

舉個(gè)例子，下圖的跳表，第二層的節(jié)點(diǎn)數(shù)量只有 1 個(gè)，而第一層的節(jié)點(diǎn)數(shù)量有 6 個(gè)。

這時(shí)，如果想要查詢節(jié)點(diǎn) 6，那基本就跟鏈表的查詢復(fù)雜度一樣，就需要在第一層的節(jié)點(diǎn)中依次順序查找，復(fù)雜度就是 O(N) 了。所以，為了降低查詢復(fù)雜度，我們就需要維持相鄰層結(jié)點(diǎn)數(shù)間的關(guān)系。

**跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)**。

下圖的跳表就是，相鄰兩層的節(jié)點(diǎn)數(shù)量的比例是 2 : 1。

那怎樣才能維持相鄰兩層的節(jié)點(diǎn)數(shù)量的比例為 2 : 1  呢？

如果采用新增節(jié)點(diǎn)或者刪除節(jié)點(diǎn)時(shí)，來(lái)調(diào)整跳表節(jié)點(diǎn)以維持比例的方法的話，會(huì)帶來(lái)額外的開銷。

Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點(diǎn)的時(shí)候，隨機(jī)生成每個(gè)節(jié)點(diǎn)的層數(shù)，并沒(méi)有嚴(yán)格維持相鄰兩層的節(jié)點(diǎn)數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會(huì)生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點(diǎn)的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過(guò) 25%，層數(shù)越高，概率越低，層高最大限制是 64。

為什么用跳表而不用平衡樹？

為什么 Zset 的實(shí)現(xiàn)用跳表而不用平衡樹（如 AVL樹、紅黑樹等）？

對(duì)于這個(gè)問(wèn)題，Redis的作者 @antirez 是怎么說(shuō)的：

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.

簡(jiǎn)單翻譯一下，主要是從內(nèi)存占用、對(duì)范圍查找的支持、實(shí)現(xiàn)難易程度這三方面總結(jié)的原因：

• 它們不是非常內(nèi)存密集型的?；旧嫌赡銢Q定。改變關(guān)于節(jié)點(diǎn)具有給定級(jí)別數(shù)的概率的參數(shù)將使其比 btree 占用更少的內(nèi)存。
• Zset 經(jīng)常需要執(zhí)行 ZRANGE 或 ZREVRANGE 的命令，即作為鏈表遍歷跳表。通過(guò)此操作，跳表的緩存局部性至少與其他類型的平衡樹一樣好。
• 它們更易于實(shí)現(xiàn)、調(diào)試等。例如，由于跳表的簡(jiǎn)單性，我收到了一個(gè)補(bǔ)?。ㄒ呀?jīng)在Redis master中），其中擴(kuò)展了跳表，在 O(log(N) 中實(shí)現(xiàn)了 ZRANK。它只需要對(duì)代碼進(jìn)行少量修改。

我再詳細(xì)補(bǔ)充點(diǎn)：

• 從內(nèi)存占用上來(lái)比較，跳表比平衡樹更靈活一些。平衡樹每個(gè)節(jié)點(diǎn)包含 2 個(gè)指針（分別指向左右子樹），而跳表每個(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ì)。
• 在做范圍查找的時(shí)候，跳表比平衡樹操作要簡(jiǎn)單。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過(guò)大值的節(jié)點(diǎn)。如果不對(duì)平衡樹進(jìn)行一定的改造，這里的中序遍歷并不容易實(shí)現(xiàn)。而在跳表上進(jìn)行范圍查找就非常簡(jiǎn)單，只需要在找到小值之后，對(duì)第 1 層鏈表進(jìn)行若干步的遍歷就可以實(shí)現(xiàn)。
• 從算法實(shí)現(xiàn)難度上來(lái)比較，跳表比平衡樹要簡(jiǎn)單得多。平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復(fù)雜，而跳表的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針，操作簡(jiǎn)單又快速。

完！