一.概述

　　跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。在大部分情況下，跳躍表的效率可以和平衡樹(shù)（關(guān)系型數(shù)據(jù)庫(kù)的索引就是平衡樹(shù)結(jié)構(gòu)）相媲美，并且因?yàn)樘S表的實(shí)現(xiàn)比平衡樹(shù)要來(lái)得更為簡(jiǎn)單，所以有不少程序使用跳躍表來(lái)代替平衡樹(shù)。

　　Redis使用跳躍表作為"有序集合鍵"的底層實(shí)現(xiàn)之一，如果一個(gè)有序集合包含的元素?cái)?shù)量比較多，又或者有序集合中元素的成員是比較長(zhǎng)的字符串時(shí)，Redis就會(huì)使用跳躍表來(lái)作為有序集合鍵的底層實(shí)現(xiàn)。

　　下面用到的命令zadd和zrange。 使用zadd 命令將多個(gè)成員(number)及其score值加入到有序集key中。number是有序集成員，score可以是整數(shù)值或雙精度浮點(diǎn)數(shù)。使用zrange命令將返回有序集合中給定區(qū)間的元素，start從0開(kāi)始，stop 結(jié)束下標(biāo)。

-- zadd命令語(yǔ)法格式

? ? ZADD key score member [[score member] [score member] ...]

? ? -- zrange命令語(yǔ)法格式

? ? ZRANGE key start stop [WITHSCORES]

　　例1：下面使用zadd將fruit-price作為一個(gè)有序集合鍵，每個(gè)節(jié)點(diǎn)元素包括score和number。其中 score是價(jià)格，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ù)都保存在一個(gè)跳躍表里面，其中每個(gè)跳躍表節(jié)點(diǎn)都保存了一款水果的價(jià)格信息，所有水果按價(jià)錢(qián)從低到高在跳躍表里面排序。對(duì)比鏈表和字典等數(shù)據(jù)結(jié)構(gòu)在Redis內(nèi)部廣泛應(yīng)用不同，Redis只在兩個(gè)地方用到了跳躍表，一個(gè)是實(shí)現(xiàn)有序集合鍵，另一個(gè)是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

　　1.1 跳躍表的實(shí)現(xiàn)

　　　　Redis跳躍表由 redis.h/zskiplistNode和redis.h/zskiplist 兩個(gè)結(jié)構(gòu)定義，其中zskiplistNode結(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è)跳躍表示例，位于是左邊的是zskiplist結(jié)構(gòu)，該結(jié)構(gòu)包括以下屬性：

(1) header: 指向跳躍表的表頭節(jié)點(diǎn)。這里為第一個(gè)zskiplistNode。

(2) tail : 指向跳躍表的表尾節(jié)點(diǎn)。這里為第四個(gè)zskiplistNode。

(3) level:記錄目前跳躍表內(nèi)，zskiplistNode節(jié)點(diǎn)中最大的層數(shù)(表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi))。最大節(jié)點(diǎn)的層數(shù)是第四個(gè)zskiplistNode節(jié)點(diǎn)，值為5 (每個(gè)跳躍表節(jié)點(diǎn)的層高都是1到32之間的隨機(jī)數(shù))。

(4) length: 記錄跳躍表的長(zhǎng)度。也就是節(jié)點(diǎn)數(shù)量(表頭節(jié)點(diǎn)不計(jì)算在內(nèi))，這里值是3。

　　　　上圖中右方四個(gè)zskiplistNode節(jié)點(diǎn)，包含以下屬性：

(1)?層level :? 每個(gè)節(jié)點(diǎn)中用L1,L2,L3等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層，每個(gè)層都帶有兩個(gè)屬性，包括前進(jìn)指針和跨度。在上圖里連線上帶有數(shù)字的箭頭就代表前進(jìn)指針， 而那個(gè)數(shù)字就是跨度。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí),訪問(wèn)會(huì)沿著層的前進(jìn)指針進(jìn)行。

(2)?后退(backward)指針: 節(jié)點(diǎn)中用BW字樣標(biāo)記節(jié)點(diǎn)的后退指針，后退指針在程序從表尾向表頭遍歷時(shí)使用。

(3)分值(socre)?: 各個(gè)節(jié)點(diǎn)中的1.0,2.0,3.0節(jié)點(diǎn)所保存的分值，在跳躍表中，節(jié)點(diǎn)按各自所保存的分值從小到大排列。

(4)成員對(duì)象(obj): 各個(gè)節(jié)點(diǎn)中的01,02,03是節(jié)點(diǎn)所保存的成員對(duì)象。

(5)Java架構(gòu)交流學(xué)習(xí)圈：874811168 面向具有Java開(kāi)發(fā)經(jīng)驗(yàn)人群 幫助突破瓶頸 提升思維能力。

　　1.2 跳躍表節(jié)點(diǎn)

　　　　下面對(duì)zskiplistNode和zskiplist兩個(gè)結(jié)構(gòu)進(jìn)行更詳細(xì)的介紹，跳躍表節(jié)點(diǎn)實(shí)現(xiàn)由redis.h/zskiplistNode結(jié)構(gòu)定義。

typedef struct zskiplistNode{

? ? ? ? ? ? //層

? ? ? ? ? ? struct zskiplistNode{

? ? ? ? ? ? ? ? //前進(jìn)指針

? ? ? ? ? ? ? ? struct zskiplistNode *forward;

? ? ? ? ? ? ? ? //跨度

? ? ? ? ? ? ? ? unsigned int span;

? ? ? ? ? ? }level[];

? ? ? ? ? ? //后退指針?

? ? ? ? ? ? struct zskiplistNode *backward;

? ? ? ? ? ? //分值

? ? ? ? ? ? double score;

? ? ? ? ? ? //成員對(duì)象

? ? ? ? ? ? robj *obj;

? ? ? ? }zskiplistNode;

　　　　(1) 層：跳躍表節(jié)點(diǎn)的level數(shù)組可以包含多個(gè)元素，每個(gè)元素都包含一個(gè)指向其他節(jié)點(diǎn)的指針，程序可以通過(guò)這些層來(lái)加快訪問(wèn)其他節(jié)點(diǎn)的速度，一般來(lái)說(shuō)，層的數(shù)量越多，訪問(wèn)其他節(jié)點(diǎn)的速度就越快。

　　　　(2) 前進(jìn)指針：每個(gè)層都有一個(gè)指向表尾方向的前進(jìn)指針(level[i].forward屬性)，用于從表頭向表尾方向訪問(wèn)節(jié)點(diǎn)。

　　　　如上圖所示: 遍歷是程序首先訪問(wèn)跳躍表的第一個(gè)節(jié)點(diǎn)(表頭)，然后從第四層(L4)的前進(jìn)指針移動(dòng)到表中的第二個(gè)節(jié)點(diǎn)。在第二個(gè)節(jié)點(diǎn)時(shí)，程序沿著第二層(L2)的前進(jìn)指針移動(dòng)到表中的第三個(gè)節(jié)點(diǎn)。在第三個(gè)節(jié)點(diǎn)時(shí)，程序同樣沿著第二層(L2)的前進(jìn)指針移動(dòng)到表中的第四個(gè)節(jié)點(diǎn)。當(dāng)程序再次沿著第四個(gè)節(jié)點(diǎn)前進(jìn)指針移動(dòng)時(shí)，遇到null,程序知道這時(shí)已經(jīng)到達(dá)了跳躍表的表尾，于是結(jié)束這次遍歷。

　　　　(3) 跨度：層的跨度(level[i].span屬性)用于記錄兩個(gè)節(jié)點(diǎn)之間的距離：兩個(gè)節(jié)點(diǎn)之間的跨度越大，它們相距就越遠(yuǎn)。 指向null的所有前進(jìn)指針跨度都為0,因?yàn)樗鼈儧](méi)有連向任何節(jié)點(diǎn)。對(duì)于遍歷操作只使用前進(jìn)指針就可以完成了，跨度實(shí)際上是用來(lái)計(jì)算排位的。

　　　　(4) 后退指針：節(jié)點(diǎn)的后退指針(backward屬性) 用于從表尾向表頭方向訪問(wèn)節(jié)點(diǎn)。與前進(jìn)指針不同，前進(jìn)指針一次可以跳過(guò)多個(gè)節(jié)點(diǎn)，而每個(gè)節(jié)點(diǎn)只有一個(gè)后退指針，所以每次只能后退至前一個(gè)節(jié)點(diǎn)。

　　　　(5) 分值和成員：節(jié)點(diǎn)的分值(score屬性)是一個(gè)double類(lèi)型的浮點(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ì)排在前面(靠近表頭的方向)。Java架構(gòu)交流學(xué)習(xí)圈：874811168 面向具有Java開(kāi)發(fā)經(jīng)驗(yàn)人群 幫助突破瓶頸 提升思維能力。

例2:? 分值相同的，按成員對(duì)象來(lái)排序。

? ? 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 跳躍表

　　　　僅靠多個(gè)跳躍表節(jié)點(diǎn)就可以組成一個(gè)跳躍表,但通過(guò)使用一個(gè)zskplist結(jié)構(gòu)來(lái)持有這些節(jié)點(diǎn)，程序可以更方便地對(duì)整個(gè)跳躍表進(jìn)行處理。

typedef struct zskiplist

? ? ? ? {

? ? ? ? ? ? //表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)

? ? ? ? ? ? struct skiplistNode *header, *tail;

? ? ? ? ? ? //表中節(jié)點(diǎn)數(shù)量

? ? ? ? ? ? unsigned long length;

? ? ? ? ? ? //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)

? ? ? ? ? ? ? int level;

? ? ? ? }zskiplist