跳躍表定義:
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針唧躲，從而達到快速訪問節(jié)點的目的嗡善。
跳躍表支持平均O（logN）、最壞O（N）復雜度的節(jié)點查找术吝，還可以通過順序性操作來批量處理節(jié)點计济。
跳躍表使用場景:
Redis使用跳躍表作為有序集合鍵的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多排苍，又或者有序集合中元素的成員（member）是比較長的字符串時沦寂，Redis就會使用跳躍表來作為有序集合鍵的底層實現(xiàn),
和鏈表、字典等數(shù)據(jù)結(jié)構被廣泛地應用在Redis內(nèi)部不同淘衙，Redis只在兩個地方用到了跳躍表传藏，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構彤守，除此之外毯侦，跳躍表在Redis里面沒有其他用途。
跳躍表構成:
Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結(jié)構定義具垫。
zskiplistNode結(jié)構用于表示跳躍表節(jié)點:
- 層（level）：節(jié)點中用L1侈离、L2、L3等字樣標記節(jié)點的各個層做修，L1代表第一層霍狰，L2代表第二層抡草，以此類推。
每個層都帶有兩個屬性：前進指針和跨度蔗坯。前進指針用于訪問位于表尾方向的其他節(jié)點康震，而跨度則記錄了前進指針所指向節(jié)點和當前節(jié)點的距離。在上面的圖片中宾濒，連線上帶有數(shù)字的箭頭就代表前進指針腿短，而那個數(shù)字就是跨度。當程序從表頭向表尾進行遍歷時绘梦，訪問會沿著層的前進指針進行橘忱。
后退（backward）指針：節(jié)點中用BW字樣標記節(jié)點的后退指針，它指向位于當前節(jié)點的前一個節(jié)點卸奉。后退指針在程序從表尾向表頭遍歷時使用钝诚。
分值（score）：各個節(jié)點中的1.0、2.0和3.0是節(jié)點所保存的分值榄棵。在跳躍表中凝颇，節(jié)點按各自所保存的分值從小到大排列。
成員對象（obj）：各個節(jié)點中的o1疹鳄、o2和o3是節(jié)點所保存的成員對象拧略。
zskiplist結(jié)構:用于保存跳躍表節(jié)點的相關信息，比如節(jié)點的數(shù)量瘪弓，以及指向表頭節(jié)點和表尾節(jié)點的指針等等垫蛆。
header：指向跳躍表的表頭節(jié)點。
tail：指向跳躍表的表尾節(jié)點
level：記錄目前跳躍表內(nèi)腺怯，層數(shù)最大的那個節(jié)點的層數(shù)（表頭節(jié)點的層數(shù)不計算在內(nèi)）
length：記錄跳躍表的長度袱饭，也即是，跳躍表目前包含節(jié)點的數(shù)量（表頭節(jié)點不計算在內(nèi)
跳躍表展示圖:
zskiplistNod 結(jié)構詳細介紹：
- 結(jié)構定義：
跳躍表節(jié)點的level數(shù)組可以包含多個元素瓢喉，每個元素都包含一個指向其他節(jié)點的指針宁赤，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說栓票，層的數(shù)量越多，訪問其他節(jié)點的速度就越快
查詢遍歷過程：
1）迭代程序首先訪問跳躍表的第一個節(jié)點（表頭）愕够，然后從第四層的前進指針移動到表中的第二個節(jié)點走贪。
2）在第二個節(jié)點時，程序沿著第二層的前進指針移動到表中的第三個節(jié)點惑芭。
3）在第三個節(jié)點時坠狡，程序同樣沿著第二層的前進指針移動到表中的第四個節(jié)點。
4）當程序再次沿著第四個節(jié)點的前進指針移動時遂跟，它碰到一個NULL逃沿，程序知道這時已經(jīng)到達了跳躍表的表尾婴渡，于是結(jié)束這次遍歷。
舉個查詢例子：
假如要查詢 數(shù)值為3.0的位置凯亮，從頭節(jié)點出發(fā)遍歷到3.0, 沿途經(jīng)歷的層：查找的過程只經(jīng)過了一個層边臼，并且層的跨度為3，所以目標節(jié)點在跳躍表中的位置為3假消。是不是很快柠并！
zskiplist 結(jié)構詳細介紹：
- 結(jié)構定義：
通過使用一個zskiplist結(jié)構來持有這些節(jié)點，程序可以更方便地對整個跳躍表進行處理富拗，比如快速訪問跳躍表的表頭節(jié)點和表尾節(jié)點臼予，或者快速地獲取跳躍表節(jié)點的數(shù)量（也即是跳躍表的長度）等信息
跳躍表常見api
總結(jié)
跳躍表是有序集合的底層實現(xiàn)之一。
Redis的跳躍表實現(xiàn)由zskiplist和zskiplistNode兩個結(jié)構組成啃沪，其中zskiplist用于保存跳躍表信息（比如表頭節(jié)點粘拾、表尾節(jié)點、長度）创千，而zskiplistNode則用于表示跳躍表節(jié)點缰雇。
每個跳躍表節(jié)點的層高都是1至32之間的隨機數(shù)。
在同一個跳躍表中签餐，多個節(jié)點可以包含相同的分值寓涨，但每個節(jié)點的成員對象必須是唯一的。?跳躍表中的節(jié)點按照分值大小進行排序氯檐，當分值相同時戒良，節(jié)點按照成員對象的大小進行排序。
