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

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

大家想象一下下面這種場(chǎng)景：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從算法實(shí)現(xiàn)難度上來(lái)比較，skiplist比平衡樹(shù)要簡(jiǎn)單得多。

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

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