SkipList 跳表的原理

前言

在各類資料結構中，實作的方式無非兩種，數組/連結清單，跳表是一種基于連結清單改進的資料結構，能夠實作快速查找；

levelDB

中便用到了它。

跳表是平衡樹的一種替代的資料結構，但是和紅黑樹不同的是，跳表對于樹的平衡的實作是基于一種随機化的算法
也就是說跳表的插入和删除工作是比較簡單的。
           

接下來我們将了解跳表的實作原理。

跳表的結構

以下是一個普通的連結清單，假設我們需要通路最後一個元素

51

，那麼我們需要從頭到尾周遊連結清單，這樣是非常耗時的，假設我們在該連結清單之上加一層索引呢？

加上一級索引後：

通路最後一個元素的路徑

沒有加索引前通路

51

需要8步，而現在效率提高了一半。

仍可繼續添加

跳表的特點

• 表為有序連結清單
• 存在于目前層的元素，一定存在于其所有底層。（就是如果level3有，那麼level2， level1， level0都有）
• 最底層包含了所有的元素

總結

以上隻是跳表的簡單原理，接下來的部落格中我們将介紹

levelDB

中實作的跳表