跳錶──沒聽過但很犀利的資料結構

連結串列 · 發表 2018-10-05 13:09:49

摘要：跳錶(skip list) 對標的是平衡樹(AVL Tree)，是一種插入/刪除/搜尋都是 O(log n) 的資料結構。它最大的優勢是原理簡單、容易實現、方便擴充套件、效率更高。因此在一些熱門的專案裡用來替代平衡樹，如 redis, leveldb 等。首先，跳錶處理的是有序的...

跳錶(skip list) 對標的是平衡樹(AVL Tree)，是一種插入/刪除/搜尋都是 O(log n) 的資料結構。它最大的優勢是原理簡單、容易實現、方便擴充套件、效率更高。因此在一些熱門的專案裡用來替代平衡樹，如 redis, leveldb 等。

首先，跳錶處理的是有序的連結串列（一般是雙向連結串列，下圖未表示雙向），如下：

這個連結串列中，如果要搜尋一個數，需要從頭到尾比較每個元素是否匹配，直到找到匹配的數為止，即時間複雜度是 $O(n)$。同理，插入一個數並保持連結串列有序，需要先找到合適的插入位置，再執行插入，總計也是 $O(n)$ 的時間。

那麼如何提高搜尋的速度呢？很簡單，做個索引：

如上圖，我們新建立一個連結串列，它包含的元素為前一個連結串列的偶數個元素。這樣在搜尋一個元素時，我們先在上層連結串列進行搜尋，當元素未找到時再到下層連結串列中搜索。例如搜尋數字 19 時的路徑如下圖：

先在上層中搜索，到達節點 17 時發現下一個節點為 21 ，已經大於 19 ，於是轉到下一層搜尋，找到的目標數字 19 。

我們知道上層的節點數目為 $n/2$，因此，有了這層索引，我們搜尋的時間複雜度降為了：$O(n/2)$。同理，我們可以不斷地增加層數，來減少搜尋的時間：

在上面的 4 層連結串列中搜索 25 ，在最上層搜尋時就可以直接跳過 21 之前的所有節點，因此十分高效。

更一般地，如果有 $k$ 層，我們需要的搜尋次數會小於 $\lceil \frac{n}{2^k} \rceil + k$ ，這樣當層數 $k$ 增加到 $\lceil \log_{2} n \rceil$ 時，搜尋的時間複雜度就變成了 $\log n$。其實這背後的原理和二叉搜尋樹或二分查詢很類似，通過索引來跳過大量的節點，從而提高搜尋效率。

上節的結構是“靜態”的，即我們先擁有了一個連結串列，再在之上建了多層的索引。但是在實際使用中，我們的連結串列是通過多次插入/刪除形成的，換句話說是“動態”的。上節的結構要求上層相鄰節點與對應下層節點間的個數比是 1:2 ，隨意插入/刪除一個節點，這個要求就被被破壞了。

因此跳錶（skip list）表示，我們就不強制要求 1:2 了，一個節點要不要被索引，建幾層的索引，都在節點插入時由拋硬幣決定。當然，雖然索引的節點、索引的層數是隨機的，為了保證搜尋的效率，要大致保證每層的節點數目與上節的結構相當。下面是一個隨機生成的跳錶：

可以看到它每層的節點數還和上節的結構差不多，但是上下層的節點的對應關係已經完全被打破了。

現在假設節點 17 是最後插入的，在插入之前，我們需要搜尋得到插入的位置：

接著，拋硬幣決定要建立幾層的索引，虛擬碼如下：

randomLevel()
lvl := 1
-- random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl

上面的虛擬碼相當於拋硬幣，如果是正面（ random() < p ）則層數加一，直到丟擲反面為止。其中的 MaxLevel 是防止如果運氣太好，層數就會太高，而太高的層數往往並不會提供額外的效能，一般 $MaxLevel = \log_{1/p}{n}$。現在假設 randomLevel 返回的結果是 2 ，那麼就得到下面的結果。

如果要刪除節點，則把節點和對應的所有索引節點全部刪除即可。當然，要刪除節點時需要先搜尋得到該節點，搜尋過程中可以把路徑記錄下來，這樣刪除索引層節點的時候就不需要多次搜尋了。

顯然，在最壞的情況下，所有節點都沒有建立索引，時間複雜度為$O(n)$，但在平均情況下，搜尋的時間複雜度卻是 $O(\log n)$，為什麼呢？

一些嚴格的證明會涉及到比較複雜的概率統計學知識，所以這裡只是簡單地說明。

上面我們提到 MaxLevel ， ofollow,noindex">原版論文中用 L(n) 來表示，要求 L(n) 層有 1/p 個節點，在搜尋時可以不理會比 L(n) 更高的層數，直接從 L(n) 層開始搜尋，這樣效率最高。

直觀上看，第 $l$ 層的節點中在第 $l+1$ 層也有索引的個數是 $n_{l+1} = n_l p$ 因此第 $l$ 層的節點個數為：

$$ n_l = n p^{l-1} $$

於是代入 $n_{L(n)} = 1/p$ 得到 $L(n) = \log_{1/p}n$。

上面推導到每層的節點數目，直觀上看，如果某一層的節點數目小於等於 1，則可以認為它是最高層了，代入 $np^{l-1} = 1$ 得到層數 $L_{max} = \log_{1/p}n + 1 = L(n) + 1 = O(\log n)$。

實際上這個問題並沒有直接的解析解，我們能知道的是，當 $n$ 足夠大時，最大能達到的層數為 $O(\log n)$，詳情可以參見我的另一篇部落格最高樓層問題。

為了計算搜尋的時間複雜度，我們可以將查詢的過程倒過來，從搜尋最後的節點開始，一直向左或向上，直到最頂層。如下圖，在路徑上的每一點，都可能有兩種情況：

p
1-p

於是，設 C(k) 為反向搜尋爬到第 k 層的平均路徑長度，則有：

C(0) = 0
C(k) = p * (情況1) + (1-p) * (情況2)

將兩種情況也用 C 代入，有：

C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
C(k) = C(k–1) + 1/p
C(k) = k/p

上式表明，搜尋時，平均在每層上需要搜尋的路徑長度為 $1/p$，從平均的角度上和我們第一小節構造的“靜態”結構相同（p 取 1/2 ）。

又注意到，上小節我們知道跳錶的最大層數為 $O(\log n)$，因此，搜尋的複雜度 $O(\log n) / p = O(\log n)$。

P.S. 這裡我們用到的是最大層數，原論文證明時用到的是 $L(n)$，然後再考慮從 $L(n)$ 層到最高層的平均節點個數。這裡為了理解方便不再詳細證明。

各種搜尋結構提高效率的方式都是通過空間換時間得到的。
跳錶最終形成的結構和搜尋樹很相似。
跳錶通過隨機的方式來決定新插入節點來決定索引的層數。
跳錶搜尋的時間複雜度是 $O(\log n)$，插入/刪除也是。

想到快排(quick sort)與其它排序演算法（如歸併排序/堆排序）雖然時間複雜度是一樣的，但複雜度的常數項較小；跳錶的原論文也說跳錶能提供一個常數項的速度提升，因此想著常數項小是不是隨機演算法的一個特點？這也它們大放異彩的重要因素吧。

跳錶──沒聽過但很犀利的資料結構

您可能也會喜歡…