??在Redis中只有兩處使用到了跳躍表，一個是實現(xiàn)有序集合鍵，另一個就是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)，用來保存槽和鍵之間的關(guān)系。
1 跳躍表
??跳躍表是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向多個指向其他節(jié)點的指針，從而達到快速訪問的目的。
??可以將上面的結(jié)構(gòu)類比成樹的結(jié)構(gòu)，最底層是實際存儲的數(shù)據(jù)，第二層可以看作是第一級索引，第三層可以看作第二級索引……通過上面的結(jié)構(gòu)，查找的平均復(fù)雜度為O(logN)，大部分情況下，跳躍表可以和平衡樹相媲美。下圖顯示了查詢13的過程：
??數(shù)據(jù)越多，跳躍表相對于鏈表的查找優(yōu)勢就越明顯。
2 Redis跳躍表的實現(xiàn)
??Redis的跳躍表由在skiplistNode和zskiplist兩個結(jié)構(gòu)定義，其中skiplistNode結(jié)構(gòu)用于表示跳躍表的節(jié)點，而zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息，如節(jié)點的數(shù)量，以及指向表頭節(jié)點和表尾節(jié)點的指針等。
??上圖展示了一個有3條數(shù)據(jù)的跳躍表，左側(cè)部分是zskiplist結(jié)構(gòu)，該結(jié)構(gòu)包括如下屬性：
(1) header：指向跳躍表表頭節(jié)點的指針。
(2) tail：指向跳躍表表尾節(jié)點的指針。
(3) level：記錄目前跳躍表內(nèi)，層數(shù)最大那個節(jié)點的層數(shù)（不包括表頭節(jié)點）。
(4) length：記錄跳躍表的長度，即跳躍表的節(jié)點數(shù)（不包括表頭節(jié)點）
??僅靠多個跳躍表也可以組成一個跳躍表。
??但是通過使用一個zskiplist結(jié)構(gòu)來持有這些節(jié)點，程序可以更方便地對整個跳躍表進行處理，比如快速訪問表頭節(jié)點和表尾節(jié)點，或者快讀獲取跳躍表節(jié)點的數(shù)量。
??zskiplistNode結(jié)構(gòu)，包括以下屬性：
(1) 層（level）：節(jié)點中用L1、L2、L3表示節(jié)點的各個層，每個層都有兩個屬性：前進指針和跨度。其中跨度表示前進指針?biāo)赶蚬?jié)點和當(dāng)前節(jié)點的距離。當(dāng)程序從表頭向表尾遍歷時，訪問會沿著層的前進指針進行。
(2) 后退（backward）指針：節(jié)點中用BW字樣標(biāo)記節(jié)點的后退指針，它指向位于當(dāng)前節(jié)點的前一個節(jié)點，后退指針用于程序從表尾向表頭遍歷時使用。
(3) 分值（score）：是一個double類型的浮點數(shù)，跳躍表中的節(jié)點按照節(jié)點的分值從小到大排列。同一個跳躍表中，它的節(jié)點保存的對象必須是唯一的，但是節(jié)點保存的分值卻是可以相同的，對于分值相同的節(jié)點會按照成員對象在字典序的大小進行排序。
(4) 成員對象（obj）：各個節(jié)點所保存的成員對象。
??2.1 跳躍表節(jié)點
??zskiplistNode結(jié)構(gòu)定義
typedef struct zskiplistNode{
// 層
struct zskiplistLevel{
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level []
// 后退指針
struct zskiplistNode *backward;
// 分值，double類型的浮點數(shù)
double score;
// 成員對象
robj *obj;
} zskiplistNode
??2.1.1層
跳躍表節(jié)點的level數(shù)據(jù)可以包含多個元素，每隔元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層加快訪問節(jié)點的速度，一般來說，層數(shù)越多，訪問節(jié)點的速度就越快。
??每次創(chuàng)建一個新的跳躍表節(jié)點的時候，程序會根據(jù)冪次定律（power law，越大的數(shù)出現(xiàn)的概率越?。╇S機生成一個介于1到32之間的值作為level數(shù)組的大小，這個大小就是層的“高度”。
??2.1.2 前進指針
??每個層都有指向表尾方向的前進指針，用于從表頭向表尾訪問節(jié)點。下圖表示程序從表頭向表尾方向，遍歷跳躍表所有節(jié)點的路徑：
(1) 迭代程序首先訪問跳躍表的第一個節(jié)點（表頭），然后從第四層的前進指針移動到第二個節(jié)點。
(2) 在第二個節(jié)點時，程序沿著第二層的前進的前進指針移動到第三個節(jié)點。
(3) 在第三個節(jié)點時，程序沿著第二層的前進指針移動到第四個節(jié)點。
(4) 當(dāng)程序再次沿著第四個節(jié)點的前進指針移動時，它碰到一個NULL，程序知道這時已經(jīng)達到了跳躍表的表尾，于是遍歷結(jié)束。
??2.1.3 跨度
??層的跨度用于記錄兩個節(jié)點之間的距離：
- 兩個節(jié)點之間的跨度越大，它們相距得就越遠。
- 指向NULL的所有前進指針的跨度都為0，因為它們沒有連向任何節(jié)點。
??跨度是用來計算排位（rank）的：在查找某個節(jié)點的過程中，將沿途訪問過的所有層的跨度累加起來，得到的結(jié)果就是目標(biāo)節(jié)點在跳躍表中的排位。
??例如下圖，在跳躍表中查找分值為3.0、成員對象為o3的節(jié)點時，沿途經(jīng)歷的層：查找的過程中經(jīng)歷了一層，層的跨度為3，所以目標(biāo)節(jié)點在跳躍表中的排位是第3位。
??同理，分值為2.0、成員對象是o2的節(jié)點在跳躍表中的排位為2。
??2.1.4后退指針
??節(jié)點后退指針用于從表尾向表頭方向訪問節(jié)點：跟可以一次跳過多個節(jié)點的前進指針不同，因為每個節(jié)點只有一個后退節(jié)點，所以每次只能后退至一個節(jié)點。
??3 小結(jié)
??(1) 跳躍表是有序集合底層實現(xiàn)之一。Redis中只有有序集合和集群節(jié)點兩處使用到了跳躍表。
??(2) Redis的跳躍表是通過zskiplist和zskiplistNode兩個結(jié)構(gòu)組成。
??(3) 每個跳躍表節(jié)點的層高都是1到32之間的隨機數(shù)。
??(4) 在同一個跳躍表中，多個節(jié)點可以包含相同的分數(shù)值，但是成員對象必須是唯一的。
??(5) 跳躍表中的及誒按順序是按照分值排序的，當(dāng)分值大小相同時，按照成員對象的字典序進行排序。
??本文完
?? 注：本文參考《Redis設(shè)計與實現(xiàn)》，如發(fā)現(xiàn)錯誤，請指正！
