轉(zhuǎn)自：http://www.redisbook.com
跳躍表¶
跳躍表（skiplist）是一種隨機(jī)化的數(shù)據(jù)， 由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》中提出， 這種數(shù)據(jù)結(jié)構(gòu)以有序的方式在層次化的鏈表中保存元素， 它的效率可以和平衡樹媲美 —— 查找、刪除、添加等操作都可以在對(duì)數(shù)期望時(shí)間下完成， 并且比起平衡樹來(lái)說(shuō)， 跳躍表的實(shí)現(xiàn)要簡(jiǎn)單直觀得多。
以下是一個(gè)典型的跳躍表例子（圖片來(lái)自維基百科）：
從圖中可以看到， 跳躍表主要由以下部分構(gòu)成：
- 表頭（head）：負(fù)責(zé)維護(hù)跳躍表的節(jié)點(diǎn)指針。
- 跳躍表節(jié)點(diǎn)：保存著元素值，以及多個(gè)層。
- 層：保存著指向其他元素的指針。高層的指針越過(guò)的元素?cái)?shù)量大于等于低層的指針，為了提高查找的效率，程序總是從高層先開始訪問(wèn)，然后隨著元素值范圍的縮小，慢慢降低層次。
- 表尾：全部由 NULL 組成，表示跳躍表的末尾。
因?yàn)樘S表的定義可以在任何一本算法或數(shù)據(jù)結(jié)構(gòu)的書中找到， 所以本章不介紹跳躍表的具體實(shí)現(xiàn)方式或者具體的算法， 而只介紹跳躍表在 Redis 的應(yīng)用、核心數(shù)據(jù)結(jié)構(gòu)和 API 。
跳躍表的實(shí)現(xiàn)
為了適應(yīng)自身的功能需要， Redis 基于 William Pugh 論文中描述的跳躍表進(jìn)行了以下修改：
- 允許重復(fù)的 score 值：多個(gè)不同的 member 的 score 值可以相同。
- 進(jìn)行對(duì)比操作時(shí)，不僅要檢查 score 值，還要檢查 member ：當(dāng) score 值可以重復(fù)時(shí)，單靠 score 值無(wú)法判斷一個(gè)元素的身份，所遇需要連 member 域都一并檢查才行。
- 每個(gè)節(jié)點(diǎn)都帶有一個(gè)高度為 1 層的后退指針，用于從表尾方向向表頭方向迭代：當(dāng)執(zhí)行 ZREVRANGE 或 ZREVRANGEBYSCORE 這類以逆序處理有序集的命令時(shí)，就會(huì)用到這個(gè)屬性。
這個(gè)修改版的跳躍表由 redis.h/zskiplist 結(jié)構(gòu)定義：
typedef struct zskiplist {
// 頭節(jié)點(diǎn)，尾節(jié)點(diǎn)
struct zskiplistNode *header, *tail;
// 節(jié)點(diǎn)數(shù)量
unsigned long length;
// 目前表內(nèi)節(jié)點(diǎn)的最大層數(shù)
int level;
} zskiplist;
跳躍表的節(jié)點(diǎn)由
redis.h/zskiplistNode 定義：
typedef struct zskiplistNode {
// member 對(duì)象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 這個(gè)層跨越的節(jié)點(diǎn)數(shù)量
unsigned int span;
} level[];
} zskiplistNode;
以下是操作這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的 API ，它們的作用以及相應(yīng)的算法復(fù)雜度：
| 函數(shù) | 作用 | 復(fù)雜度 |
|---|
| zslCreateNode | 創(chuàng)建并返回一個(gè)新的跳躍表節(jié)點(diǎn) | 最壞 O(1) |
| zslFreeNode | 釋放給定的跳躍表節(jié)點(diǎn) | 最壞 O(1) |
| zslCreate | 創(chuàng)建并初始化一個(gè)新的跳躍表 | 最壞 O(N) |
| zslFree | 釋放給定的跳躍表 | 最壞 O(N) |
| zslInsert | 將一個(gè)包含給定 score 和 member 的新節(jié)點(diǎn)添加到跳躍表中 | 最壞 O(N) 平均 O(logN) |
| zslDeleteNode | 刪除給定的跳躍表節(jié)點(diǎn) | 最壞 O(N) |
| zslDelete | 刪除匹配給定 member 和 score 的元素 | 最壞 O(N) 平均 O(logN) |
| zslFirstInRange | 找到跳躍表中第一個(gè)符合給定范圍的元素 | 最壞 O(N) 平均 O(logN) |
| zslLastInRange | 找到跳躍表中最后一個(gè)符合給定范圍的元素 | 最壞 O(N) 平均 O(logN) |
| zslDeleteRangeByScore | 刪除 score 值在給定范圍內(nèi)的所有節(jié)點(diǎn) | 最壞 O(N2) |
| zslDeleteRangeByRank | 刪除給定排序范圍內(nèi)的所有節(jié)點(diǎn) | 最壞 O(N2) |
| zslGetRank | 返回目標(biāo)元素在有序集中的排位 | 最壞 O(N) 平均 O(logN) |
| zslGetElementByRank | 根據(jù)給定排位，返回該排位上的元素節(jié)點(diǎn) | 最壞 O(N) 平均 O(logN) |
跳躍表的應(yīng)用
和字典、鏈表或者字符串這幾種在 Redis 中大量使用的數(shù)據(jù)結(jié)構(gòu)不同， 跳躍表在 Redis 的唯一作用， 就是實(shí)現(xiàn)有序集數(shù)據(jù)類型。
跳躍表將指向有序集的 score 值和 member 域的指針作為元素， 并以 score 值為索引， 對(duì)有序集元素進(jìn)行排序。
舉個(gè)例子， 以下代碼就創(chuàng)建了一個(gè)帶有 3 個(gè)元素的有序集：
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"
在底層實(shí)現(xiàn)中， Redis 為
x 、
y 和
z 三個(gè)
member 分別創(chuàng)建了三個(gè)字符串， 并為
6 、
10 和
15 分別創(chuàng)建三個(gè)
double 類型的值， 然后用一個(gè)跳躍表將這些指針有序地保存起來(lái)， 形成這樣一個(gè)跳躍表：
為了展示的方便， 在圖片中我們直接將 member 和 score 值包含在表節(jié)點(diǎn)中， 但是在實(shí)際的定義中， 因?yàn)樘S表要和另一個(gè)實(shí)現(xiàn)有序集的結(jié)構(gòu)（字典）分享 member 和 score 值， 所以跳躍表只保存指向 member 和 score 的指針。 更詳細(xì)的信息，請(qǐng)參考《有序集》章節(jié)。
小結(jié)
- 跳躍表是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，它的查找、添加、刪除操作都可以在對(duì)數(shù)期望時(shí)間下完成。
- 跳躍表目前在 Redis 的唯一作用就是作為有序集類型的底層數(shù)據(jù)結(jié)構(gòu)（之一，另一個(gè)構(gòu)成有序集的結(jié)構(gòu)是字典）。
- 為了適應(yīng)自身的需求，Redis 基于 William Pugh 論文中描述的跳躍表進(jìn)行了修改，包括：
- score 值可重復(fù)。
- 對(duì)比一個(gè)元素需要同時(shí)檢查它的 score 和 memeber 。
- 每個(gè)節(jié)點(diǎn)帶有高度為 1 層的后退指針，用于從表尾方向向表頭方向迭代。