一.概述 跳躍表(skiplist)是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。在大部分情況下，跳躍表的效率可以和平衡樹（關係型資料庫的索引就是平衡樹結構）相媲美，並且因為跳躍表的實現比平衡樹要來得更為簡單，所以有不少程式使用跳躍表來代替平衡樹。 R ...
一.概述
跳躍表(skiplist)是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。在大部分情況下，跳躍表的效率可以和平衡樹（關係型資料庫的索引就是平衡樹結構）相媲美，並且因為跳躍表的實現比平衡樹要來得更為簡單，所以有不少程式使用跳躍表來代替平衡樹。
Redis使用跳躍表作為"有序集合鍵"的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員是比較長的字元串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現。
下麵用到的命令zadd和zrange。 使用zadd 命令將多個成員(number)及其score值加入到有序集key中。number是有序集成員，score可以是整數值或雙精度浮點數。使用zrange命令將返回有序集合中給定區間的元素，start從0開始，stop 結束下標。
-- zadd命令語法格式 ZADD key score member [[score member] [score member] ...] -- zrange命令語法格式 ZRANGE key start stop [WITHSCORES]
例1：下麵使用zadd將fruit-price作為一個有序集合鍵，每個節點元素包括score和number。其中 score是價格，number是水果名稱。再使用zrange 讀出有序集合元素。
127.0.0.1:6379> zadd fruit-price 5.0 banana 6.5 cherry 8.0 apple (integer) 3 127.0.0.1:6379> zadd fruit-price 4.0 pear (integer) 1 127.0.0.1:6379> zrange fruit-price 0 3 withscores 1) "pear" 2) "4" 3) "banana" 4) "5" 5) "cherry" 6) "6.5" 7) "apple" 8) "8"
在上例中fruit-price有序集合的所有數據都保存在一個跳躍表裡面，其中每個跳躍表節點都保存了一款水果的價格信息，所有水果按價錢從低到高在跳躍表裡面排序。對比鏈表和字典等數據結構在Redis內部廣泛應用不同，Redis只在兩個地方用到了跳躍表，一個是實現有序集合鍵，另一個是在集群節點中用作內部數據結構。
1.1 跳躍表的實現
Redis跳躍表由 redis.h/zskiplistNode和redis.h/zskiplist 兩個結構定義，其中zskiplistNode結構用於表示跳躍表節點, 而zskiplist結構則用於保存跳躍表節點的相關信息，比如節點數量，以及指向表頭節點和表尾節點的指針等等。
上圖中展示了一個跳躍表示例，位於是左邊的是zskiplist結構，該結構包括以下屬性：
(1) header: 指向跳躍表的表頭節點。這裡為第一個zskiplistNode。
(2) tail : 指向跳躍表的表尾節點。這裡為第四個zskiplistNode。
(3) level:記錄目前跳躍表內，zskiplistNode節點中最大的層數(表頭節點的層數不計算在內)。最大節點的層數是第四個zskiplistNode節點，值為5 (每個跳躍表節點的層高都是1到32之間的隨機數)。
(4) length: 記錄跳躍表的長度。也就是節點數量(表頭節點不計算在內)，這裡值是3。
上圖中右方四個zskiplistNode節點，包含以下屬性：
(1) 層level : 每個節點中用L1,L2,L3等字樣標記節點的各個層，每個層都帶有兩個屬性，包括前進指針和跨度。在上圖裡連線上帶有數字的箭頭就代表前進指針， 而那個數字就是跨度。當程式從表頭向表尾進行遍歷時,訪問會沿著層的前進指針進行。
(2) 後退(backward)指針: 節點中用BW字樣標記節點的後退指針，後退指針在程式從表尾向表頭遍歷時使用。
(3)分值(socre) : 各個節點中的1.0,2.0,3.0節點所保存的分值，在跳躍表中，節點按各自所保存的分值從小到大排列。
(4)成員對象(obj): 各個節點中的01,02,03是節點所保存的成員對象。
1.2 跳躍表節點
下麵對zskiplistNode和zskiplist兩個結構進行更詳細的介紹，跳躍表節點實現由redis.h/zskiplistNode結構定義。
typedef struct zskiplistNode{ //層 struct zskiplistNode{ //前進指針 struct zskiplistNode *forward; //跨度 unsigned int span; }level[]; //後退指針 struct zskiplistNode *backward; //分值 double score; //成員對象 robj *obj; }zskiplistNode;
(1) 層：跳躍表節點的level數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程式可以通過這些層來加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快。
(2) 前進指針：每個層都有一個指向表尾方向的前進指針(level[i].forward屬性)，用於從表頭向表尾方向訪問節點。
如上圖所示: 遍歷是程式首先訪問跳躍表的第一個節點(表頭)，然後從第四層(L4)的前進指針移動到表中的第二個節點。在第二個節點時，程式沿著第二層(L2)的前進指針移動到表中的第三個節點。在第三個節點時，程式同樣沿著第二層(L2)的前進指針移動到表中的第四個節點。當程式再次沿著第四個節點前進指針移動時，遇到null,程式知道這時已經到達了跳躍表的表尾，於是結束這次遍歷。
(3) 跨度：層的跨度(level[i].span屬性)用於記錄兩個節點之間的距離：兩個節點之間的跨度越大，它們相距就越遠。 指向null的所有前進指針跨度都為0,因為它們沒有連向任何節點。對於遍歷操作只使用前進指針就可以完成了，跨度實際上是用來計算排位的。
(4) 後退指針：節點的後退指針(backward屬性) 用於從表尾向表頭方向訪問節點。與前進指針不同，前進指針一次可以跳過多個節點，而每個節點只有一個後退指針，所以每次只能後退至前一個節點。
(5) 分值和成員：節點的分值(score屬性)是一個double類型的浮點數，跳躍表中的所有節點都按分值從小到大來排序。節點的成員對象(obj屬性)是一個指針，它指向一個字元串對象，而字元串對象則保存著一個SDS值。在同一個跳躍表中，各個節點保存的成員對象必須是唯一的，但是多個節點保存的分值卻可以是相同的，分值相同的節點將按照成員對象在字典中的大小來進行排序，成員對象較小的節點會排在前面(靠近表頭的方向)。
例2: 分值相同的，按成員對象來排序。 127.0.0.1:6379> zadd test 1.0 a (integer) 1 127.0.0.1:6379> zadd test 1.0 c (integer) 1 127.0.0.1:6379> zadd test 1.0 b (integer) 1 127.0.0.1:6379> zrange test 0 2 withscores 1) "a" 2) "1" 3) "b" 4) "1" 5) "c" 6) "1"
1.3 跳躍表
僅靠多個跳躍表節點就可以組成一個跳躍表,但通過使用一個zskplist結構來持有這些節點，程式可以更方便地對整個跳躍表進行處理。
typedef struct zskiplist { //表頭節點和表尾節點 struct skiplistNode *header, *tail; //表中節點數量 unsigned long length; //表中層數最大的節點的層數 int level; }zskiplist
