跳表

跳表 skiplist 是一種有序的數據結構, 通過在每個節(jié)點中維持多個指向其它節(jié)點的指針、達到快速訪問節(jié)點的目的

支持平均 O(logN), 最壞 O(N)復雜度的查找, 還支持順序性操作來批量處理節(jié)點, 大部分情況下、效率可以合平衡樹相媲美, 且實現簡單, 很多程序都可以使用skipList替代平衡樹, Redis使用跳躍表作為有序集合鍵的底層實現之一.

跳表只在兩個地方使用: 實現有序集合鍵 & 在集群節(jié)點中用作內部結構

跳表的實現

Redis 的跳躍表由 redis.h/zskiplistNode 和 redis.h/zskiplist 兩個結構定義, zskiplistNode 結構用于表示跳躍表節(jié)點, zskiplist 則用于保存跳躍表節(jié)點的相關信息, eg.

節(jié)點梳理、及指向表頭節(jié)點 和 表尾節(jié)點的指針.

跳表示意圖.png

最左邊是跳表的zskiplist結構, 包含下邊這些屬性:

header: 指向跳表的表頭節(jié)點

tail: 指向跳表的表尾節(jié)點

level: 記錄當前跳表內、層次最大的那個節(jié)點的層數(表頭節(jié)點的層數不計算在內)

length: 記錄跳表的長度, 即: 目前跳表內包含的節(jié)點的數量(表頭節(jié)點不計)

右邊是4個zskiplistNode結構, 屬性如下:

level: 節(jié)點中用 L1, L2, L3 等標記節(jié)點的各個層, L1代表第一層, 依次類推. 每個層有兩個屬性: 前進指針 和 跨度. 前進指針用于訪問位于表尾方向的其它節(jié)點, 跨度記錄前進指針指向的節(jié)點和當前節(jié)點的距離. 程序從表頭向表尾遍歷時, 訪問會沿著層的前進指針進行.

backward: 后退指針, 節(jié)點中BW標記的指針, 指向當前節(jié)點的前一個指針, 后退指針在程序從表尾向表頭遍歷時使用

score: 分值, 節(jié)點中的1.0, 2.0, 3.0是各節(jié)點保存的分值, 在跳表中節(jié)點按各自保存的分值從小到大排列.

obj: 成員對象, 各個節(jié)點中的o1, o2 和 o3 是節(jié)點保存的成員對象.

注意: 表頭節(jié)點和其它節(jié)點的構造是一致的, 也有后退指針, 分值 和 成員對象, 但不會被使用.

跳躍表節(jié)點

由redis.h/zskiplistNode結構定義

typedef struct zskiplistNode {
  // 層
  struct zskiplistLevel {
    struct zskiplistNode *forward; // 前進指針
    unsigned int span; // 跨度
  }level[];
  struct zskiplistNode *backward; // 后退指針
  double score; // 分值
  robj *obj; // 成員對象
} zskiplistNode;

層 跳躍表節(jié)點的level數組可以包含多個元素, 每個元素都包含一個指向其它節(jié)點的指針, 程序可以通過這些層來加速訪問其它節(jié)點的速度, 一般來說、層的數量越多, 訪問其它節(jié)點的速度就越快. 每次創(chuàng)建一個新的跳表時、程序根據冪次定律隨機生成一個介于1和32之間的值作為level數組的大小, 即 層高

前進指針 每一個層都有一個指向表尾方向的前進指針(level[i].forward), 用于從表頭向表尾方向訪問節(jié)點.

跨度 (level[i].span)用于記錄兩個節(jié)點之間的距離, 兩個節(jié)點之間的跨度越大,相距就越遠. 指向null的所有前進指針的跨度都為0, 因為他們沒有連向任何節(jié)點

后退指針 (backward)用于從表尾向表頭方向訪問節(jié)點, 跟一次可以跳多個節(jié)點的前進指針不同, 每個節(jié)點只有一個后退指針、只能后退至前一個節(jié)點.

分值和成員 (score)是一個double類型的浮點數, 跳躍表中所有的節(jié)點都按分值從小到大來排序(obj)是一個指針、指向一個字符串對象、字符串對象中則保存著一個SDS值

在同一個跳表中、各節(jié)點保存的成員對象必須是唯一的、但多個節(jié)點保存的分值卻是可以相同的. 分值相同的節(jié)點按照成員對象在字典序中的大小排序, 小的節(jié)點放在前邊.

跳躍表

僅靠多個跳躍表節(jié)點就可以完成一個跳表、但使用一個zskiplist結構來持有這些節(jié)點, 程序可以更方便的對整個跳表進行處理, eg. 快速訪問跳表的頭結點和尾結點、快速獲取節(jié)點數量.

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; // 表頭節(jié)點和表尾節(jié)點
  unsigned long length; // 表中節(jié)點的數量
  int level; // 表中層數最大的節(jié)點的層數
} zskiplist;

header 和 tail 指針分別指向表頭和表尾節(jié)點, 程序定位表頭節(jié)點和表尾節(jié)點的復雜度是 O(1)

通過length屬性記錄節(jié)點的數量、程序可以在 O(1) 復雜度內返回跳表長度

level 屬性則用于在 O(1)復雜度內獲取跳表中層高最大的節(jié)點的層數量(表頭節(jié)點的層高不計)

重點回顧

1. 跳表是有序集合的底層實現之一
2. Redis的跳表實現由 zskiplist 和 zskiplistNode 兩個結構組成, 其中 zskiplist 用于保存跳表信息(eg. 表頭節(jié)點、表尾節(jié)點、長度)、而zskiplistNode 則用于表示跳躍表節(jié)點
3. 每個跳躍表節(jié)點的層高都是 1~32 之間的隨機數
4. 同一個跳表中、多個節(jié)點可以包含相同的分值、但每個節(jié)點的成員對象必須是唯一的
5. 跳表中的節(jié)點按照分值大小排序、分值相同時、節(jié)點按照成員對象的大小排序