[TOC] ### **什么是跳躍表** ***** 跳躍表（skiplist）是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。 **跳躍表詳情參考**：[跳躍表](%E8%B7%B3%E8%B7%83%E8%A1%A8.md) ### **Redis中跳躍表的實現** ***** Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結構定義： zskiplistNode表示跳躍表節點信息，zskiplist跳躍表節點的相關信息：節點的數量，以及指向表頭節點和表尾節點的指針 ` `  #### **跳躍表節點** ***** **zskiplistNode結構** ``` typedef struct zskiplistNode { //層 struct zskiplistLevel { // 前進指針 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; // 后退指針 struct zskiplistNode *backward; // 分值 double score; // 成員對象 robj *obj; } zskiplistNode; ``` ##### **層（level）** 跳躍表節點的level數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程序可以通過這些層來加快訪問其他節點的速度，一般來說，**層的數量越多，訪問其他節點的速度就越快**。每個層都帶有兩個屬性：**前進指針和跨度**。前進指針用于訪問位于表尾方向的其他節點，而跨度則記錄了前進指針所指向節點和當前節點的距離。在上面的圖片中，連線上帶有數字的箭頭就代表前進指針，而那個數字就是跨度。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。 >每次創建一個新跳躍表節點的時候，程序都根據冪次定律（power law，越大的數出現的概率越小）隨機生成一個介于1和32之間的值作為level數組的大小，這個大小就是層的“高度”。 ##### **前進指針** 每個層都有一個指向表尾方向的前進指針（level\[i\].forward屬性），用于從表頭向表尾方向訪問節點。圖5-3用虛線表示出了程序從表頭向表尾方向，遍歷跳躍表中所有節點的路徑：  **遍歷整個跳躍表**  1）迭代程序首先訪問跳躍表的第一個節點（表頭），然后從第四層的前進指針移動到表中的第二個節點。 2）在第二個節點時，程序沿著第二層的前進指針移動到表中的第三個節點。 3）在第三個節點時，程序同樣沿著第二層的前進指針移動到表中的第四個節點。 4）當程序再次沿著第四個節點的前進指針移動時，它碰到一個NULL，程序知道這時已經到達了跳躍表的表尾，于是結束這次遍歷。 ##### **跨度** 層的跨度（level\[i\].span屬性）用于記錄兩個節點之間的距離： ·兩個節點之間的跨度越大，它們相距得就越遠。 ·指向NULL的所有前進指針的跨度都為0，因為它們沒有連向任何節點。 跨度實際上是用來計算排位（rank）的：在查找某個節點的過程中，將沿途訪問過的所有層的跨度累計起來，得到的結果就是目標節點在跳躍表中的排位。 >**跨度和遍歷操作無關**，**遍歷操作**只使用**前進指針**就可以完成了 ##### **后退（backward）指針** 節點中用BW字樣標記節點的后退指針，它指向位于當前節點的前一個節點。后退指針在程序從表尾向表頭遍歷時使用。 ##### **分值（score）** 節點的分值（score屬性）是一個**double類型的浮點數**，跳躍表中的所有節點都按**分值從小到大來排序**。節點的成員對象（obj屬性）是一個指針，它指向一個字符串對象，而**字符串對象則保存著一個SDS值**。 ##### **成員對象（obj）** **各個節點保存的成員對象必須是唯一的**，但是多個節點保存的分值卻可以是相同的：**分值相同的節點將按照成員對象在字典序中的大小來進行排序**，成員對象較小的節點會排在前面（靠近表頭的方向），而成員對象較大的節點則會排在后面（靠近表尾的方向）。 >注意表頭節點和其他節點的構造是一樣的：表頭節點也有后退指針、分值和成員對象，不過表頭節點的這些屬性都不會被用到，所以圖中省略了這些部分，只顯示了表頭節點的各個層。 ##### 跳躍表 **zskiplist結構**： ``` typedef struct zskiplist { // 表頭節點和表尾節點 structz skiplistNode *header, *tail; // 表中節點的數量 unsigned long length; // 表中層數最大的節點的層數 int level; } zskiplist; ``` * header：指向跳躍表的表頭節點。 * tail：指向跳躍表的表尾節點。 * level：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）。 * length：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在內）  ` ` header和tail指針分別指向跳躍表的表頭和表尾節點，通過這兩個指針，程序定位表頭節點和表尾節點的復雜度為O（1）。 ` ` ### **知識點** ***** ##### **跳躍表的時間復雜度** 跳躍表支持平均O（logN）、最壞O（N）復雜度的節點查找，還可以通過順序性操作來批量處理節點。 >跳躍表的效率可以和平衡樹相媲美，并且因為跳躍表的實現比平衡樹要來得更為簡單，所以有不少程序都使用跳躍表來代替平衡樹。 ##### **跳躍表在Redis的用途** 和鏈表、字典等數據結構被廣泛地應用在Redis內部不同，Redis只在兩個地方用到了跳躍表，一個是實現`有序集合鍵`，另一個是在`集群節點`中用作`內部數據結構`，除此之外，跳躍表在Redis里面沒有其他用途。 * 跳躍表是有序集合的底層實現之一。 * Redis的跳躍表實現由zskiplist和zskiplistNode兩個結構組成，其中zskiplist用于保存跳躍表信息（比如表頭節點、表尾節點、長度），而zskiplistNode則用于表示跳躍表節點。 * 每個跳躍表節點的層高都是1至32之間的隨機數。 * 在同一個跳躍表中，多個節點可以包含相同的分值，但每個節點的成員對象必須是唯一的。 * 跳躍表中的節點按照分值大小進行排序，當分值相同時，節點按照成員對象的大小進行排序。