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