舉個例子，樓主逛完街要回張江玉蘭香苑，如果從人民廣場做公共汽車回去，要經曆非常多站：
閱讀目錄：
- 基本介紹
- 算法思想
- 演化步驟
- 實作細節
- 總結
SkipList是William Pugh在1990年提出的，它是一種可替代平衡樹的資料結構。 SkipList在實作上相對比較簡單，比如在限定時間條件下，能非常輕松的實作SkipList，但卻實作不了B樹、紅黑樹、AVL樹等，想一想單B樹的删除，就要考慮非常多的細節。雖說SkipList簡單，但性能卻非常高，在平均情況下，其插入、删除、查找資料時間複雜度都是O(log(N))，其最壞情況下都為O(N)，這點要低于平衡樹。
SkipList依賴随機生成數以一定機率來保持資料在樹上的平衡分布，是以SkipList也屬于機率算性的資料結構，和之前介紹的BoolFilter屬于一個類型C#之布隆過濾器(Bloom filter)。
舉個例子，樓主逛完街要回張江玉蘭香苑，如果從人民廣場做公共汽車回去，要路過非常多的站：
想想這麼遠的路程,多悲慘(在大資料情況下找對應項同樣的問題)，相較來說坐地鐵就快很多，然後到廣蘭路換程。 這就是SkipList最核心的思想非常簡單。 現在路線變成：
因為可以一次跨越很多不需要的站，是以就快了很多。如果可以搭朋友順風車的話，變成：
這個圖就非常接近SkipList的結構及思想了。
大緻了解怎麼回事了、看具體怎麼實作。 首先我們忘記樹、圖等進階概念及結構，回到我們剛學到連結清單的時候。 再看上面的回家路線圖，我們把最下面一層當成一個連結清單，每個節點(站)指針指向下一個節點(站)。
單個有序連結清單：
按照傳統的操作有序連結清單的做法，如果需要查找其中一條資料，需要順序周遊。 按照地鐵的思路，如果給一部分的節點增加個指向後面的節點指針，假設一半節點增加，最多周遊[n/2]+1次即可找到任意節點。這裡把18、23、33、40、47節點都多增加個指針指向後面的節點：
以此類推，繼續增加3、4個等更多的指針，使其指向更遠的後方節點，這樣可以更好的提高查詢效率。 3個節點的情況：
如果理想情況下查找，就類似二分查找了。 SkipList通過随機數(丢硬币決定)在插入節點時，随機判定該節點應該有多少個執行後續節點的指針。 有幾個執行後面節點指針，就是在第幾層，比如上圖18存在3個指針指向後面，它就在第三層，23有2個指針就在第二層。
搜尋
在同一層查找節點時和普通有序連結清單一樣，順序向後查找，查到傳回，否則進入下一層繼續向後查找。比如查找35，會從最頂層搜尋比較18、相等傳回，大于比較40繼續下一層找，比較1、23、33、40後繼續下一層，比較33、35正确傳回、否則不存在。
更新
搜尋到值後更新：
SkipListNode<TKey, TValue> position;
bool found = search(key, out position);
if(found)
position.value = value; 插入
插入時，如果值存在則更新，不存在插入。 如上圖，假如要插入29，需要先查找到27插入到後面，如果扔硬币後得到3，那麼依次增加指向後面節點的指針。
随機數
也稱丢硬币做法。
Random generator = new Random();
int levels = 0;
while (generator.NextDouble() < 0.5&&levels<=maxlevel)
levels++;
return levels; 删除同插入一樣，如果找到，調整相對應的指針順序，然後删除節點。
由于skipList的高效及維護簡單，是以很多大資料系統中在維護有序清單是都會使用SkipList。比如LevelDB在記憶體中暫存資料的結構MemTable是使用SkipList實作的，Redis在Sorted Set資料結構時也采用的是SkipList，還有Lucene中同樣采用SkipList來對倒排清單進行快速查找。
關于就算法的實作， 可參考https://github.com/kencausey/SkipList
探索C#之系列導航
作者：蘑菇先生
出處： http://mushroom.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載。未經作者同意下，必須在文章頁面明顯标出原文連結及作者，否則保留追究法律責任的權利。
如果您認為這篇文章還不錯或者有所收獲，可以點選右下角的
【推薦】按鈕，因為你的支援是我繼續寫作，分享的最大動力！