上兩節我們講了二分查找算法。當時我講到，因為二分查找底層依賴的是數組隨機訪問的特性，所以只能用數組來實現。如果數據存儲在鏈表中，就真的沒法用二分查找算法了嗎？

實際上，我們只需要對鏈表稍加改造，就可以支持類似“二分”的查找算法。我們把改造之后的數據結構叫作跳表（Skip list），也就是今天要講的內容。

跳表這種數據結構對你來說，可能會比較陌生，因為一般的數據結構和算法書籍里都不怎么會講。但是它確實是一種各方面性能都比較優秀的動態數據結構，可以支持快速插入，刪除，查找操作，寫起來也不復雜，甚至可以替代紅黑樹（Red-black-tree）。

Redis中的有序集合（Sorted Set）就是用跳表來實現的。如果你有一定基礎，應該知道紅黑樹也可以實現地插入，刪除和查找操作。那Redis為什么會選擇用跳表來實現有序集合呢？為什么不用紅黑樹呢？學完今天的內容，你就知道答案了。

如何理解“跳表”？

對于一個單鏈表來講，即便鏈表中存儲的數據是有序的，如果我們要想在其中查找某個數據，也只能從頭到尾遍歷鏈表。這樣查找效率就會很低，時間復雜度很高，是O（n）。

那怎么來提高查找效率呢？如果像圖中那樣，對鏈表建立一級“索引”，查找起來是不是就會更快一些呢？每兩個結點提取一個結點到上一級，我們把抽出來的那一級叫做索引或索引層。你可以看我畫圖。圖中的down表示down指針，指向下一級結點。

如果我們現在要查找某個結點，比如17。我們可以先在索引層遍歷，當遍歷到索引層中值為16，我們發現下一個結點是18，那要查找的結點17肯定就在這兩個結點之間。然后我們通過索引層結點的down指針，下降到原始鏈表這一層，繼續遍歷。這個時候，我們只需要再遍歷2個結點，就可以找等于17的這個結點了。這樣原來如果要查找17，需要遍歷10個結點，現在只需要7個結點。

從這個例子里，我們看出，加來一層索引之后，查找一個結點需要的結點個數減少了，也就是說查找效率提高了。那如果我們再加一級索引呢？效率會不會提升更多呢？

跟前面建立第一級索引的方式相似，我們在第一級索引的基礎之上，每兩個結點就抽出一個結點到第二級索引。現在我們再來查找17，需要6個結點了，需要遍歷的結點數量又減少了。

我舉的例子數據量不大，所以即便加了兩級索引，查找效率的提升也并不明顯。為了讓你能真切地感受索引提升查找效率。我畫了一個包含64個結點的鏈表，按照前面講的這種思路，建立了五級索引。

從圖中我們可以看出，原來沒有索引的時候，查找62需要遍歷62個結點，現在只需要遍歷11個結點，速度是不是提高了很多？所以，當鏈表的長度n比較大時，比如1000,10000的時候，在構建索引之后，查找效率的提升就會非常明顯。

前面講的這種鏈表加多級索引的結構，就是跳表。我通過例子給你展示了跳表是如何減少查詢次數的，現在你應該比較清晰地知道，跳表確實是可以提高查詢效率的。接下里，我會定量地分析一下，用跳表查詢到底有多快。

用跳表查詢到底有多快？

前面我講過，算法的執行效率可以通過時間復雜度來度量，這里依舊可以用。我們知道，在一個單鏈表中查詢某個數據的時間復雜度是O(n)。那在一個具有多級索引的跳表中，查詢某個數據的時間復雜度是多少呢？

這個時間復雜度的分析方法比較難想到。我把問題分解一下，先來看這樣的一個問題，如果鏈表里有n個結點，會有多少級索引呢？

按照我們剛才講的，每兩個結點會抽出一個結點作為上一級索引的結點，那第一級索引的結點個數大約就是n/2，第二級索引的結點個數大約就是n/4，第三級索引的結點個數大約就是n/8，依次類推，也就是說，第k級索引的結點個數是第k-1級索引的結點個數的1/2，那第k級索引結點的個數的就是n/(2^k)。

假設索引有h級，最高級的索引有2個結點。通過上面的公式，我們可以得到n/(2^h) =2,從而求得h = log2n-1。如果包含原始鏈表這一層，整個跳表的高度就是log2n。我們在跳表中查詢某個數據的時候，如果每一層都要遍歷m個結點，那在跳表中查詢一個數據的時間復雜度就是O(m*logn)。

那這個m的值是多少呢？按照前面這種索引結構，我們每一級索引都最多只需要遍歷3個結點，也就是說m=3,為什么是3呢？我解釋一下。

假設我們要查找的數據是x,在第k級索引中，我們遍歷到y的結點之后，發現x大于y，小于后面的結點z,所以我們通過y的down指針，從第k級索引下降到第k-1級索引。在第k-1級 索引中，y和z之間只有3個結點（包含y和z），所以，我們在k-1級索引中最多只需要遍歷3個結點，依次類推，每一級索引都最多只需要遍歷3個結點。

通過上面的分析，我們得到m=3,所以在跳表中查找任意數據的時間復雜度就是O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現的二分查找，是不是很神奇？不過，天下沒有免費的午餐，這種查詢效率的提升，前提是建立了很多級索引，也就是我們在第6節講過的空間換時間的設計思路。

跳表是不是很浪費內存？

比起單純的單鏈表，跳表需要存儲多級索引，肯定要消耗更多的存儲空間。那到底需要消耗多少額外的存儲空間呢？我們來分析一下跳表的空間復雜度。

跳表的空間復雜度分析并不難，我在前面說了，假設原始鏈表大小為n，那第一級索引大約有n/2個結點，第二級索引大約有n/4個結點，以此類推，每上升一級就減少一半，直到剩下2個結點。如果我們每層索引的結點數寫出來，就是一個等比數列。

這幾級索引得到結點總和就是n/2+n/4+n/8...+8+4+2=n-2。所以，跳表的空間復雜度是O(n)。也就是說，如果將包含n個結點的單鏈表構造成跳表，我們需要額外再用接近n個結點的存儲空間。那我們有沒有辦法降低索引占用的內存空間呢？

實際上，在軟件開發中，我們不必太在意索引占用的額外空間。在講數據結構和算法時，我們習慣性地把要處理的數據看成整數，但是在實際的軟件開發中，原始鏈表中存儲的有可能是很大的對象，而索引結點只需要存儲關鍵值和幾個指針，并不需要存儲對象，所以當對象比索引結點大很多時，那索引占用的額外空間就可以忽略了。

高效的動態插入和刪除

跳表長什么樣子我想你應該已經很清楚了，它的查找操作我們剛剛也講過了。實際上，跳表這個動態數據結構，不僅支持查找操作，還支持動態的插入，刪除操作，而且插入，刪除操作的時間復雜度也是O(logn)。

我們現在來看下，如何在跳表中插入一個數據，以及它是如何做到O（logn）的時間復雜度的？

我們知道，在單鏈表中，一旦定位好要插入的位置，插入結點的時間復雜度是很低的，就是O（1）。但是，這里為了保證原始鏈表中數據的有序性，我們需要先找到要插入的位置，這個查找操作就會比較耗時。

對于純粹的單鏈表，需要遍歷每個結點，來找到插入的位置。但是，對于跳表來說，我們講過查找某個結點的時間復雜度是O（logn），所以這里查找某個數據應該插入的位置，方法也是類似的，時間復雜度也是O（logn）。我畫了一張圖，你可以很清晰地看到插入的過程。

好了，我們再來看刪除操作。

如果這個結點在索引中也有出現，我們除了要刪除原始鏈表中的結點，還要刪除索引中的。因為單鏈表中的刪除操作需要拿到要刪除結點的前驅結點，然后通過指針操作完成刪除。所以在查找要刪除的結點的時候，一定要獲取前驅結點。當然，如果我們用的雙向鏈表，就不需要考慮這個問題了。

跳表索引動態更新

當我們不停地往跳表中插入數據時，如果我們不更新索引，就有可能出現某2個索引結點之間數據非常多的情況。極端情況下，跳表還會退化成單鏈表。

作為一種動態數據結構，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結點多了，索引結點就相應地增加一些，避免復雜度退化，以及查找，插入，刪除操作性能下降。

如果你了解紅黑樹，AVL樹這樣平衡二叉樹，你就知道他們是通過左右旋的方式保持左右子樹的大小平衡（如果不了解也沒關系，我們后面會講），而跳表是通過隨機函數來維護前面提到的“平衡性”。

當我們往跳表中插入數據的時候，我們可以選擇同時將這個數據插入到部分索引層中。如何選擇假如哪些索引層呢？

我們通過一個隨機函數，來決定將這個結點插入到哪幾級索引中，比如隨機函數生成了值K,那我們就將這個結點添加到第一級到第K級這K級索引中。

隨機函數的選擇很有講究，從概率上來講，能夠保證跳表的索引大小和數據大小平衡性，不至于性能過度退化。至于隨機函數的選擇，我就不展開講解了。

跳表的實現還是稍微有點復雜，跳表的實現并不是我們這節的重點。

解答開篇

今天的內容到此就講完了。現在，我來講解一下開篇的思考題:為什么Redis要用跳表來實現有序集合，而不是紅黑樹。

Redis中的有序集合是通過跳表來實現的，嚴格點講，其實還用到了散列表。不過散列表我們后面才會講到，所以我們現在暫且忽略這部分。如果你去查看Redis的開發手冊，就會發現，Redis中的有序集合支持的核心操作主要有下面這幾個：

·插入一個數據

·刪除一個數據

·查找一個數據

·按照區間查找數據（比如查找值在[100,356]之間的數據）

·迭代輸出有序序列。

其中插入，刪除，查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成，時間復雜度跟跳表是一樣的。但是，按照區間來查找數據這個操作，紅黑樹的效率沒有跳表高。

對于按照區間查找數據這個操作，跳表可以做到O(logn)的時間復雜度定位區間的起點，然后在原始鏈表中順序往后遍歷就可以了。這樣做非常高效。

當然，Redis之所以用跳表來實現有序集合，還有其他原因，比如，跳表更容易代碼實現。雖然跳表的實現也不簡單，但比起紅黑樹來說還是好懂，好寫多了，而簡單就意味著可讀性好，不容易出錯。還有，跳表更加靈活，它可以通過改變索引構建策略，有效平衡執行效率和內存消耗。

不過，跳表也不能完全替代紅黑樹。因為紅黑樹比跳表的出現要早一些，很多編程語言中的map類型都是通過紅黑樹來實現的，我們做業務開發的是，直接拿來用就可以了，不用費勁自己去實現一個紅黑樹，但是跳表并沒有一個現成的實現，所以，在開發中，如果你想使用跳表，必須要自己實現。

內容小結

今天我們講了跳表這種數據結構。跳表使用空間換時間的設計思路，通過構建多級索引來提高查詢的效率，實現了基于鏈表的“二分查找”。跳表時候一種動態數據結構，支持快速地插入，刪除，查找操作，時間復雜度都是O（logn）。

跳表的空間復雜度是O（n）。不過，跳表的實現非常靈活，可以通過改變索引構建策略，有效平衡執行效率和內存消耗。雖然跳表的代碼實現并不簡單，但是作為一種動態數據結構，比起紅黑樹來說，實現要簡單多了。所以很多時候，我們為了代碼的簡單，易讀，比起紅黑樹，我們更傾向用跳表。

參考文獻

王爭老師 《數據結構與算法之美》

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的为什么redis取出来是null_跳表：为什么Redis一定要用跳表来实现有序集合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。