Redis 為什么用跳表，而不用平衡樹？
大家好，我是小林。
之前寫過一篇 Redis 數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)：為了拿捏 Redis 數(shù)據(jù)結(jié)構(gòu)，我畫了 40 張圖
其中提到，ZSet 對象的底層數(shù)據(jù)結(jié)構(gòu)實現(xiàn)之一是跳表。
然后，有讀者就問：為什么不使用平衡樹（如紅黑樹、AVL 樹）？
我們先來了解下跳表，再來回答這個問題。
跳表
Redis 只有 Zset 對象的底層實現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復(fù)雜度的節(jié)點查找。
zset 結(jié)構(gòu)體里有兩個數(shù)據(jù)結(jié)構(gòu)：一個是跳表，一個是哈希表。這樣的好處是既能進行高效的范圍查詢，也能進行高效單點查詢。
typedef struct zset { dict *dict; zskiplist *zsl; } zset;
Zset 對象在執(zhí)行數(shù)據(jù)插入或是數(shù)據(jù)更新的過程中，會依次在跳表和哈希表中插入或更新相應(yīng)的數(shù)據(jù)，從而保證了跳表和哈希表中記錄的信息一致。
Zset 對象能支持范圍查詢（如 ZRANGEBYSCORE 操作），這是因為它的數(shù)據(jù)結(jié)構(gòu)設(shè)計采用了跳表，而又能以常數(shù)復(fù)雜度獲取元素權(quán)重（如 ZSCORE 操作），這是因為它同時采用了哈希表進行索引。
可能很多人會奇怪，為什么我開頭說 Zset 對象的底層數(shù)據(jù)結(jié)構(gòu)是「壓縮列表」或者「跳表」，而沒有說哈希表呢？
Zset 對象在使用跳表作為數(shù)據(jù)結(jié)構(gòu)的時候，是使用由「哈希表+跳表」組成的 struct zset，但是我們討論的時候，都會說跳表是 Zset 對象的底層數(shù)據(jù)結(jié)構(gòu)，而不會提及哈希表，是因為 struct zset 中的哈希表只是用于以常數(shù)復(fù)雜度獲取元素權(quán)重，大部分操作都是跳表實現(xiàn)的。
接下來，詳細的說下跳表。
跳表結(jié)構(gòu)設(shè)計
鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進過來的，實現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。
那跳表長什么樣呢？我這里舉個例子，下圖展示了一個層級為 3 的跳表。
圖中頭節(jié)點有 L0~L2 三個頭指針，分別指向了不同層級的節(jié)點，然后每個層級的節(jié)點都通過指針連接起來：
- L0 層級共有 5 個節(jié)點，分別是節(jié)點1、2、3、4、5；
- L1 層級共有 3 個節(jié)點，分別是節(jié)點 2、3、5；
- L2 層級只有 1 個節(jié)點，也就是節(jié)點 3 。
如果我們要在鏈表中查找節(jié)點 4 這個元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點 4，因為可以在頭節(jié)點直接從 L2 層級跳到節(jié)點 3，然后再往前遍歷找到節(jié)點 4。
可以看到，這個查找過程就是在多個層級上跳來跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時，跳表的查找復(fù)雜度就是 O(logN)。
那跳表節(jié)點是怎么實現(xiàn)多層級的呢？這就需要看「跳表節(jié)點」的數(shù)據(jù)結(jié)構(gòu)了，如下：
typedef struct zskiplistNode { //Zset 對象的元素值 sds ele; //元素權(quán)重值 double score; //后向指針 struct zskiplistNode *backward; //節(jié)點的level數(shù)組，保存每層上的前向指針和跨度 struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;
Zset 對象要同時保存「元素」和「元素的權(quán)重」，對應(yīng)到跳表節(jié)點結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節(jié)點都有一個后向指針（struct zskiplistNode *backward），指向前一個節(jié)點，目的是為了方便從跳表的尾節(jié)點開始訪問節(jié)點，這樣倒序查找時很方便。
跳表是一個帶有層級關(guān)系的鏈表，而且每一層級可以包含多個節(jié)點，每一個節(jié)點通過指針連接起來，實現(xiàn)這一特性就是靠跳表節(jié)點結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。
level 數(shù)組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個跳表節(jié)點的指針」和「跨度」，跨度時用來記錄兩個節(jié)點之間的距離。
比如，下面這張圖，展示了各個節(jié)點的跨度。
第一眼看到跨度的時候，以為是遍歷操作有關(guān)，實際上并沒有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。
跨度實際上是為了計算這個節(jié)點在跳表中的排位。具體怎么做的呢？因為跳表中的節(jié)點都是按序排列的，那么計算某個節(jié)點排位的時候，從頭節(jié)點點到該結(jié)點的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結(jié)果就是目標節(jié)點在跳表中的排位。
舉個例子，查找圖中節(jié)點 3 在跳表中的排位，從頭節(jié)點開始查找節(jié)點 3，查找的過程只經(jīng)過了一個層（L2），并且層的跨度是 3，所以節(jié)點 3 在跳表中的排位是 3。
另外，圖中的頭節(jié)點其實也是 zskiplistNode 跳表節(jié)點，只不過頭節(jié)點的后向指針、權(quán)重、元素值都沒有用到，所以圖中省略了這部分。
問題來了，由誰定義哪個跳表節(jié)點是頭節(jié)點呢？這就介紹「跳表」結(jié)構(gòu)體了，如下所示：
typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;
跳表結(jié)構(gòu)里包含了：
- 跳表的頭尾節(jié)點，便于在O(1)時間復(fù)雜度內(nèi)訪問跳表的頭節(jié)點和尾節(jié)點；
- 跳表的長度，便于在O(1)時間復(fù)雜度獲取跳表節(jié)點的數(shù)量；
- 跳表的最大層數(shù)，便于在O(1)時間復(fù)雜度獲取跳表中層高最大的那個節(jié)點的層數(shù)量；
跳表節(jié)點查詢過程
查找一個跳表節(jié)點的過程時，跳表會從頭節(jié)點的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點時，會用跳表節(jié)點中的 SDS 類型的元素和元素的權(quán)重來進行判斷，共有兩個判斷條件：
- 如果當(dāng)前節(jié)點的權(quán)重「小于」要查找的權(quán)重時，跳表就會訪問該層上的下一個節(jié)點。
- 如果當(dāng)前節(jié)點的權(quán)重「等于」要查找的權(quán)重時，并且當(dāng)前節(jié)點的 SDS 類型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時，跳表就會訪問該層上的下一個節(jié)點。
如果上面兩個條件都不滿足，或者下一個節(jié)點為空時，跳表就會使用目前遍歷到的節(jié)點的 level 數(shù)組里的下一層指針，然后沿著下一層指針繼續(xù)查找，這就相當(dāng)于跳到了下一層接著查找。
舉個例子，下圖有個 3 層級的跳表。
如果要查找「元素：abcd，權(quán)重：4」的節(jié)點，查找的過程是這樣的：
- 先從頭節(jié)點的最高層開始，L2 指向了「元素：abc，權(quán)重：3」節(jié)點，這個節(jié)點的權(quán)重比要查找節(jié)點的小，所以要訪問該層上的下一個節(jié)點；
- 但是該層的下一個節(jié)點是空節(jié)點（ leve[2]指向的是空節(jié)點），于是就會跳到「元素：abc，權(quán)重：3」節(jié)點的下一層去找，也就是 leve[1];
- 「元素：abc，權(quán)重：3」節(jié)點的 leve[1] 的下一個指針指向了「元素：abcde，權(quán)重：4」的節(jié)點，然后將其和要查找的節(jié)點比較。雖然「元素：abcde，權(quán)重：4」的節(jié)點的權(quán)重和要查找的權(quán)重相同，但是當(dāng)前節(jié)點的 SDS 類型數(shù)據(jù)「大于」要查找的數(shù)據(jù)，所以會繼續(xù)跳到「元素：abc，權(quán)重：3」節(jié)點的下一層去找，也就是 leve[0]；
- 「元素：abc，權(quán)重：3」節(jié)點的 leve[0] 的下一個指針指向了「元素：abcd，權(quán)重：4」的節(jié)點，該節(jié)點正是要查找的節(jié)點，查詢結(jié)束。
跳表節(jié)點層數(shù)設(shè)置
跳表的相鄰兩層的節(jié)點數(shù)量的比例會影響跳表的查詢性能。
舉個例子，下圖的跳表，第二層的節(jié)點數(shù)量只有 1 個，而第一層的節(jié)點數(shù)量有 6 個。
這時，如果想要查詢節(jié)點 6，那基本就跟鏈表的查詢復(fù)雜度一樣，就需要在第一層的節(jié)點中依次順序查找，復(fù)雜度就是 O(N) 了。所以，為了降低查詢復(fù)雜度，我們就需要維持相鄰層結(jié)點數(shù)間的關(guān)系。
**跳表的相鄰兩層的節(jié)點數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)**。
下圖的跳表就是，相鄰兩層的節(jié)點數(shù)量的比例是 2 : 1。
那怎樣才能維持相鄰兩層的節(jié)點數(shù)量的比例為 2 : 1 呢？
如果采用新增節(jié)點或者刪除節(jié)點時，來調(diào)整跳表節(jié)點以維持比例的方法的話，會帶來額外的開銷。
Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點的時候，隨機生成每個節(jié)點的層數(shù)，并沒有嚴格維持相鄰兩層的節(jié)點數(shù)量比例為 2 : 1 的情況。
具體的做法是，跳表在創(chuàng)建節(jié)點時候，會生成范圍為[0-1]的一個隨機數(shù)，如果這個隨機數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個隨機數(shù)，直到隨機數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點的層數(shù)。
這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。
為什么用跳表而不用平衡樹？
為什么 Zset 的實現(xiàn)用跳表而不用平衡樹（如 AVL樹、紅黑樹等）？
對于這個問題，Redis的作者 @antirez 是怎么說的：
There are a few reasons:
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.
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.
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)存占用、對范圍查找的支持、實現(xiàn)難易程度這三方面總結(jié)的原因：
- 它們不是非常內(nèi)存密集型的?；旧嫌赡銢Q定。改變關(guān)于節(jié)點具有給定級別數(shù)的概率的參數(shù)將使其比 btree 占用更少的內(nèi)存。
- Zset 經(jīng)常需要執(zhí)行 ZRANGE 或 ZREVRANGE 的命令，即作為鏈表遍歷跳表。通過此操作，跳表的緩存局部性至少與其他類型的平衡樹一樣好。
- 它們更易于實現(xiàn)、調(diào)試等。例如，由于跳表的簡單性，我收到了一個補丁（已經(jīng)在Redis master中），其中擴展了跳表，在 O(log(N) 中實現(xiàn)了 ZRANK。它只需要對代碼進行少量修改。
我再詳細補充點：
- 從內(nèi)存占用上來比較，跳表比平衡樹更靈活一些。平衡樹每個節(jié)點包含 2 個指針（分別指向左右子樹），而跳表每個節(jié)點包含的指針數(shù)目平均為 1/(1-p)，具體取決于參數(shù) p 的大小。如果像 Redis里的實現(xiàn)一樣，取 p=1/4，那么平均每個節(jié)點包含 1.33 個指針，比平衡樹更有優(yōu)勢。
- 在做范圍查找的時候，跳表比平衡樹操作要簡單。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現(xiàn)。而在跳表上進行范圍查找就非常簡單，只需要在找到小值之后，對第 1 層鏈表進行若干步的遍歷就可以實現(xiàn)。
- 從算法實現(xiàn)難度上來比較，跳表比平衡樹要簡單得多。平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復(fù)雜，而跳表的插入和刪除只需要修改相鄰節(jié)點的指針，操作簡單又快速。
完！
下載文檔
