什麼是跳躍表？
SkipList在leveldb、redis以及lucence中都廣為使用，是比較高效的資料結構。由于它的代碼以及原理實作的簡單性，更為人們所接受。我們首先看看SkipList的定義，為什麼叫跳躍表？
“ Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees. ”
譯文：跳躍表使用機率均衡技術而不是使用強制性均衡，是以，對于插入和删除結點比傳統上的平衡樹算法更為簡潔高效。
跳躍表的了解
有序表的搜尋：考慮一個有序表
從該有序表中搜尋元素 < 23, 43, 59 > ，需要比較的次數分别為 < 2, 4, 6 >，總共比較的次數為 2 + 4 + 6 = 12 次。有沒有優化的算法嗎? 連結清單是有序的，但不能使用二分查找。類似二叉搜尋樹，我們把一些節點提取出來，作為索引。得到如下結構：
提取出來作為一級索引，這樣搜尋的時候就可以減少比較次數了。
我們還可以再從一級索引提取一些元素出來，作為二級索引，三級索引…
這裡元素不多，展現不出優勢，如果元素足夠多，這種索引結構就能展現出優勢來了。
跳表
下面的結構是就是跳表：
其中 -1 表示 INT_MIN， 連結清單的最小值，1 表示 INT_MAX，連結清單的最大值。
跳表具有如下性質：
(1) 由很多層結構組成
(2) 每一層都是一個有序的連結清單
(3) 最底層(Level 1)的連結清單包含所有元素
(4) 如果一個元素出現在 Level i 的連結清單中，則它在 Level i 之下的連結清單也都會出現。
(5) 每個節點包含兩個指針，一個指向同一連結清單中的下一個元素，一個指向下面一層的元素。
跳表的搜尋
例子：查找元素 117
(1) 比較 21， 比 21 大，往後面找
(2) 比較 37, 比 37大，比連結清單最大值小，從 37 的下面一層開始找
(3) 比較 71, 比 71 大，比連結清單最大值小，從 71 的下面一層開始找
(4) 比較 85， 比 85 大，從後面找
(5) 比較 117， 等于 117， 找到了節點。
具體的搜尋算法如下：
/* 如果存在 x, 傳回 x 所在的節點，
* 否則傳回 x 的後繼節點 */
find(x)
{
p = top;
while (1) {
while (p->next->key < x)
p = p->next;
if (p->down == NULL)
return p->next;
p = p->down;
}
} 跳表的插入
先确定該元素要占據的層數 K（采用丢硬币的方式，這完全是随機的）
然後在 Level 1 … Level K 各個層的連結清單都插入元素。
例子：插入 119， K = 2
如果 K 大于連結清單的層數，則要添加新的層。
例子：插入 119， K = 4
丢硬币決定 K
插入元素的時候，元素所占有的層數完全是随機的，通過一下随機算法産生：
int random_level()
{
K = 1;
while (random(0,1))
K++;
return K;
} 相當與做一次丢硬币的實驗，如果遇到正面，繼續丢，遇到反面，則停止，
用實驗中丢硬币的次數 K 作為元素占有的層數。顯然随機變量 K 滿足參數為 p = 1/2 的幾何分布，
K 的期望值 E[K] = 1/p = 2. 就是說，各個元素的層數，期望值是 2 層。
跳表的高度。
n 個元素的跳表，每個元素插入的時候都要做一次實驗，用來決定元素占據的層數 K， 跳表的高度等于這 n 次實驗中産生的最大 K，待續。。。
跳表的空間複雜度分析
根據上面的分析，每個元素的期望高度為 2， 一個大小為 n 的跳表，其節點數目的期望值是 2n。
跳表的删除
在各個層中找到包含 x 的節點，使用标準的 delete from list 方法删除該節點。
例子：删除 71
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而不用平衡樹？
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. 這裡從記憶體占用、對範圍查找的支援和實作難易程度這三方面總結的原因。
資料出處：https://blog.csdn.net/u014427196/article/details/52454462