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