Redis 的跳躍表由?`redis.h/zskiplistNode`?和?`redis.h/zskiplist`?兩個結構定義, 其中?`zskiplistNode`?結構用于表示跳躍表節點, 而?`zskiplist`結構則用于保存跳躍表節點的相關信息, 比如節點的數量, 以及指向表頭節點和表尾節點的指針, 等等。

圖 5-1 展示了一個跳躍表示例, 位于圖片最左邊的是?`zskiplist`?結構, 該結構包含以下屬性:
* `header`?:指向跳躍表的表頭節點。
* `tail`?:指向跳躍表的表尾節點。
* `level`?:記錄目前跳躍表內,層數最大的那個節點的層數(表頭節點的層數不計算在內)。
* `length`?:記錄跳躍表的長度,也即是,跳躍表目前包含節點的數量(表頭節點不計算在內)。
位于?`zskiplist`?結構右方的是四個?`zskiplistNode`?結構, 該結構包含以下屬性:
* 層(level):節點中用?`L1`?、?`L2`?、?`L3`?等字樣標記節點的各個層,?`L1`?代表第一層,?`L2`?代表第二層,以此類推。每個層都帶有兩個屬性:前進指針和跨度。前進指針用于訪問位于表尾方向的其他節點,而跨度則記錄了前進指針所指向節點和當前節點的距離。在上面的圖片中,連線上帶有數字的箭頭就代表前進指針,而那個數字就是跨度。當程序從表頭向表尾進行遍歷時,訪問會沿著層的前進指針進行。
* 后退(backward)指針:節點中用?`BW`?字樣標記節點的后退指針,它指向位于當前節點的前一個節點。后退指針在程序從表尾向表頭遍歷時使用。
* 分值(score):各個節點中的?`1.0`?、?`2.0`?和?`3.0`?是節點所保存的分值。在跳躍表中,節點按各自所保存的分值從小到大排列。
* 成員對象(obj):各個節點中的?`o1`?、?`o2`?和?`o3`?是節點所保存的成員對象。
注意表頭節點和其他節點的構造是一樣的: 表頭節點也有后退指針、分值和成員對象, 不過表頭節點的這些屬性都不會被用到, 所以圖中省略了這些部分, 只顯示了表頭節點的各個層。
本節接下來的內容將對?`zskiplistNode`?和?`zskiplist`?兩個結構進行更詳細的介紹。
## 跳躍表節點
跳躍表節點的實現由?`redis.h/zskiplistNode`?結構定義:
~~~
typedef struct zskiplistNode {
// 后退指針
struct zskiplistNode *backward;
// 分值
double score;
// 成員對象
robj *obj;
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
~~~
### 層
跳躍表節點的?`level`?數組可以包含多個元素, 每個元素都包含一個指向其他節點的指針, 程序可以通過這些層來加快訪問其他節點的速度, 一般來說, 層的數量越多, 訪問其他節點的速度就越快。
每次創建一個新跳躍表節點的時候, 程序都根據冪次定律 ([power law](http://en.wikipedia.org/wiki/Power_law),越大的數出現的概率越小) 隨機生成一個介于?`1`?和?`32`?之間的值作為?`level`?數組的大小, 這個大小就是層的“高度”。
圖 5-2 分別展示了三個高度為?`1`?層、?`3`?層和?`5`?層的節點, 因為 C 語言的數組索引總是從?`0`?開始的, 所以節點的第一層是?`level[0]`?, 而第二層是?`level[1]`?, 以此類推。

### 前進指針
每個層都有一個指向表尾方向的前進指針(`level[i].forward`?屬性), 用于從表頭向表尾方向訪問節點。
圖 5-3 用虛線表示出了程序從表頭向表尾方向, 遍歷跳躍表中所有節點的路徑:
1. 迭代程序首先訪問跳躍表的第一個節點(表頭), 然后從第四層的前進指針移動到表中的第二個節點。
2. 在第二個節點時, 程序沿著第二層的前進指針移動到表中的第三個節點。
3. 在第三個節點時, 程序同樣沿著第二層的前進指針移動到表中的第四個節點。
4. 當程序再次沿著第四個節點的前進指針移動時, 它碰到一個?`NULL`?, 程序知道這時已經到達了跳躍表的表尾, 于是結束這次遍歷。

### 跨度
層的跨度(`level[i].span`?屬性)用于記錄兩個節點之間的距離:
* 兩個節點之間的跨度越大, 它們相距得就越遠。
* 指向?`NULL`?的所有前進指針的跨度都為?`0`?, 因為它們沒有連向任何節點。
初看上去, 很容易以為跨度和遍歷操作有關, 但實際上并不是這樣 —— 遍歷操作只使用前進指針就可以完成了, 跨度實際上是用來計算排位(rank)的: 在查找某個節點的過程中, 將沿途訪問過的所有層的跨度累計起來, 得到的結果就是目標節點在跳躍表中的排位。
舉個例子, 圖 5-4 用虛線標記了在跳躍表中查找分值為?`3.0`?、 成員對象為?`o3`?的節點時, 沿途經歷的層: 查找的過程只經過了一個層, 并且層的跨度為?`3`?, 所以目標節點在跳躍表中的排位為?`3`?。

再舉個例子, 圖 5-5 用虛線標記了在跳躍表中查找分值為?`2.0`?、 成員對象為?`o2`?的節點時, 沿途經歷的層: 在查找節點的過程中, 程序經過了兩個跨度為?`1`?的節點, 因此可以計算出, 目標節點在跳躍表中的排位為 2 。

### 后退指針
節點的后退指針(`backward`?屬性)用于從表尾向表頭方向訪問節點: 跟可以一次跳過多個節點的前進指針不同, 因為每個節點只有一個后退指針, 所以每次只能后退至前一個節點。
圖 5-6 用虛線展示了如果從表尾向表頭遍歷跳躍表中的所有節點: 程序首先通過跳躍表的?`tail`?指針訪問表尾節點, 然后通過后退指針訪問倒數第二個節點, 之后再沿著后退指針訪問倒數第三個節點, 再之后遇到指向?`NULL`?的后退指針, 于是訪問結束。

### 分值和成員
節點的分值(`score`?屬性)是一個?`double`?類型的浮點數, 跳躍表中的所有節點都按分值從小到大來排序。
節點的成員對象(`obj`?屬性)是一個指針, 它指向一個字符串對象, 而字符串對象則保存著一個 SDS 值。
在同一個跳躍表中, 各個節點保存的成員對象必須是唯一的, 但是多個節點保存的分值卻可以是相同的: 分值相同的節點將按照成員對象在字典序中的大小來進行排序, 成員對象較小的節點會排在前面(靠近表頭的方向), 而成員對象較大的節點則會排在后面(靠近表尾的方向)。
舉個例子, 在圖 5-7 所示的跳躍表中, 三個跳躍表節點都保存了相同的分值?`10086.0`?, 但保存成員對象?`o1`?的節點卻排在保存成員對象?`o2`和?`o3`?的節點之前, 而保存成員對象?`o2`?的節點又排在保存成員對象?`o3`?的節點之前, 由此可見,?`o1`?、?`o2`?、?`o3`?三個成員對象在字典中的排序為?`o1?<=?o2?<=?o3`?。

## 跳躍表
雖然僅靠多個跳躍表節點就可以組成一個跳躍表, 如圖 5-8 所示。

但通過使用一個?`zskiplist`?結構來持有這些節點, 程序可以更方便地對整個跳躍表進行處理, 比如快速訪問跳躍表的表頭節點和表尾節點, 又或者快速地獲取跳躍表節點的數量(也即是跳躍表的長度)等信息, 如圖 5-9 所示。

`zskiplist`?結構的定義如下:
~~~
typedef struct zskiplist {
// 表頭節點和表尾節點
struct zskiplistNode *header, *tail;
// 表中節點的數量
unsigned long length;
// 表中層數最大的節點的層數
int level;
} zskiplist;
~~~
`header`?和?`tail`?指針分別指向跳躍表的表頭和表尾節點, 通過這兩個指針, 程序定位表頭節點和表尾節點的復雜度為??。
通過使用?`length`?屬性來記錄節點的數量, 程序可以在??復雜度內返回跳躍表的長度。
`level`?屬性則用于在??復雜度內獲取跳躍表中層高最大的那個節點的層數量, 注意表頭節點的層高并不計算在內。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤