skiplist 是一種有序數(shù)據(jù)結(jié)構(gòu)吉执。它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針， 從而達到快速訪問節(jié)點的目的地来。 跳躍表支持平均O(log N) 最壞 O(N)
復(fù)雜度的節(jié)點查找戳玫。

1、跳表介紹

為了使得鏈表支持類似二分查找的算法未斑，對原始的鏈表進行修改咕宿，修改后的鏈表就是跳躍表，簡稱跳表。跳表支持快速的插入府阀、刪除缆镣、查找操作，是一種動態(tài)的數(shù)據(jù)結(jié)構(gòu)试浙。

1-1

如果我們想查找圖1-1 的鏈表里面的某個元素董瞻，那必須從頭遍歷到尾才能找到，時間復(fù)雜度為O(n)

1-2

我們可以給原始鏈表加一級索引田巴，如上圖1-2钠糊，從圖中可以看出如果我們此時查找是6這個元素的，從紅線表示看我們只需要查找5次壹哺，原始鏈表查詢需要6次

1-3

我們可以給原始鏈表再增加一級索引抄伍，來減少我們的查找時間復(fù)雜度。

由于這個數(shù)據(jù)量不大管宵，查找效率提升的不明顯截珍，對于數(shù)據(jù)量較大的時候，查找效率提高很快箩朴，拿空間換時間岗喉。
JAVA中也有跳表的實現(xiàn)-ConcurrentSkipListMap。

2炸庞、redis skiplist 結(jié)構(gòu)

在redis中 對外暴露的數(shù)據(jù)結(jié)構(gòu)：sorted set沈堡，然后sorted set 底端不僅僅使用skiplist，還是使用ziplist和dict （關(guān)于ziplist 后面章節(jié)會介紹）燕雁，那么具體什么情況下面才會使用skiplist

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
  zset-max-ziplist-entries 128
  zset-max-ziplist-value 64

通過redis.conf 上面這倆個配置來具體確定 ziplist 到skiplist的轉(zhuǎn)換

• zset-max-ziplist-entries ：當sorted set中的元素個數(shù)诞丽，即(數(shù)據(jù), score)對的數(shù)目超過128的時。
• zset-max-ziplist-value ：當sorted set中插入的任意一個數(shù)據(jù)的長度超過了64的時拐格。

1-1

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    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;
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

上面代碼出自redis-4.0 的 server.h 僧免，對上面結(jié)構(gòu)做些簡單分析

• ZSKIPLIST_MAXLEVEL：創(chuàng)建zskiplist會創(chuàng)建一個空的zskiplistNode （zskiplist.header的指向） 該node.level[] 的長度即該參數(shù)，還有就是每次創(chuàng)建新node的時會隨機數(shù)字捏浊，該隨機數(shù)范圍最大值就是該參數(shù)懂衩。生成的隨機數(shù)為node.level[]的長度
• ZSKIPLIST_P:生成隨機數(shù)概率期望

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

• zskiplistNode定義了skiplist節(jié)點結(jié)構(gòu)。
  ele : 存儲數(shù)據(jù) 為sds 類型（關(guān)于sds 可參考前面章節(jié)）
  score ：數(shù)據(jù)對應(yīng)的分數(shù)
  *backward：指向位于當前節(jié)點的前一個節(jié)點（雙向鏈表提升遍歷時間復(fù)雜度）
  level ：節(jié)點中用 L1 金踪、 L2 浊洞、 L3 等字樣標記節(jié)點的各個層（參考圖1-1）存放指向各層鏈表后一個節(jié)點的指針 。forward表示每層的一個向后指針胡岔。span 表示記錄兩個節(jié)點之間的距離法希，可以用于計算元素排名(rank)。
  如圖1-1 我們需要找到o3這個元素 對應(yīng)的score為2.0靶瘸，從header開始找到level最大一個元素 即o3苫亦，o3.span 為3 毛肋，在根據(jù)o3 的backward 找到o2，o3到o2的span為1屋剑，那么計算排名則為（3-1）-1 =1 润匙，rank是從0開始計算，所以從圖中可以看出o2的rank唉匾。這也是redis對skiplist做的一層擴展孕讳，并且level[] 是一個柔性數(shù)組。
• zskiplist 定義了skiplist真正結(jié)構(gòu)
  header和tail 分別指向skiplist 的頭尾節(jié)點巍膘。
  length ：記錄所有的節(jié)點數(shù)卫病，其中不包含新創(chuàng)建zskiplist時 創(chuàng)建的空node芜壁。
  level ：記錄所有節(jié)點 zskiplistNode.level[] 長度最大的數(shù)字粤蝎，其中也不計算新創(chuàng)建zskiplist時 創(chuàng)建的空node（這個node的level[] 長度為32）

3外邓、redis skiplist 創(chuàng)建過程以及skiplist的轉(zhuǎn)換

創(chuàng)建過程

為什么把創(chuàng)建過程單獨拿出來作為一項，因為筆者在剛剛開始的時候?qū)μ硗耆涣私獯澹戳撕芏噘Y料也還是一知半解。特別當筆者第一次看到圖1-1（別人畫的借用下）完全不理解header指向為什么是一個null的node 而且還是長度為32的level[]幽告，所以這里面做下特殊的源碼講解梅鹦。

/* Create a skiplist node with the specified number of levels.
 * The SDS string 'ele' is referenced by the node after the call. */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

上述代碼出自redis-4.0 的 t_zset.c ，簡單做下分析

• zslCreate 創(chuàng)建skiplist 并且創(chuàng)建header 的node冗锁，可以看出來傳過去的參數(shù)為ZSKIPLIST_MAXLEVEL齐唆，直接創(chuàng)建一個長度為32的level[]，看到這里就很清楚上圖1-1 上面所畫的冻河。
• zslCreateNode 創(chuàng)建具體node節(jié)點箍邮。

下面分析插入節(jié)點操作：

/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
    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 &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

代碼很長，總體思路大概分為3步：

• 根據(jù)目前傳入的score找到插入位置x叨叙，這個過程會保存各層x的前一個位置節(jié)點锭弊。
• 根據(jù)隨機函數(shù)獲取level，并且生成新節(jié)點擂错。
• 修改各個指針的指向味滞，將創(chuàng)建的新節(jié)點插入。

skiplist的轉(zhuǎn)換

前面介紹sorted set并不是一開始就用skiplist 而是后面才開始轉(zhuǎn)換成的钮呀。通過上面介紹的zset-max-ziplist-entries 和zset-max-ziplist-value來控制的剑鞍。

• 當數(shù)據(jù)量不滿足zset-max-ziplist-entries 和zset-max-ziplist-value時，sorted set是由一個ziplist來實現(xiàn)的爽醋。
• 當滿足zset-max-ziplist-entries 和zset-max-ziplist-value其中之一蚁署，sorted set會通zset 的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)轉(zhuǎn)換skiplist

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

4、為什么redis用skiplist而不用平衡樹

關(guān)于這個話我們可以從查找蚂四、新增刪除的角度考慮

平衡樹:采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個樹形結(jié)構(gòu)的數(shù)據(jù)形用，用這個樹形結(jié)構(gòu)的數(shù)據(jù)減少無關(guān)數(shù)據(jù)的檢索就轧，大大的提升了數(shù)據(jù)檢索的速度。

• 查找：在平衡樹上田度，我們找到指定范圍的小值之后妒御，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點。然而用skiplist 進行范圍查找的時候镇饺，我們只需要找到小值在對第一層進行遍歷即可得到乎莉；查找單個key 時平衡樹和skiplist 時間復(fù)雜度基本差不多都為O(log n)
• 新增刪除：平衡樹新增和刪除可能會引起子樹的調(diào)整，而skiplist 只需要改變向前指針或者向后指針的改變奸笤，操作簡單快速惋啃。

從上面三點其實已經(jīng)說明很多選擇skiplist的優(yōu)勢，還有一點skiplist 實現(xiàn)起來比平衡樹簡單很多监右。

Redis作者：(原話地址）

There are a few reasons:

1. They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

5边灭、總結(jié)

• redis skiplist 在原始的跳表上面做了一些優(yōu)化。
• redis sorted set 在zset-max-ziplist-entries 和zset-max-ziplist-value都不滿足的情況時使用ziplist 來節(jié)省內(nèi)存開銷健盒，超過那倆個參數(shù)利用查詢绒瘦、新增時間復(fù)雜度比較低的skiplist來實現(xiàn)。