跳躍表
- 概述
- 跳躍表的實作
- 跳躍表節點-zskiplistNode
-
- 層(level)
- 前進指針(forward)
- 跨度(span)
- 後退指針(backward)
- 分值(score) 和 成員(obj)
- 跳躍表-zskiplist
- 跳躍表API
- 跳躍表的查詢
- 跳躍表的插入
- 跳躍表的删除
概述
跳躍表（skiplist） 是一種 有序資料結構，它通過 在每個節點中 維持多個 指向其他節點的指針，進而達到 快速通路節點 的 目的
跳躍表 支援 平均O(logN)、最壞O(N)複雜度的節點查找，還可以通過 順序性操作 來批量 處理節點
在大部分情況下，跳躍表的效率可以和平衡樹相媲美，并且因為跳躍表的實作比平衡樹要來得更為簡單，是以有不少程式都使用跳躍表來代替平衡樹
Redis 使用 跳躍表 作為 有序集合鍵(zset) 的 底層實作之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員（member）是比較長的字元串時，Redis就會使用跳躍表來作為有序集合鍵的底層實作
和連結清單、字典等資料結構被廣泛地應用在Redis内部不同，Redis隻在兩個地方用到了跳躍表，一個是 實作 有序集合鍵(zset)，另一個是 在叢集節點中 用作 内部資料結構，除此之外，跳躍表在Redis裡面沒有其他用途
跳躍表的實作
Redis的跳躍表由
redis.h/zskiplistNode
和
redis.h/zskiplist
兩個結構定義
zskiplistNode
結構 用于表示 跳躍表節點
zskiplist
結構 則用于 儲存 跳躍表節點 的 相關資訊，比如節點的數量，以及指向表頭節點和表尾節點的指針等等
上圖展示了一個跳躍表示例，位于圖檔最左邊的是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
跳躍表節點的實作由
redis.h/zskiplistNode
結構定義
typedef struct zskiplistNode {
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
// 後退指針
struct zskiplistNode *backward;
// 分值
double score;
// 成員對象
robj *obj;
} zskiplistNode;
層(level)
跳躍表節點 的 level數組 可以包含 多個元素，每個元素 都包含一個 指向 其他節點 的 指針
程式可以通過這些層 來加快 通路其他節點的速度，一般來說，層的數量越多，通路其他節點的速度就越快
每次建立一個新跳躍表節點的時候，程式都根據幂次定律（power law，越大的數出現的機率越小）随機生成一個介于1和32之間的值 作為 level數組的大小，這個大小就是層的“高度”
前進指針(forward)
每個層 都有一個 指向 表尾方向 的 前進指針（level[i].
forward
屬性），用于 從表頭 向 表尾方向 通路節點
以上圖為例，周遊跳躍表中所有節點的路徑如下：
- 疊代程式首先通路跳躍表的第一個節點（表頭），然後從第四層的前進指針移動到表中的第二個節點
- 在第二個節點時，程式沿着第二層的前進指針移動到表中的第三個節點
- 在第三個節點時，程式同樣沿着第二層的前進指針移動到表中的第四個節點
- 當程式再次沿着第四個節點的前進指針移動時，它碰到一個NULL，程式知道這時已經到達了跳躍表的表尾，于是結束這次周遊
跨度(span)
層的跨度（level[i].
span
屬性）用于記錄兩個節點之間的距離：
- 兩個節點之間的跨度越大，它們相距得就越遠
- 指向NULL的所有前進指針的跨度都為0，因為它們沒有連向任何節點
初看上去，很容易以為跨度和周遊操作有關，但實際上并不是這樣，周遊操作隻使用前進指針就可以完成了，跨度 實際上 是 用來計算排位（rank）的
在查找某個節點的過程中，将 沿途 通路過的所有層 的 跨度(span) 累加起來，得到的結果 就是 目标節點 在 跳躍表中的排位
後退指針(backward)
節點的後退指針（
backward
屬性） 用于 從表尾 向 表頭方向 通路 節點
跟可以一次跳過多個節點的前進指針不同，因為每個節點隻有一個後退指針，是以每次隻能後退至前一個節點
分值(score) 和 成員(obj)
節點的分值（
score
屬性）是一個double類型的浮點數，跳躍表中的所有節點都按分值從小到大來排序
節點的成員對象（obj屬性）是一個指針，它指向一個字元串對象，而字元串對象則儲存着一個SDS值
在同一個跳躍表中，各個節點儲存的成員對象必須是唯一的，但是 多個節點 儲存的分值 卻可以是相同的
分值相同的節點 将按照 成員對象 在 字典序中的大小 來進行排序，成員對象較小的節點會排在前面（靠近表頭的方向），而成員對象較大的節點則會排在後面（靠近表尾的方向）
跳躍表-zskiplist
僅靠 多個 跳躍表節點 就可以 組成一個跳躍表
但通過使用一個
zskiplist
結構來持有這些節點，程式可以更友善地對整個跳躍表進行處理，比如快速通路跳躍表的表頭節點和表尾節點，或者快速地擷取跳躍表節點的數量（也即是跳躍表的長度）等資訊
zskiplist結構的定義如下：
typedef struct zskiplist {
// 表頭節點和表尾節點
structz skiplistNode *header, *tail;
// 表中節點的數量
unsigned long length;
// 表中 層數最大的節點 的 層數
int level;
} zskiplist;
header和tail指針分别指向跳躍表的表頭和表尾節點，通過這兩個指針，程式定位表頭節點和表尾節點的複雜度為O(1)
通過使用length屬性來記錄節點的數量，程式可以在O(1)複雜度内傳回跳躍表的長度
level屬性則用于在O(1)複雜度内 擷取 跳躍表中 層高最大 的 那個節點 的 層數量，注意表頭節點的層高并不計算在内
跳躍表API
跳躍表的查詢
跳躍表的查詢 是從 頂層 往下找，那麼會先從第K層開始找，方式就是循環比較，如果K層節點的下一個節點為空 說明 到達末尾，會跳到第二層，繼續周遊，直到找到對應節點
跳躍表的插入
先确定 要插入的元素要 占據的層數 K（采用丢硬币的方式，這完全是随機的）
然後在 Level 1 … Level K 各個層的連結清單都插入元素
如果 K 超過 連結清單現有的層數，則要添加新的層
跳躍表的删除
跳躍表的删除和查找類似，都是一級一級找到相對應的節點，然後 将 要删除節點的 前一個節點的 forward 指向 下一個節點，完全和連結清單類似