一、為什么Redis一定要用跳表來實現有序集合

跳表的全稱是跳躍表，它的基礎是有序鏈表，在有序鏈表的基礎上，增加多級索引，實現快速查找。跳表的所有額外索引結點總數為 n2+n4+n8+…+4+2=n?2n2+n4+n8+…+4+2=n?2，所以跳表的空間復雜度為 O(n)O(n)。

用跳表查找效率到底可以提升多少

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

這里先來看一個問題，如果鏈表里有 n 個結點，會有多少級索引呢？

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

假設索引有 h 級，較高級的索引有 2 個結點。通過上面的公式，我們可以得到 n/(2h)=2，從而求得 h=log2n-1。如果包含原始鏈表這一層，整個跳表的高度就是 log2n。

我們在跳表中查詢某個數據的時候，如果每一層都要遍歷 m 個結點，那在跳表中查詢一個數據的時間復雜度就是 O(m*logn)。那這個 m 的值是多少呢？按照前面這種索引結構，我們每一級索引都非常多只需要遍歷 3 個結點，也就是說 m=3，為什么是 3 呢？這里解釋一下：

假設我們要查找的數據是 x，在第 k 級索引中，我們遍歷到 y 結點之后，發(fā)現 x 大于 y，小于后面的結點 z，所以我們通過 y 的 down 指針，從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中，y 和 z 之間只有 3 個結點（包含 y 和 z），所以，我們在 K-1 級索引中非常多只需要遍歷 3 個結點，依次類推，每一級索引都非常多只需要遍歷 3 個結點。通過上面的分析，我們得到 m=3，所以在跳表中查詢任意數據的時間復雜度就是 O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現了二分查找，但是，有一個比較雞肋的地方就是：這種查詢效率的提升，前提是建立了很多級索引，即需要占用額外的內存空間。

延伸閱讀：

二、跳表內存使用情況

比起單純的單鏈表，跳表需要存儲多級索引，肯定要消耗更多的存儲空間。下面來看下跳表的空間復雜度。

假設原始鏈表大小為 n，那名列前茅級索引大約有 n/2 個結點，第二級索引大約有 n/4 個結點，以此類推，每上升一級就減少一半，直到剩下 2 個結點。如果我們把每層索引的結點數寫出來，就是一個等比數列。

原始鏈表大小為n，每2個節(jié)點取1個，則每層索引的節(jié)點數：n/2, n/4, n/8, … , 8, 4, 2。

這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復雜度是 O(n)。也就是說，如果將包含 n 個結點的單鏈表構造成跳表，我們需要額外再用接近 n 個結點的存儲空間。那我們有沒有辦法降低索引占用的內存空間呢？我們前面都是每兩個結點抽一個結點到上級索引，如果我們每三個結點或五個結點，抽一個結點到上級索引，這樣是不是就不用那么多索引結點了呢？

通過等比數列求和公式，總的索引結點大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復雜度還是 O(n)，但比上面的每兩個結點抽一個結點的索引構建方法，要減少了一半的索引結點存儲空間。

實際上，在程序開發(fā)中，我們一般不必太在意索引占用的額外空間。因為當對象比索引結點大很多時，那索引占用的額外空間就可以忽略了。