跳表是個啥東西請看這個文章。

我們知道，節點插入時隨機出一個層數，僅僅依靠一個簡單的隨機數操作而構建出來的多層鏈表結構，能保證它有一個良好的查找性能嗎？為了回答這個疑問，我們需要分析skiplist的統計性能。

在分析之前，我們還需要著重指出的是，執行插入操作時計算隨機數的過程，是一個很關鍵的過程，它對skiplist的統計特性有著很重要的影響。這并不是一個普通的服從均勻分布的隨機數，它的計算過程如下：

首先，每個節點肯定都有第1層指針（每個節點都在第1層鏈表里）。
如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p。
節點最大的層數不允許超過一個最大值，記為MaxLevel。

這個計算隨機層數的偽碼如下所示：

randomLevel()
level := 1
// random()返回一個[0...1)的隨機數
while random() < p and level < MaxLevel do
level := level + 1
return level

randomLevel()的偽碼中包含兩個參數，一個是p，一個是MaxLevel。在Redis的skiplist實現中，這兩個參數的取值為：

p = 1/4
MaxLevel = 32

skiplist的算法性能分析

在這一部分，我們來簡單分析一下skiplist的時間復雜度和空間復雜度，以便對于skiplist的性能有一個直觀的了解。如果你不是特別偏執于算法的性能分析，那么可以暫時跳過這一小節的內容。

我們先來計算一下每個節點所包含的平均指針數目（概率期望）。節點包含的指針數目，相當于這個算法在空間上的額外開銷(overhead)，可以用來度量空間復雜度。

根據前面randomLevel()的偽碼，我們很容易看出，產生越高的節點層數，概率越低。定量的分析如下：

節點層數至少為1。而大于1的節點層數，滿足一個概率分布。
節點層數恰好等于1的概率為1-p。
節點層數大于等于2的概率為p，而節點層數恰好等于2的概率為p(1-p)。
節點層數大于等于3的概率為p^2，而節點層數恰好等于3的概率為p^2(1-p)。
節點層數大于等于4的概率為p^3，而節點層數恰好等于4的概率為p^3(1-p)。
......

因此，一個節點的平均層數（也即包含的平均指針數目），計算如下：

現在很容易計算出：

當p=1/2時，每個節點所包含的平均指針數目為2；
當p=1/4時，每個節點所包含的平均指針數目為1.33。這也是Redis里的skiplist實現在空間上的開銷。

接下來，為了分析時間復雜度，我們計算一下skiplist的平均查找長度。查找長度指的是查找路徑上跨越的跳數，而查找過程中的比較次數就等于查找長度加1。以前面圖中標出的查找23的查找路徑為例，從左上角的頭結點開始，一直到結點22，查找長度為6。

為了計算查找長度，這里我們需要利用一點小技巧。我們注意到，每個節點插入的時候，它的層數是由隨機函數randomLevel()計算出來的，而且隨機的計算不依賴于其它節點，每次插入過程都是完全獨立的。所以，從統計上來說，一個skiplist結構的形成與節點的插入順序無關。

這樣的話，為了計算查找長度，我們可以將查找過程倒過來看，從右下方第1層上最后到達的那個節點開始，沿著查找路徑向左向上回溯，類似于爬樓梯的過程。我們假設當回溯到某個節點的時候，它才被插入，這雖然相當于改變了節點的插入順序，但從統計上不影響整個skiplist的形成結構。

現在假設我們從一個層數為i的節點x出發，需要向左向上攀爬k層。這時我們有兩種可能：

如果節點x有第(i+1)層指針，那么我們需要向上走。這種情況概率為p。
如果節點x沒有第(i+1)層指針，那么我們需要向左走。這種情況概率為(1-p)。

preview

用C(k)表示向上攀爬k個層級所需要走過的平均查找路徑長度（概率期望），那么：

C(0)=0
C(k)=(1-p)×(上圖中情況b的查找長度) + p×(上圖中情況c的查找長度)

代入，得到一個差分方程并化簡：

C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
C(k)=1/p+C(k-1)
C(k)=k/p

這個結果的意思是，我們每爬升1個層級，需要在查找路徑上走1/p步。而我們總共需要攀爬的層級數等于整個skiplist的總層數-1。

那么接下來我們需要分析一下當skiplist中有n個節點的時候，它的總層數的概率均值是多少。這個問題直觀上比較好理解。根據節點的層數隨機算法，容易得出：

第1層鏈表固定有n個節點；
第2層鏈表平均有n*p個節點；
第3層鏈表平均有n*p^2個節點；
...

所以，從第1層到最高層，各層鏈表的平均節點數是一個指數遞減的等比數列。容易推算出，總層數的均值為log1/pn，而最高層的平均節點數為1/p。

綜上，粗略來計算的話，平均查找長度約等于：

C(log1/pn-1)=(log1/pn-1)/p

即，平均時間復雜度為O(log n)。

當然，這里的時間復雜度分析還是比較粗略的。比如，沿著查找路徑向左向上回溯的時候，可能先到達左側頭結點，然后沿頭結點一路向上；還可能先到達最高層的節點，然后沿著最高層鏈表一路向左。但這些細節不影響平均時間復雜度的最后結果。另外，這里給出的時間復雜度只是一個概率平均值，但實際上計算一個精細的概率分布也是有可能的。

詳情還請參見William Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

skiplist與平衡樹、哈希表的比較

skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。
在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。
平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。
從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。
查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現的。
從算法實現難度上來比較，skiplist比平衡樹要簡單得多。

Redis中的skiplist和經典有何不同

分數(score)允許重復，即skiplist的key允許重復。這在最開始介紹的經典skiplist中是不允許的。
在比較時，不僅比較分數（相當于skiplist的key），還比較數據本身。在Redis的skiplist實現中，數據本身的內容唯一標識這份數據，而不是由key來唯一標識。另外，當多個元素分數相同的時候，還需要根據數據內容來進字典排序。
第1層鏈表不是一個單向鏈表，而是一個雙向鏈表。這是為了方便以倒序方式獲取一個范圍內的元素。
在skiplist中可以很方便地計算出每個元素的排名(rank)。

作者的話

最后我們看看，對于這個問題，Redis的作者 @antirez 是怎么說的：

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.

有幾個原因：

1）它們的記憶力不是很強。基本上由你決定。更改有關節點具有給定數量級別的概率的參數將使內存密集度低于btree。

2）排序集通常是許多Zrange或Zrevrange操作的目標，即作為鏈表遍歷跳過列表。通過此操作，跳過列表的緩存區域性至少與其他類型的平衡樹一樣好。

3）它們易于實現、調試等。例如，由于跳過列表的簡單性，我收到了一個補丁（已經在redis master中），其中包含在o（log（n））中實現zrank的擴展跳過列表。它只需要對代碼稍作修改。