基于天然概率的無需人為平衡的skiplist的美之展現

任何事情都無法阻擋我對一種簡單之美的由衷驚嘆。
半夜思索，無法入眠，索性起床看會書，關于中東文明的，可是又看不進去，也許是潮熱的原因 吧...還不如靜下心來寫一篇意識流文章，我指的是不用思考的那種，我已經被近東，中東的錯綜復雜的歷史搞的有點煩了，那真是太難了。然而你能想象我指的 那個不用思考的東西是一個算法嗎？算法不都是很難的嗎？真的就是一個算法，也可以說是一個數據結構，這就是skiplist。
       可以從網上找到大量深入分析skiplist的資料，包括分析其時間復雜度，空間占用情況的。但是本文不，因為我不想在一個如此美好的早上就消耗腦細胞，也不能說是早上，此時凌晨3點整！！注意，我是不需要怎么睡覺還能保持精力的那種怪人。
       那就開始了。
       說到查找，首先能想到的幾乎就是各種查找樹，當然，實際上在實用主義看來用得比較多的還是HASH，查找樹可能學院派更加青睞一些吧。至于HASH，它可 能受制于擴展性，需要不斷的reHASH操作，然而對于動態節點，有一種一致性HASH可以參考，大量用于分布式環境，它完美解決了擴展性問題。當然它體 現了另一種動態美，以后如果哪天早上又打雞血了，會寫一篇分析一下的。提到HASH的不易擴展性以及reHASH操作，查找樹事實上是可以無限擴展的，但 是在擴展過程中，會破壞樹的平衡性，破壞了平衡性就會嚴重損耗查找樹的查找性能，因此為了在擴展過程中保持平衡，需要一種人為的干預，這種干預就是所謂的 “平衡”操作。
       不管對于AVL樹，2-3-4樹，還是衍生出來的紅黑樹，都是以上所述的這類查找樹的典型。如果說有一種數據結構，在擴展過程中可以自然而然地保持平衡性，根本無需人為干預，那該有多好。
       我是一個基因決定論的信徒，相信任何的爆發或者隕滅都是由原始基本基因決定的，當然這是蝴蝶效應的一種體現。我天然反對健身房減肥，因為我相信瘦的人是基 因決定的，怎么吃都不會胖，就好比掰手腕，很多人根本就沒有練過，但是天然力氣驚人，瞬間扳倒在健身房練了好幾年的，這些人一旦離開了健身房，馬上肌肉就 變成了消失了，脂肪越來越多...這種在健身房練就一身肌肉的，就好像AVL樹，紅黑樹，需要花費成本不斷地進行平衡斧正，而對于那種天然基因決定的擁有 完美曲線的人，就好比skiplist，快樂生活，自由成長。

skiplist簡介

本文就不介紹了，不過當你baidu了之后，你幾乎也就理解了skiplist的全部，也就無需再接著看下去了，因此更多的，本文屬于我自己的記錄隨筆。

插入過程理解skiplist

下圖展示了一個skiplist的插入構建過程：

skiplist查找示例

skiplist的美之展現

在畫圖的過程中，我發現不經意間所有的話都表達在圖示里面了，無需更多的言語，這難道就是簡單之美嗎？

統計性能！統計性能！統計性能！統計性能！還是統計性能！