一.概述
跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。在大部分情況下，跳躍表的效率可以和平衡樹（關(guān)系型數(shù)據(jù)庫的索引就是平衡樹結(jié)構(gòu)）相媲美，并且因為跳躍表的實現(xiàn)比平衡樹要來得更為簡單，所以有不少程序使用跳躍表來代替平衡樹。
Redis使用跳躍表作為"有序集合鍵"的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。
下面用到的命令zadd和zrange。 使用zadd 命令將多個成員(number)及其score值加入到有序集key中。number是有序集成員，score可以是整數(shù)值或雙精度浮點數(shù)。使用zrange命令將返回有序集合中給定區(qū)間的元素，start從0開始，stop 結(jié)束下標。
-- zadd命令語法格式
? ? ZADD key score member [[score member] [score member] ...]
? ? -- zrange命令語法格式
? ? ZRANGE key start stop [WITHSCORES]
例1：下面使用zadd將fruit-price作為一個有序集合鍵，每個節(jié)點元素包括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有序集合的所有數(shù)據(jù)都保存在一個跳躍表里面，其中每個跳躍表節(jié)點都保存了一款水果的價格信息，所有水果按價錢從低到高在跳躍表里面排序。對比鏈表和字典等數(shù)據(jù)結(jié)構(gòu)在Redis內(nèi)部廣泛應(yīng)用不同，Redis只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
1.1 跳躍表的實現(xiàn)
Redis跳躍表由 redis.h/zskiplistNode和redis.h/zskiplist 兩個結(jié)構(gòu)定義，其中zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點, ?而zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息，比如節(jié)點數(shù)量，以及指向表頭節(jié)點和表尾節(jié)點的指針等等。
上圖中展示了一個跳躍表示例，位于是左邊的是zskiplist結(jié)構(gòu)，該結(jié)構(gòu)包括以下屬性：
(1) header: 指向跳躍表的表頭節(jié)點。這里為第一個zskiplistNode。
(2) tail : 指向跳躍表的表尾節(jié)點。這里為第四個zskiplistNode。
(3) level:記錄目前跳躍表內(nèi)，zskiplistNode節(jié)點中最大的層數(shù)(表頭節(jié)點的層數(shù)不計算在內(nèi))。最大節(jié)點的層數(shù)是第四個zskiplistNode節(jié)點，值為5 (每個跳躍表節(jié)點的層高都是1到32之間的隨機數(shù))。
(4) length: 記錄跳躍表的長度。也就是節(jié)點數(shù)量(表頭節(jié)點不計算在內(nèi))，這里值是3。
上圖中右方四個zskiplistNode節(jié)點，包含以下屬性：
(1)?層level :? 每個節(jié)點中用L1,L2,L3等字樣標記節(jié)點的各個層，每個層都帶有兩個屬性，包括前進指針和跨度。在上圖里連線上帶有數(shù)字的箭頭就代表前進指針， 而那個數(shù)字就是跨度。當(dāng)程序從表頭向表尾進行遍歷時,訪問會沿著層的前進指針進行。
(2)?后退(backward)指針: 節(jié)點中用BW字樣標記節(jié)點的后退指針，后退指針在程序從表尾向表頭遍歷時使用。
(3)分值(socre)?: 各個節(jié)點中的1.0,2.0,3.0節(jié)點所保存的分值，在跳躍表中，節(jié)點按各自所保存的分值從小到大排列。
(4)成員對象(obj): 各個節(jié)點中的01,02,03是節(jié)點所保存的成員對象。
(5)Java架構(gòu)交流學(xué)習(xí)圈：874811168 面向具有Java開發(fā)經(jīng)驗人群 幫助突破瓶頸 提升思維能力。
1.2 跳躍表節(jié)點
下面對zskiplistNode和zskiplist兩個結(jié)構(gòu)進行更詳細的介紹，跳躍表節(jié)點實現(xiàn)由redis.h/zskiplistNode結(jié)構(gòu)定義。
typedef struct zskiplistNode{
? ? ? ? ? ? //層
? ? ? ? ? ? struct zskiplistNode{
? ? ? ? ? ? ? ? //前進指針
? ? ? ? ? ? ? ? struct zskiplistNode *forward;
? ? ? ? ? ? ? ? //跨度
? ? ? ? ? ? ? ? unsigned int span;
? ? ? ? ? ? }level[];
? ? ? ? ? ? //后退指針?
? ? ? ? ? ? struct zskiplistNode *backward;
? ? ? ? ? ? //分值
? ? ? ? ? ? double score;
? ? ? ? ? ? //成員對象
? ? ? ? ? ? robj *obj;
? ? ? ? }zskiplistNode;
(1) 層：跳躍表節(jié)點的level數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點的速度就越快。
(2) 前進指針：每個層都有一個指向表尾方向的前進指針(level[i].forward屬性)，用于從表頭向表尾方向訪問節(jié)點。
如上圖所示: 遍歷是程序首先訪問跳躍表的第一個節(jié)點(表頭)，然后從第四層(L4)的前進指針移動到表中的第二個節(jié)點。在第二個節(jié)點時，程序沿著第二層(L2)的前進指針移動到表中的第三個節(jié)點。在第三個節(jié)點時，程序同樣沿著第二層(L2)的前進指針移動到表中的第四個節(jié)點。當(dāng)程序再次沿著第四個節(jié)點前進指針移動時，遇到null,程序知道這時已經(jīng)到達了跳躍表的表尾，于是結(jié)束這次遍歷。
(3) 跨度：層的跨度(level[i].span屬性)用于記錄兩個節(jié)點之間的距離：兩個節(jié)點之間的跨度越大，它們相距就越遠。 指向null的所有前進指針跨度都為0,因為它們沒有連向任何節(jié)點。對于遍歷操作只使用前進指針就可以完成了，跨度實際上是用來計算排位的。
(4) 后退指針：節(jié)點的后退指針(backward屬性) 用于從表尾向表頭方向訪問節(jié)點。與前進指針不同，前進指針一次可以跳過多個節(jié)點，而每個節(jié)點只有一個后退指針，所以每次只能后退至前一個節(jié)點。
(5) 分值和成員：節(jié)點的分值(score屬性)是一個double類型的浮點數(shù)，跳躍表中的所有節(jié)點都按分值從小到大來排序。節(jié)點的成員對象(obj屬性)是一個指針，它指向一個字符串對象，而字符串對象則保存著一個SDS值。在同一個跳躍表中，各個節(jié)點保存的成員對象必須是唯一的，但是多個節(jié)點保存的分值卻可以是相同的，分值相同的節(jié)點將按照成員對象在字典中的大小來進行排序，成員對象較小的節(jié)點會排在前面(靠近表頭的方向)。Java架構(gòu)交流學(xué)習(xí)圈：874811168 面向具有Java開發(fā)經(jīng)驗人群 幫助突破瓶頸 提升思維能力。
例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 跳躍表
僅靠多個跳躍表節(jié)點就可以組成一個跳躍表,但通過使用一個zskplist結(jié)構(gòu)來持有這些節(jié)點，程序可以更方便地對整個跳躍表進行處理。
typedef struct zskiplist
? ? ? ? {
? ? ? ? ? ? //表頭節(jié)點和表尾節(jié)點
? ? ? ? ? ? struct skiplistNode *header, *tail;
? ? ? ? ? ? //表中節(jié)點數(shù)量
? ? ? ? ? ? unsigned long length;
? ? ? ? ? ? //表中層數(shù)最大的節(jié)點的層數(shù)
? ? ? ? ? ? ? int level;
? ? ? ? }zskiplist
