摘要：使用跳躍表而不是平衡樹的原因和各種平衡樹如紅黑樹等的元素是有序排列的，而哈希表不是有序的。如果想要了解有關跳躍表源碼更具體的分析，建議閱讀學習筆記源碼學習之跳躍表。

Grape
全部視頻：https://segmentfault.com/a/11...

大家想象一下下面這種場景：

面試官：我們有一個有序的數(shù)組2,5,6,7,9，我們要去查7，設計一個算法。
考生：第一眼看到相信大家都會看出來是二分查找，O(logN)就完事了。
面試官：那么接下來我們把這個數(shù)組換成鏈表呢(2->5->6->7->9)？
考生：這簡單，二叉樹，同樣logN。
面試官：那么請手寫一下完整代碼！
考生：卒

想象一下，給你一張草稿紙，一只筆，一個編輯器，你能立即實現(xiàn)一顆紅黑樹，或者AVL樹出來嗎？ 很難吧，這需要時間，要考慮很多細節(jié)，要參考一堆算法與數(shù)據(jù)結(jié)構(gòu)之類的樹，還要參考網(wǎng)上的代碼，相當麻煩。

回去之后，小明很難過，又不想被二叉樹所折磨，想要找一個方法來代替二叉樹，在他的不懈努力之下，終于，找出了替代紅黑樹的方法，它叫做skiplist。

怎么解決的呢？
首先，表是處于一個初始狀態(tài)的，沒有任何一個元素，類似于下圖：

那么，我們繼續(xù)插入一個元素2，那么它就變成了這樣。

然后我們拋硬幣，結(jié)果是正面，那么我們要將2插入到L2層，如下圖:?

繼續(xù)拋硬幣，結(jié)果是反面，那么元素2的插入操作就停止了，插入后的表結(jié)構(gòu)就是上圖所示。接下來，我們插入元素5，跟元素2的插入一樣，現(xiàn)在L1層插入5，如下圖：?

接下來繼續(xù)拋硬幣，是正面的話就上升一層，否則就終止，繼續(xù)插入其他新的元素。
那么最后，我們建造成的樣子就如下圖所示。

這樣子就構(gòu)造成了skiplist。當然因為規(guī)模小，結(jié)果很可能不是一個理想的跳躍表。但是如果元素個數(shù)n的規(guī)模很大，學過概率論的同學都知道，最終的表結(jié)構(gòu)肯定非常接近于理想跳躍表。
這樣是不是很簡單？
回歸正題，我們?nèi)绾尾檎业?呢？很簡單，我們看首先和6比較，發(fā)現(xiàn)7大于6，我們就向后走，發(fā)現(xiàn)相等就找到了節(jié)點7.當然，如果我們找5的話就是和6比完之后降到L2，然后和2比，比2大比6小，繼續(xù)降級，找到5。
小明同學是一個很會舉一反三的人，既然都知道查找這么簡單了，就看看插入吧，等把增刪改查都解決了，媽媽就再也不用擔心我的紅黑樹了。

接下來我們就看看插入，我們要插入一個4，怎么辦呢？
從最高層開始找到每一層比4大的節(jié)點的前一個值，然后投硬幣，隨機選擇層數(shù)后插入，舉個例子這個值為4.那么插入之后就是下圖所示。

我們發(fā)現(xiàn)，他會新增一層，并且會在同層級之間進行連接。然后就完成了插入操作。

刪除操作：
刪除操作類似于插入操作，包含如下3步：1、查找到需要刪除的結(jié)點 2、刪除結(jié)點 3、調(diào)整指針。

到此，Skiplist的增刪改查就很明確了，但是知其然我們也得知其所以然，小明同學不拋棄不放棄，想要知道他是怎么樣實現(xiàn)的，以及在上邊過程中自己的問題。

1. 為什么要投硬幣？
我們先解釋一下投硬幣這個流程：跳躍表節(jié)點的層數(shù)限制在了64（在redis5.0之前是32），若想超過64層得連續(xù)64次拋硬幣都得到正面，這得有足夠多的節(jié)點，redis限定了拋硬幣正面的概率為1/4，所以到達64層的概率為(1/2)^128，一般一臺64位的計算機能擁有的最大內(nèi)存也無法存儲這么多zskiplistNode，所以對于基本使用 64層的上限已經(jīng)足夠高了，再高也沒必要 浪費頭節(jié)點的內(nèi)存。所以，投硬幣是為了讓數(shù)據(jù)盡量都在低的層級以達到節(jié)省內(nèi)存的目的。

2. 跳躍表是什么？在哪用？
跳躍表( skiplist) 是一種有序的數(shù)據(jù)結(jié)構(gòu), 它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針,從而達到快速訪問節(jié)點的目的。跳躍表支持平均O(logN),最壞O(N)復雜度的節(jié)點查找. 大部分情況下,跳躍表的效率可以和平衡樹想媲美,并且跳躍表的實現(xiàn)比平衡樹更為簡單。
Redis 使用跳躍表作為有序集合鍵的底層實現(xiàn)之一, 如果一個有序集合包含的元素數(shù)量較多,或者有序集合中元素的成員是比較長的字符串, Redis 會使用跳躍表來作為有序集合的底層實現(xiàn)。
那跳表這么棒在Redis中用到的地方肯定非常多嗎？答案是否定的，Redis 只在兩個地方用到了跳躍表,一個是實現(xiàn)有序集合鍵,另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu), 除此之外,跳躍表在 Redis 中沒有其他用途。

3. 跳躍表是怎么實現(xiàn)的？
我們來看一看skiplist的源碼：

      typedef struct zskiplistNode {
            sds ele;        //元素
            double score;   //分值
            struct zskiplistNode *backward;   //后退指針，后退指針用于從表尾向表頭訪問節(jié)點,跟可以一次跳過多個節(jié)點的前進指針不同,每個節(jié)點只有一個后退指針
            struct zskiplistLevel {
                struct zskiplistNode *forward;   //前進指針，每個層都有一個指向表尾方向的指針.用于從表頭向表尾方向訪問節(jié)點
                unsigned long span;   //跨度，層的跨度用于記錄兩個節(jié)點之間的距離. 兩個節(jié)點之間的跨度越大,它們距離越遠;指向 NULL 的節(jié)點的跨度為0
            } level[];   
        } zskiplistNode;
        //跳躍表的 level 數(shù)組可以包含多個元素,每個元素都包含一個指向其他節(jié)點的指針,程序可以通過這些指針加快訪問速度
        //一般來說,層的數(shù)量越多,訪問其他節(jié)點的速度越快
        //每次創(chuàng)建一個新跳躍表節(jié)點時,程序會根據(jù)冪次定律(越大的數(shù)出現(xiàn)的概率越小)隨機生成一個介于1 和 64 之間的值作為 level 數(shù)組的大小,這個大小就是層的高度
    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;    //表頭和表尾指針
        unsigned long length;       //節(jié)點的數(shù)量
        int level;      //層數(shù)最大的節(jié)點的層數(shù)
    } zskiplist;
    

由此我們可以得出skiplist內(nèi)存結(jié)構(gòu)圖如下：

抽象內(nèi)存結(jié)構(gòu)圖如下：

另外呢？ 我們在gdb有序集合zset代碼的時候，發(fā)現(xiàn)程序會在創(chuàng)建skiplist的之前會先創(chuàng)建一個字典dict。那么，這個dict的作用是什么呢？dict的作用呢是一個hashtable，用來映射元素與zset中分值score的關系。擁有這個映射表，我們?nèi)ゲ檎乙粋€元素的分值時間復雜度就變成了O(1)。

4. redis使用跳躍表而不是平衡樹的原因
skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節(jié)點。

在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現(xiàn)。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現(xiàn)。

平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節(jié)點的指針，操作簡單又快速。

從內(nèi)存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節(jié)點包含2個指針（分別指向左右子樹），而skiplist每個節(jié)點包含的指針數(shù)目平均為1/(1-p)，具體取決于參數(shù)p的大小。如果像Redis里的實現(xiàn)一樣，取p=1/4，那么平均每個節(jié)點包含1.33個指針，比平衡樹更有優(yōu)勢。

查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結(jié)構(gòu)，大都是基于哈希表實現(xiàn)的。

從算法實現(xiàn)難度上來比較，skiplist比平衡樹要簡單得多。

最后，學以致用，知道skiplist是怎么回事，我們還需要知道它的老東家在怎么用它，大家可以想一下Redis中的ZADD，ZRANGE,ZRANGEBYSCORE等命令是怎么用到它的。

如果想要了解有關跳躍表源碼更具體的分析，建議閱讀【Redis學習筆記】2018-05-29 redis源碼學習之跳躍表。