位于圖片最左邊的是 zskiplist 結(jié)構(gòu)吹散， 該結(jié)構(gòu)包含以下屬性，右邊是各個(gè)跳躍表節(jié)點(diǎn)
左邊的zskiplist結(jié)構(gòu)包括了一下幾個(gè)屬性：
- header ：指向跳躍表的表頭節(jié)點(diǎn)空民。
- tail ：指向跳躍表的表尾節(jié)點(diǎn)。
- level ：記錄目前跳躍表內(nèi)界轩，層數(shù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)（表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi)）。2^5=32
- length ：記錄跳躍表的長(zhǎng)度浊猾，也即是，跳躍表目前包含節(jié)點(diǎn)的數(shù)量（表頭節(jié)點(diǎn)不計(jì)算在內(nèi)）葫慎。
位于 zskiplist 結(jié)構(gòu)右方的是四個(gè) zskiplistNode 結(jié)構(gòu)， 該結(jié)構(gòu)包含以下屬性：
- 層（level）：節(jié)點(diǎn)中用 L1 幅疼、 L2 米奸、 L3 等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層悴晰， L1 代表第一層， L2 代表第二層，以此類推铡溪。每個(gè)層都帶有兩個(gè)屬性：前進(jìn)指針和跨度漂辐。前進(jìn)指針用于訪問位于表尾方向的其他節(jié)點(diǎn)，而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離棕硫。在上面的圖片中髓涯，連線上帶有數(shù)字的箭頭就代表前進(jìn)指針，而那個(gè)數(shù)字就是跨度哈扮。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí)纬纪，訪問會(huì)沿著層的前進(jìn)指針進(jìn)行。
- 后退（backward）指針：節(jié)點(diǎn)中用 BW 字樣標(biāo)記節(jié)點(diǎn)的后退指針滑肉，它指向位于當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)包各。后退指針在程序從表尾向表頭遍歷時(shí)使用。
- 分值（score）：各個(gè)節(jié)點(diǎn)中的 1.0 靶庙、 2.0 和 3.0 是節(jié)點(diǎn)所保存的分值问畅。在跳躍表中，節(jié)點(diǎn)按各自所保存的分值從小到大排列六荒。
- 成員對(duì)象（obj）：各個(gè)節(jié)點(diǎn)中的 o1 护姆、 o2 和 o3 是節(jié)點(diǎn)所保存的成員對(duì)象。
跳躍表節(jié)點(diǎn)
節(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct zskiplistNode {
// 后退指針
struct zskiplistNode *backward;
// 分值
double score;
// 成員對(duì)象
robj *obj;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
層
跳躍表節(jié)點(diǎn)的 level 數(shù)組可以包含多個(gè)元素掏击， 每個(gè)元素都包含一個(gè)指向其他節(jié)點(diǎn)的指針卵皂， 程序可以通過這些層來(lái)加快訪問其他節(jié)點(diǎn)的速度，一般來(lái)說(shuō)铐料， 層的數(shù)量越多渐裂， 訪問其他節(jié)點(diǎn)的速度就越快豺旬。每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候钠惩， 程序都根據(jù)冪次定律 （power law，越大的數(shù)出現(xiàn)的概率越凶逶摹）隨機(jī)生成一個(gè)介于 1 和 32 之間的值作為 level 數(shù)組的大小篓跛， 這個(gè)大小就是層的“高度”。圖 5-2 分別展示了三個(gè)高度為 1 層坦刀、 3 層和 5 層的節(jié)點(diǎn)愧沟， 因?yàn)?C 語(yǔ)言的數(shù)組索引總是從 0 開始的， 所以節(jié)點(diǎn)的第一層是 level[0]鲤遥， 而第二層是 level[1]沐寺， 以此類推。
前進(jìn)指針
每個(gè)層都有一個(gè)指向表尾方向的前進(jìn)指針（level[i].forward 屬性）盖奈， 用于從表頭向表尾方向訪問節(jié)點(diǎn)混坞。
圖 5-3 用虛線表示出了程序從表頭向表尾方向， 遍歷跳躍表中所有節(jié)點(diǎn)的路徑：
- 迭代程序首先訪問跳躍表的第一個(gè)節(jié)點(diǎn)（表頭）， 然后從第四層的前進(jìn)指針移動(dòng)到表中的第二個(gè)節(jié)點(diǎn)究孕。
- 在第二個(gè)節(jié)點(diǎn)時(shí)啥酱， 程序沿著第二層的前進(jìn)指針移動(dòng)到表中的第三個(gè)節(jié)點(diǎn)。
- 在第三個(gè)節(jié)點(diǎn)時(shí)镶殷， 程序同樣沿著第二層的前進(jìn)指針移動(dòng)到表中的第四個(gè)節(jié)點(diǎn)绘趋。
- 當(dāng)程序再次沿著第四個(gè)節(jié)點(diǎn)的前進(jìn)指針移動(dòng)時(shí)颗管， 它碰到一個(gè) NULL ， 程序知道這時(shí)已經(jīng)到達(dá)了跳躍表的表尾拷呆， 于是結(jié)束這次遍歷茬斧。
后退指針
前進(jìn)指針可以跳躍项秉，后退指針只能每次退回一層慷彤。
分值和成員
節(jié)點(diǎn)的分值（score 屬性）是一個(gè) double 類型的浮點(diǎn)數(shù)， 跳躍表中的所有節(jié)點(diǎn)都按分值從小到大來(lái)排序岁诉。
節(jié)點(diǎn)的成員對(duì)象（obj 屬性）是一個(gè)指針涕癣， 它指向一個(gè)字符串對(duì)象前标， 而字符串對(duì)象則保存著一個(gè) SDS 值。
在同一個(gè)跳躍表中只搁， 各個(gè)節(jié)點(diǎn)保存的成員對(duì)象必須是唯一的俭尖， 但是多個(gè)節(jié)點(diǎn)保存的分值卻可以是相同的： 分值相同的節(jié)點(diǎn)將按照成員對(duì)象在字典序中的大小來(lái)進(jìn)行排序， 成員對(duì)象較小的節(jié)點(diǎn)會(huì)排在前面（靠近表頭的方向）明肮， 而成員對(duì)象較大的節(jié)點(diǎn)則會(huì)排在后面（靠近表尾的方向）柿估。
舉個(gè)例子， 在圖 5-7 所示的跳躍表中的妖， 三個(gè)跳躍表節(jié)點(diǎn)都保存了相同的分值 10086.0 足陨， 但保存成員對(duì)象 o1 的節(jié)點(diǎn)卻排在保存成員對(duì)象 o2和 o3 的節(jié)點(diǎn)之前， 而保存成員對(duì)象 o2 的節(jié)點(diǎn)又排在保存成員對(duì)象 o3 的節(jié)點(diǎn)之前星虹， 由此可見宽涌， o1 蝶棋、 o2 、 o3 三個(gè)成員對(duì)象在字典中的排序?yàn)?o1 <= o2 <= o3 兼贸。
跳躍表
使用一個(gè) zskiplist 結(jié)構(gòu)來(lái)持有這些節(jié)點(diǎn)溶诞， 程序可以更方便地對(duì)整個(gè)跳躍表進(jìn)行處理罕偎， 比如快速訪問跳躍表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)很澄， 又或者快速地獲取跳躍表節(jié)點(diǎn)的數(shù)量（也即是跳躍表的長(zhǎng)度）等信息。
zskiplist 結(jié)構(gòu)的定義如下：
typedef struct zskiplist {
// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
struct zskiplistNode *header, *tail;
// 表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
// 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
} zskiplist;
header 和 tail 指針分別指向跳躍表的表頭和表尾節(jié)點(diǎn)俏站， 通過這兩個(gè)指針肄扎， 程序定位表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 。通過使用 length屬性來(lái)記錄節(jié)點(diǎn)的數(shù)量旭等， 程序可以在 O(1) 復(fù)雜度內(nèi)返回跳躍表的長(zhǎng)度衡载。level 屬性則用于在 O(1)復(fù)雜度內(nèi)獲取跳躍表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量痰娱， 注意表頭節(jié)點(diǎn)的層高并不計(jì)算在內(nèi)梨睁。
跳躍表在redis中用于實(shí)現(xiàn)有序集合
關(guān)于跳躍表的增刪改查demo可以看這個(gè)http://blog.csdn.net/ict2014/article/details/17394259
