Redis 數據結構 skiplist
簡(jiǎn)介
Redis 的跳躍表由 server.h/zskiplistNode 和 server.h/zskiplist兩個(gè)結構定義， 其中 zskiplistNode結構用于表示跳躍表節點(diǎn)， 而 zskiplist結構則用于保存跳躍表節點(diǎn)的相關(guān)信息， 比如節點(diǎn)的數量， 以及指向表頭節點(diǎn)和表尾節點(diǎn)的指針， 等等。
圖 5-1 展示了一個(gè)跳躍表示例， 位于圖片最左邊的是 zskiplist 結構， 該結構包含以下屬性：
header：指向跳躍表的表頭節點(diǎn)。tail：指向跳躍表的表尾節點(diǎn)。level：記錄目前跳躍表內，層數最大的那個(gè)節點(diǎn)的層數（表頭節點(diǎn)的層數不計算在內）。length：記錄跳躍表的長(cháng)度，也即是，跳躍表目前包含節點(diǎn)的數量（表頭節點(diǎn)不計算在內）。
位于 zskiplist 結構右方的是四個(gè) zskiplistNode 結構， 該結構包含以下屬性：
- 層（level）：節點(diǎn)中用 L1 、 L2 、 L3 等字樣標記節點(diǎn)的各個(gè)層， L1 代表第一層， L2 代表第二層，以此類(lèi)推。每個(gè)層都帶有兩個(gè)屬性：前進(jìn)指針和跨度。前進(jìn)指針用于訪(fǎng)問(wèn)位于表尾方向的其他節點(diǎn)，而跨度則記錄了前進(jìn)指針所指向節點(diǎn)和當前節點(diǎn)的距離。在上面的圖片中，連線(xiàn)上帶有數字的箭頭就代表前進(jìn)指針，而那個(gè)數字就是跨度。當程序從表頭向表尾進(jìn)行遍歷時(shí)，訪(fǎng)問(wèn)會(huì )沿著(zhù)層的前進(jìn)指針進(jìn)行。
- 后退（backward）指針：節點(diǎn)中用 BW 字樣標記節點(diǎn)的后退指針，它指向位于當前節點(diǎn)的前一個(gè)節點(diǎn)。后退指針在程序從表尾向表頭遍歷時(shí)使用。
- 分值（score）：各個(gè)節點(diǎn)中的 1.0 、 2.0 和 3.0 是節點(diǎn)所保存的分值。在跳躍表中，節點(diǎn)按各自所保存的分值從小到大排列。
- 成員對象（obj）：各個(gè)節點(diǎn)中的 o1 、 o2 和 o3 是節點(diǎn)所保存的成員對象。
注意表頭節點(diǎn)和其他節點(diǎn)的構造是一樣的： 表頭節點(diǎn)也有后退指針、分值和成員對象， 不過(guò)表頭節點(diǎn)的這些屬性都不會(huì )被用到， 所以圖中省略了這些部分， 只顯示了表頭節點(diǎn)的各個(gè)層。
跳躍表節點(diǎn)
跳躍表節點(diǎn)的實(shí)現由 server.h/zskiplistNode 結構定義：
typedef struct zskiplistNode {
// 成員對象,使用redis內部封裝的字符串類(lèi)型
sds ele;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 跨度
unsigned long span;
} level[];
} zskiplistNode;
層
跳躍表節點(diǎn)的 level 數組可以包含多個(gè)元素， 每個(gè)元素都包含一個(gè)指向其他節點(diǎn)的指針， 程序可以通過(guò)這些層來(lái)加快訪(fǎng)問(wèn)其他節點(diǎn)的速度， 一般來(lái)說(shuō)， 層的數量越多， 訪(fǎng)問(wèn)其他節點(diǎn)的速度就越快。
每次創(chuàng )建一個(gè)新跳躍表節點(diǎn)的時(shí)候， 程序都根據冪次定律 （power law，越大的數出現的概率越?。?隨機生成一個(gè)介于 1 和 32 之間的值作為 level 數組的大小， 這個(gè)大小就是層的“高度”。
圖 5-2 分別展示了三個(gè)高度為 1 層、 3 層和 5 層的節點(diǎn)， 因為 C 語(yǔ)言的數組索引總是從 0 開(kāi)始的， 所以節點(diǎn)的第一層是 level[0] ， 而第二層是 level[1] ， 以此類(lèi)推。
前進(jìn)指針
每個(gè)層都有一個(gè)指向表尾方向的前進(jìn)指針（level[i].forward 屬性）， 用于從表頭向表尾方向訪(fǎng)問(wèn)節點(diǎn)。
圖 5-3 用虛線(xiàn)表示出了程序從表頭向表尾方向， 遍歷跳躍表中所有節點(diǎn)的路徑：
- 迭代程序首先訪(fǎng)問(wèn)跳躍表的第一個(gè)節點(diǎn)（表頭）， 然后從第四層的前進(jìn)指針移動(dòng)到表中的第二個(gè)節點(diǎn)。
- 在第二個(gè)節點(diǎn)時(shí)， 程序沿著(zhù)第二層的前進(jìn)指針移動(dòng)到表中的第三個(gè)節點(diǎn)。
- 在第三個(gè)節點(diǎn)時(shí)， 程序同樣沿著(zhù)第二層的前進(jìn)指針移動(dòng)到表中的第四個(gè)節點(diǎn)。
- 當程序再次沿著(zhù)第四個(gè)節點(diǎn)的前進(jìn)指針移動(dòng)時(shí)， 它碰到一個(gè) NULL ， 程序知道這時(shí)已經(jīng)到達了跳躍表的表尾， 于是結束這次遍歷。
跨度
層的跨度（level[i].span 屬性）用于記錄兩個(gè)節點(diǎn)之間的距離：
- 兩個(gè)節點(diǎn)之間的跨度越大， 它們相距得就越遠。
- 指向 NULL 的所有前進(jìn)指針的跨度都為 0 ， 因為它們沒(méi)有連向任何節點(diǎn)。
初看上去， 很容易以為跨度和遍歷操作有關(guān)， 但實(shí)際上并不是這樣 —— 遍歷操作只使用前進(jìn)指針就可以完成了， 跨度實(shí)際上是用來(lái)計算排位（rank）的： 在查找某個(gè)節點(diǎn)的過(guò)程中， 將沿途訪(fǎng)問(wèn)過(guò)的所有層的跨度累計起來(lái)， 得到的結果就是目標節點(diǎn)在跳躍表中的排位。
舉個(gè)例子， 圖 5-4 用虛線(xiàn)標記了在跳躍表中查找分值為 3.0 、 成員對象為 o3 的節點(diǎn)時(shí)， 沿途經(jīng)歷的層： 查找的過(guò)程只經(jīng)過(guò)了一個(gè)層， 并且層的跨度為 3 ， 所以目標節點(diǎn)在跳躍表中的排位為 3 。
再舉個(gè)例子， 圖 5-5 用虛線(xiàn)標記了在跳躍表中查找分值為 2.0 、 成員對象為 o2 的節點(diǎn)時(shí)， 沿途經(jīng)歷的層： 在查找節點(diǎn)的過(guò)程中， 程序經(jīng)過(guò)了兩個(gè)跨度為 1 的節點(diǎn)， 因此可以計算出， 目標節點(diǎn)在跳躍表中的排位為 2 。
后退指針
節點(diǎn)的后退指針（backward 屬性）用于從表尾向表頭方向訪(fǎng)問(wèn)節點(diǎn)： 跟可以一次跳過(guò)多個(gè)節點(diǎn)的前進(jìn)指針不同， 因為每個(gè)節點(diǎn)只有一個(gè)后退指針， 所以每次只能后退至前一個(gè)節點(diǎn)。
圖 5-6 用虛線(xiàn)展示了如果從表尾向表頭遍歷跳躍表中的所有節點(diǎn)： 程序首先通過(guò)跳躍表的 tail 指針訪(fǎng)問(wèn)表尾節點(diǎn)， 然后通過(guò)后退指針訪(fǎng)問(wèn)倒數第二個(gè)節點(diǎn)， 之后再沿著(zhù)后退指針訪(fǎng)問(wèn)倒數第三個(gè)節點(diǎn)， 再之后遇到指向 NULL 的后退指針， 于是訪(fǎng)問(wèn)結束。
分值和成員
節點(diǎn)的分值（score 屬性）是一個(gè) double 類(lèi)型的浮點(diǎn)數， 跳躍表中的所有節點(diǎn)都按分值從小到大來(lái)排序。
節點(diǎn)的成員對象（obj 屬性）是一個(gè)指針， 它指向一個(gè)字符串對象， 而字符串對象則保存著(zhù)一個(gè) SDS 值。
在同一個(gè)跳躍表中， 各個(gè)節點(diǎn)保存的成員對象必須是唯一的， 但是多個(gè)節點(diǎn)保存的分值卻可以是相同的： 分值相同的節點(diǎn)將按照成員對象在字典序中的大小來(lái)進(jìn)行排序， 成員對象較小的節點(diǎn)會(huì )排在前面（靠近表頭的方向）， 而成員對象較大的節點(diǎn)則會(huì )排在后面（靠近表尾的方向）。
舉個(gè)例子， 在圖 5-7 所示的跳躍表中， 三個(gè)跳躍表節點(diǎn)都保存了相同的分值 10086.0 ， 但保存成員對象 o1 的節點(diǎn)卻排在保存成員對象 o2 和 o3 的節點(diǎn)之前， 而保存成員對象 o2 的節點(diǎn)又排在保存成員對象 o3 的節點(diǎn)之前， 由此可見(jiàn)， o1 、 o2 、 o3 三個(gè)成員對象在字典中的排序為 o1 <= o2 <= o3 。
跳躍表
雖然僅靠多個(gè)跳躍表節點(diǎn)就可以組成一個(gè)跳躍表， 如圖 5-8 所示。
但通過(guò)使用一個(gè) zskiplist 結構來(lái)持有這些節點(diǎn)， 程序可以更方便地對整個(gè)跳躍表進(jìn)行處理， 比如快速訪(fǎng)問(wèn)跳躍表的表頭節點(diǎn)和表尾節點(diǎn)， 又或者快速地獲取跳躍表節點(diǎn)的數量（也即是跳躍表的長(cháng)度）等信息， 如圖 5-9 所示。
zskiplist 結構的定義如下
typedef struct zskiplist {
// 表中節點(diǎn)的數量
struct zskiplistNode *header, *tail;
// 表中節點(diǎn)的數量
unsigned long length;
// 表中層數最大的節點(diǎn)的層數
int level;
} zskiplist;
header 和 tail 指針?lè )謩e指向跳躍表的表頭和表尾節點(diǎn)， 通過(guò)這兩個(gè)指針， 程序定位表頭節點(diǎn)和表尾節點(diǎn)的復雜度為 O(1) 。
通過(guò)使用 length 屬性來(lái)記錄節點(diǎn)的數量， 程序可以在 O(1) 復雜度內返回跳躍表的長(cháng)度。
level 屬性則用于在 O(1) 復雜度內獲取跳躍表中層高最大的那個(gè)節點(diǎn)的層數量， 注意表頭節點(diǎn)的層高并不計算在內。
評論
