探索c#之跳躍表(SkipList)
基本介紹
SkipList是William Pugh在1990年提出的，它是一種可替代平衡樹的數據結構。 SkipList在實現上相對比較簡單，比如在限定時間條件下，能非常輕松的實現SkipList，但卻實現不了B樹、紅黑樹、AVL樹等，想一想單B樹的刪除，就要考慮非常多的細節。雖說SkipList簡單，但性能卻非常高，在平均情況下，其插入、刪除、查找數據時間復雜度都是O(log(N))，其最壞情況下都為O(N)，這點要低於平衡樹。
由於skipList的高效及維護簡單，所以很多大數據系統中在維護有序列表是都會使用SkipList，比如LevelDB在內存中暫存數據的結構MemTable就是使用SkipList實現的，Redis在Sorted Set數據結構時也采用的是SkipList，還有Lucene中同樣采用SkipList來對倒排列表進行快速查找。
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;
刪除同插入一樣，如果找到，調整相對應的指針順序，然後刪除節點。
