一、概述

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。

如下，對于單個鏈表來講，即便鏈表中存儲的數(shù)據(jù)是有序的，如果我們要向在其中查找某個數(shù)據(jù)，它只能從頭到尾遍歷鏈表。這樣查找效率就會很低，時間復雜度會很高，達到了O(n)。

如果我們想要提高其查詢效率，可以考慮在鏈表上構(gòu)建索引的 方式，每兩個節(jié)點提取一個節(jié)點到上級，我們把抽出來的那一級就叫做索引，如下：

此時，我們假設(shè)要查找節(jié)點8，我們可以先在索引層遍歷，當遍歷到索引層中值為7的節(jié)點時，發(fā)現(xiàn)下一個節(jié)點是9，那么要查找的節(jié)點肯定在這兩個節(jié)點之間，我們下降到鏈表層繼續(xù)遍歷就找到了8這個節(jié)點。原來我們在單鏈表中找到8這個節(jié)點要遍歷8個節(jié)點，而現(xiàn)在有了一級索引后，只需要遍歷5個節(jié)點。

從上個例子中，我們可以看出，加來一層索引后，查找一個節(jié)點需要遍歷的節(jié)點個數(shù)減少了，也就是說查詢效率得到了提升，同理我們在一級索引的基礎(chǔ)上，在加二級索引。

從圖中我們可以看出，查找效率又有了提升，因為在這里例子中我們的數(shù)據(jù)量很少，當有大量的數(shù)據(jù)時，我們可以增加多級索引，在查詢時，效率可以得到明顯的提升。像這種鏈表增加多種索引的結(jié)構(gòu)，就是跳躍表。

Redis使用跳躍表作為有序集合鍵的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員（member）是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。

二、跳躍表的實現(xiàn)

Redis的跳躍表由zskiplistNode和zskiplist兩個結(jié)構(gòu)定義，其中zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點，而zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息，比如節(jié)點的數(shù)量，以及指向表頭節(jié)點和表尾節(jié)點的指針等等，如下，是一個跳躍表的結(jié)構(gòu)：

上圖片最左邊的是zskiplist結(jié)構(gòu)，該結(jié)構(gòu)包含以下屬性：?

• header：指向跳躍表的表頭節(jié)點，通過這個指針程序定位表頭節(jié)點的時間復雜度就為O(1)；
• tail：指向跳躍表的表尾節(jié)點，通過這個指針程序定位表尾節(jié)點的時間復雜度就為O(1)；
• level：記錄目前跳躍表內(nèi)，層數(shù)最大的那個節(jié)點的層數(shù)（表頭節(jié)點的層數(shù)不計算在內(nèi)）；通過這個屬性可以再O(1)的時間復雜度內(nèi)獲取層高最高的節(jié)點的層數(shù)
• length：記錄跳躍表的長度，也即是，跳躍表目前包含節(jié)點的數(shù)量（表頭節(jié)點不計算在內(nèi)）通過這個屬性，程序可以再O(1)的時間復雜度內(nèi)返回跳躍表的長度

上圖位于zskiplist結(jié)構(gòu)右方的是四個zskiplistNode結(jié)構(gòu)，該結(jié)構(gòu)包含以下屬性：?

• 層（level）：節(jié)點中用L1、L2、L3等字樣標記節(jié)點的各個層，L1代表第一層，L2代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節(jié)點，而跨度則記錄了前進指針所指向節(jié)點和當前節(jié)點的距離（跨度越大，距離越遠）。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進指針，而那個數(shù)字就是跨度。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。
• 后退（backward）指針：節(jié)點中用BW字樣標記節(jié)點的后退指針，它指向位于當前節(jié)點的前一個節(jié)點。后退指針在程序從表尾向表頭遍歷時使用
• 分值（score）：各個節(jié)點中的1.0、2.0和3.0是節(jié)點所保存的分值。在跳躍表中，節(jié)點按各自所保存的分值從小到大排列。
• 成員對象（obj）：各個節(jié)點中的o1、o2和o3是節(jié)點所保存的成員對象

2.1 跳躍表節(jié)點的zskiplisNode結(jié)構(gòu)定義

typedef struct zskiplistNode {
    // 層
    struct zskiplistLevel {
        // 前進指針
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 后退指針
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成員對象
    robj *obj;
} zskiplistNode;

層：跳躍表節(jié)點的level數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點的速度就越快。
每個層都有一個指向表尾方向的前進指針（level[i].forward屬性），用于從表頭向表尾方向訪問節(jié)點
層的跨度（level[i].span屬性）用于記錄兩個節(jié)點之間的距離。
節(jié)點的后退指針（backward屬性）用于從表尾向表頭方向訪問節(jié)點：跟可以一次跳過多個節(jié)點的前進指針不同，因為每個節(jié)點只有一個后退指針，所以每次只能后退至前一個節(jié)點
節(jié)點的分值（score屬性）是一個double類型的浮點數(shù)，跳躍表中的所有節(jié)點都按分值從小到大來排序；
節(jié)點的成員對象（obj屬性）是一個指針，它指向一個字符串對象，而字符串對象則保存著一個SDS值

2.2?zskiplist結(jié)構(gòu)的定義

typedef struct zskiplist {
    // 表頭節(jié)點和表尾節(jié)點
    structz skiplistNode *header, *tail;
    // 表中節(jié)點的數(shù)量
    unsigned long length;
    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;
} zskiplist;

header和tail指針分別指向跳躍表的表頭和表尾節(jié)點，通過這兩個指針，程序定位表頭節(jié)點和表尾節(jié)點的復雜度為O(1)。

通過使用length屬性來記錄節(jié)點的數(shù)量，程序可以在O(1)復雜度內(nèi)返回跳躍表的長度。

三、結(jié)束

Redis使用跳躍表作為有序集合鍵的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員（member）是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。之所以如此，是因為跳躍表在鏈表的基礎(chǔ)上增加了多級索引以提升查找的效率，但其是一個空間換時間的方案，必然會帶來一個問題——索引是占內(nèi)存的。原始鏈表中存儲的有可能是很大的對象，而索引結(jié)點只需要存儲關(guān)鍵值值和幾個指針，并不需要存儲對象，因此當節(jié)點本身比較大或者元素數(shù)量比較多的時候，其優(yōu)勢必然會被放大，而缺點則可以忽略。