1.什么是skiplist跳表

跳表是一種特殊的鏈表，特殊的點在于其可以進行二分查找。普通的鏈表要查找元素只能挨個遍歷鏈表中的所有元素，而跳表則利用了空間換時間的策略，在原來有序鏈表的基礎上面增加了多級索引，然后利用類似二分查找的思路來快速實現查找功能。跳表可以支持快速的查找，插入，刪除等操作，時間復雜度為O(logn)，空間復雜度為O(n)。

2.隨機層數的計算

跳表在節點插入時候，會隨機出一個層數，依靠這個隨機數操作構建的多層鏈表結構，能保證一個比較好的查找性能。這個隨機層數不是一個普通的服從均勻分布的隨機數，具體的計算邏輯如下

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

偽代碼如下

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

randomLevel邏輯中包含有兩個參數，一個是概率p，一個是最大層數MaxLevel。在redis的實現中，這兩個參數分別為

p = 1/4
MaxLevel = 32

該部分內容來自于如下文檔:

skiplist的算法性能分析

關于跳表本身更詳細的講解可以參考上述文檔。

3.redis為什么要使用跳表

經常會有人問這個問題，redis中為什么要使用跳表？

這個問題，redis作者已經給出過明確答案

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.跳表不是非常吃內存，并且基本是取決于你自己。你可以通過改變參數p(第二部分中提到的)，從而達到比btree消耗更少內存的目的。

2.redis中的zset結構經常會使用ZRANGE或者ZREVRANGE這種操作，這個時候遍歷跳表就相當于遍歷一個普通的鏈表。這種情況下，跳表的表現跟btree一樣優秀。

3.很多人認為這一點是最重要的原因。跳表實現起來更容易，只需要一點點代碼就能達到效果，修改起來也很方便。