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`?屬性則用于在??復雜度內獲取跳躍表中層高最大的那個節點的層數量， 注意表頭節點的層高并不計算在內。