Redis skip list結構分析

　　如何實現一個海量用戶的實時排名系統？或許可以用 mysql 搞一個糾結的方案；但要是選擇了 redis，那絕對是既簡單又優雅。Redis 的 zset 本身就是一種支持排序的集合，而 zset 的實現，則使用了 skip list 數據結構。Skip list 是一種多層次的有序鏈表，通過隨機地選擇層數來實現插入、查找和刪除都是O(logn)的時間復雜度（和平衡樹同樣的效率，但實現比平衡樹簡單很多）。關 于 skip list 的具體介紹可以參見 William Pugh 的論文：Skip Lists: A Probabilistic Alternative to Balanced Trees 。下面我們來分析一下 redis 中 skip list 的實現。

　　Redis 中 skip list 主要有 zskiplist 和 zskiplistNode 兩個數據結構：

    　　typedef struct zskiplistNode {

    　　    robj *obj;

    　　    double score;

    　　    struct zskiplistNode *backward;

    　　    struct zskiplistLevel {

    　　        struct zskiplistNode *forward;

    　　        unsigned int span;

    　　    } level[];

    　　} zskiplistNode;

    　　 

    　　typedef struct zskiplist {

    　　    struct zskiplistNode *header, *tail;

    　　    unsigned long length;

    　　    int level;

    　　} zskiplist;

　　其中 zskiplistNode 中包含一個 zskiplistLevel 數組，數組的大小根據節點所在的層數(level)決定。backward 指針是為了方便向后遍歷而對 skip list 做的改進。

　　主要的 API 有：

　　zslCreate            創建一個 zskiplist，并添加一個具有最高層數 ZSKIPLIST_MAXLEVEL（代碼中定義為32）的節點來管理分層的鏈表。

　　zslInsert              插入一個節點到 zskiplist，并調整每一個層級的鏈表都是有序的。

　　zslDelete            從 zskiplist 刪除一個節點，并調整剩余節點在每個層級都是有序的。

　　zslRandomLevel 為新加入的節點隨機產生一個不超過 ZSKIPLIST_MAXLEVEL 的層數。

　　zslInsert 和 zslDelete 函數都需要首先查找到合適的位置或節點，查找的代碼很簡單，直接包含在了這兩個函數內：

　　x = zsl->header;

    　　for (i = zsl->level-1; i >= 0; i–) {

    　　/* store rank that is crossed to reach the insert position */

    　　    rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

    　　    while (x->level[i].forward &&

    　　          (x->level[i].forward->score < score

    　　             (x->level[i].forward->score == score &&

    　　          compareStringObjects (x->level[i].forward->obj,obj) < 0))) {

    　　       rank[i] += x->level[i].span;

    　　       x = x->level[i].forward;

    　　   }

    　　   update[i] = x;

    　　}

　　查找是從 zskiplist 現有的最高層開始向前，并在查找的過程中根據規則轉向低層的鏈表繼續，一直到 skip list 的最低層為止。同時看到 redis 的實現中允許相同的 score 存在（這時按對象的字符串進行比較），但不允許具有相同值的對象并存（集合的特性）。

　　下面通過一個例子來說明 skip list 的建立過程。

　　按順序執行下列語句：

    　　zslInsert (zsl, 5, obj1);              //level=1;

    　　zslInsert (zsl, 3, obj2);              //level=2;

    　　zslInsert (zsl, 4, obj3);              //level=1;

    　　zslInsert (zsl, 1, obj4);              //level=3;

    　　zslInsert (zsl, 2, obj5);              //level=1;

　　現在的 zsl 結構如下圖所示，其中 level array 的數組下標是為了圖例更直觀，實際不占存儲空間。為了保證圖例的簡潔，backward 的指針沒有畫出，對應 level 0 紅色指針相反方向的指針。

　　祝大家玩兒的開心！
      來自: rdc.taobao.com