17.跳表：為什麼Redis一定要用跳表來實作有序集合？
markdown檔案已上傳至github
因為二分查找底層依賴的是數組随機通路的特性，是以隻能用數組來實作。如果資料存儲在連結清單中，我們隻需要對連結清單稍加改造，就可以支援類似“二分”的查找算法。我們把改造之後的資料結構叫做跳表（Skip list）。
跳表：是一種各方面性能都比較優秀的動态資料結構，可以支援快速地插入、删除、查找操作，寫起來也不複雜，甚至可以替代紅黑樹（Red-black tree）。
1.如何了解“跳表”？
單連結清單中即使存儲的資料有序，我們要查找一個元素也要從頭到尾周遊連結清單，這樣查找效率很低，時間複雜度為O(n)。
為了提高查找效率，可以對連結清單建立一級索引，每兩個結點提取一個節點到上一級，把抽出來的那一級叫做索引或索引層。如圖，down表示為down指針。
如果我們現在要查找某個結點，比如 16。我們可以先在索引層周遊，當周遊到索引層中值為 13 的結點時，我們發現下一個結點是 17，那要查找的結點 16 肯定就在這兩個結點之間。然後我們通過索引層結點的 down 指針，下降到原始連結清單這一層，繼續周遊。這個時候，我們隻需要再周遊 2 個結點，就可以找到值等于 16 的這個結點了。這樣，原來如果要查找 16，需要周遊 10 個結點，現在隻需要周遊 7 個結點。
加一層索引後，查找一個結點需要周遊的結點個數減少了，也就是查找效率提高了。
在第一級索引的基礎上，每兩個結點抽出一個結點到第二級索引，如下圖，現在查找16隻需要周遊6個節點了，周遊的結點又減少了。
假如有64個結點的連結清單，建立五級索引，如下圖：
在沒有索引的時候，查找62需要周遊62個結點，現在隻需要周遊11個結點，當n比較大的時候，查找效率的提升會非常明顯。
2.用跳表查詢到底有多快？
在一個單連結清單中查詢某個資料的時間複雜度是 O ( n ) O(n) O(n)。 在一個具有多級索引的跳表中，查詢某個資料的時間複雜度是多少呢？
把問題分解一下，先來看這樣一個問題，如果連結清單裡有 n 個結點，會有多少級索引呢？
每兩個結點會抽出一個結點作為上一級索引的結點，那第一級索引的結點個數大約就是 n/2，第二級索引的結點個數大約就是 n/4，第三級索引的結點個數大約就是 n/8，依次類推，也就是說，第 k 級索引的結點個數是第 k-1 級索引的結點個數的 1/2，那第 k級索引結點的個數就是 n / ( 2 k ) n/(2^k) n/(2k)。
假設索引有 h 級，最進階的索引有 2 個結點。通過上面的公式，我們可以得到 n / ( 2 h ) = 2 n/(2^h)=2 n/(2h)=2，進而求得 h=log2n-1。如果包含原始連結清單這一層，整個跳表的高度就是$ log_2n$。我們在跳表中查詢某個資料的時候，如果每一層都要周遊 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)。這個查找的時間複雜度跟二分查找是一樣的。換句話說，我們其實是基于單連結清單實作了二分查找。
3.跳表是不是很浪費記憶體
跳表的空間複雜度分析并不難，我在前面說了，假設原始連結清單大小為 n，那第一級索引大約有 n/2 個結點，第二級索引大約有 n/4 個結點，以此類推，每上升一級就減少一半，直到剩下 2 個結點。如果我們把每層索引的結點數寫出來，就是一個等比數列。
這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2。是以，跳表的空間複雜度是 O(n)。也就是說，如果将包含 n 個結點的單連結清單構造成跳表，我們需要額外再用接近 n 個結點的存儲空間。如果我們每三個結點或五個結點抽一個結點到上層索引，需要的索引結點的存儲空間将更少。
實際軟體開發過程中，原始連結清單中存儲的有可能是很大的對象，而索引結點隻需要存儲關鍵值，并不需要存儲對象，是以當對象比索引結點大很多時，那索引所占的額外空間就可以忽略了。
4.高效的動态插入和删除
跳表這個動态資料結構，不僅支援查找操作，還支援動态的插入、删除操作，而且插入、删除操作的時間複雜度也是 O(logn)。
4.1在跳表中插入一個元素
單連結清單一旦定位好要插入資料的位置，插入結點的時間複雜度是O(1)。查找插入位置是比較費時的。
對于跳表來說，查找時間複雜度為 O ( l o g n ) O(logn) O(logn),是以插入時間複雜度為 O ( l o g n ) O(logn) O(logn)。
4.2 跳表中的删除操作
如果這個結點在索引中也有出現，我們除了要删除原始連結清單中的結點，還要删除索引中的。因為單連結清單中的删除操作需要拿到要删除結點的前驅結點，然後通過指針操作完成删除。是以在查找要删除的結點的時候，一定要擷取前驅結點。當然，如果我們用的是雙向連結清單，就不需要考慮這個問題了。
5.跳表索引動态更新
當我們不停地往跳表中插入資料時，如果我們不更新索引，就有可能出現某 2 個索引結點之間資料非常多的情況。極端情況下，跳表還會退化成單連結清單。
如果你了解紅黑樹、AVL 樹這樣平衡二叉樹，你就知道它們是通過左右旋的方式保持左右子樹的大小平衡（如果不了解也沒關系，我們後面會講），而跳表是通過随機函數來維護前面提到的“平衡性”。當我們往跳表中插入資料的時候，我們可以選擇同時将這個資料插入到部分索引層中。我們通過一個随機函數，來決定将這個結點插入到哪幾級索引中，比如随機函數生成了值 K，那我們就将這個結點添加到第一級到第 K 級這 K 級索引中。随機函數的選擇很有講究，從機率上來講，能夠保證跳表的索引大小和資料大小平衡性，不至于性能過度退化。
6.解答開篇
為什麼 Redis 要用跳表來實作有序集合，而不是紅黑樹？
Redis 中的有序集合支援的核心操作主要有下面這幾個：
插入一個資料；
删除一個資料；
查找一個資料；
按照區間查找資料（比如查找值在[100, 356]之間的資料）；
疊代輸出有序序列。
其中，插入、删除、查找以及疊代輸出有序序列這幾個操作，紅黑樹也可以完成，時間複雜度跟跳表是一樣的。但是，按照區間來查找資料這個操作，紅黑樹的效率沒有跳表高。對于按照區間查找資料這個操作，跳表可以做到 O(logn) 的時間複雜度定位區間的起點，然後在原始連結清單中順序往後周遊就可以了。這樣做非常高效。當然，Redis 之是以用跳表來實作有序集合，還有其他原因，比如，跳表更容易代碼實作。雖然跳表的實作也不簡單，但比起紅黑樹來說還是好懂、好寫多了，而簡單就意味着可讀性好，不容易出錯。還有，跳表更加靈活，它可以通過改變索引建構政策，有效平衡執行效率和記憶體消耗。不過，跳表也不能完全替代紅黑樹。因為紅黑樹比跳表的出現要早一些，很多程式設計語言中的 Map 類型都是通過紅黑樹來實作的。我們做業務開發的時候，直接拿來用就可以了，不用費勁自己去實作一個紅黑樹，但是跳表并沒有一個現成的實作，是以在開發中，如果你想使用跳表，必須要自己實作。
7.思考題
如果每三個或者五個結點提取一個結點作為上級索引，對應的在跳表中查詢資料的時間複雜度是多少呢？
如果每三個或者五個節點提取一個節點作為上級索引，那麼對應的查詢資料時間複雜度，應該也還是 O(logn)。
假設每 5 個節點提取，那麼最高一層有 5 個節點，而跳表高度為 log5n，每層最多需要查找 5 個節點，即 O(mlogn) 中的 m = 5，最終，時間複雜度為 O(logn)。
空間複雜度也還是 O(logn)，雖然省去了一部分索引節點，但是似乎意義不大。
8.參考
這個是我學習王争老師的《資料結構與算法之美》所做的筆記，王争老師是前谷歌工程師，該課程截止到目前已有87244人付費學習，品質不用多說。
截取了課程部分目錄，課程結合實際應用場景，從概念開始層層剖析，由淺入深進行講解。本人之前也學過許多資料結構與算法的課程，唯獨王争老師的課給我一種茅塞頓開的感覺，強烈推薦大家購買學習。課程二維碼我已放置在下方，大家想買的話可以掃碼購買。
本人做的筆記并不全面，推薦大家掃碼購買課程進行學習，而且課程非常便宜，學完後必有很大提高。