本文摘抄自redis 源碼剖析
跳躍表是一種隨機化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 ——查找啦桌、刪除准颓、添加等操作都可以在對數(shù)期望時間下完成，并且比起平衡樹來說凉馆，跳躍表的實現(xiàn)要簡單直觀得多薪寓。
以下是個典型的跳躍表例子：
從圖中可以看到，跳躍表主要由以下部分構(gòu)成：
- 表頭（head）：負責維護跳躍表的節(jié)點指針澜共。
- 跳躍表節(jié)點：保存著元素值向叉，以及多個層。
- 層：保存著指向其他元素的指針嗦董。高層的指針越過的元素數(shù)量大于等于低層的指針母谎，為了提高查找的效率，程序總是從高層先開始訪問京革，然后隨著元素值范圍的縮小奇唤，慢慢降低層次幸斥。
- 表尾：全部由NULL組成，表示跳躍表的末尾咬扇。
跳躍表的實現(xiàn)
為了滿足自身的功能需要甲葬，Redis對跳躍表進行了如下修改：
- 允許重復的score
- 值：多個不同的member的score 值可以相同
進行對比操作時，不僅要檢查score值懈贺，還要檢查member：當score
值可以重復時经窖，單靠score值無法判斷一個元素的身份，所以需要連member域都一并檢查才行梭灿。
每個節(jié)點都帶有一個高度為1層的后退指針画侣，用于從表尾方向向表頭方向迭代：當執(zhí)行ZREVRANGE或ZREVRANGEBYSCORE這類以逆序處理有序集的命令時，就會用到這個屬性堡妒。
這個修改版的跳躍表由redis.h/zskiplist結(jié)構(gòu)定義：
typedef struct zskiplist {
// 頭節(jié)點配乱，尾節(jié)點
struct zskiplistNode *header, *tail;
// 節(jié)點數(shù)量
unsigned long length;
// 目前表內(nèi)節(jié)點的最大層數(shù) int level;
} zskiplist;
跳躍表的節(jié)點由redis.h/zskiplistNode定義：
typedef struct zskiplistNode {
//member 對象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 這個層跨越的節(jié)點數(shù)量
unsigned int span;
} level[];
} zskiplistNode;
跳躍表的應用
和字典、鏈表或者字符串這幾種在 Redis 中大量使用的數(shù)據(jù)結(jié)構(gòu)不同皮迟，跳躍表在 Redis 的唯一作用宪卿，就是實現(xiàn)有序集數(shù)據(jù)類型。
跳躍表將指向有序集的score值和member
域的指針作為元素万栅，并以score 值為索引佑钾，對有序集元素進行排序。
舉個例子烦粒，以下代碼創(chuàng)建了一個帶有 3 個元素的有序集：
redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"
在底層實現(xiàn)中休溶，Redis 為x、y和z三個member分別創(chuàng)建了三個字符串扰她，值分別為double類型的6兽掰、10和15，然后用跳躍表將這些指針有序地保存起來徒役，形成這樣一個跳躍表：
為了方便展示孽尽，在圖片中我們直接將member和score值包含在表節(jié)點中，但是在實際的定義中忧勿，因為跳躍表要和另一個實現(xiàn)有序集的結(jié)構(gòu)（字典）分享member和score值杉女，所以跳躍表只保存指向member
和score的指針。
