一、為什么Redis一定要用跳表來(lái)實(shí)現(xiàn)有序集合

跳表的全稱(chēng)是跳躍表，它的基礎(chǔ)是有序鏈表，在有序鏈表的基礎(chǔ)上，增加多級(jí)索引，實(shí)現(xiàn)快速查找。跳表的所有額外索引結(jié)點(diǎn)總數(shù)為 n2+n4+n8+…+4+2=n?2n2+n4+n8+…+4+2=n?2，所以跳表的空間復(fù)雜度為 O(n)O(n)。

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

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

這里先來(lái)看一個(gè)問(wèn)題，如果鏈表里有 n 個(gè)結(jié)點(diǎn)，會(huì)有多少級(jí)索引呢？

按照我們剛才講的，每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)，那名列前茅級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大概就是 n/2，第二級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/4，第三級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/8，依次類(lèi)推，也就是說(shuō)，第 k 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第 k-1 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的 1/2，那第 k 級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是 n/(2k)。

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

我們?cè)谔碇胁樵?xún)某個(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷 m 個(gè)結(jié)點(diǎn)，那在跳表中查詢(xún)一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(m*logn)。那這個(gè) m 的值是多少呢？按照前面這種索引結(jié)構(gòu)，我們每一級(jí)索引都非常多只需要遍歷 3 個(gè)結(jié)點(diǎn)，也就是說(shuō) m=3，為什么是 3 呢？這里解釋一下：

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

延伸閱讀：

二、跳表內(nèi)存使用情況

比起單純的單鏈表，跳表需要存儲(chǔ)多級(jí)索引，肯定要消耗更多的存儲(chǔ)空間。下面來(lái)看下跳表的空間復(fù)雜度。

假設(shè)原始鏈表大小為 n，那名列前茅級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)，以此類(lèi)推，每上升一級(jí)就減少一半，直到剩下 2 個(gè)結(jié)點(diǎn)。如果我們把每層索引的結(jié)點(diǎn)數(shù)寫(xiě)出來(lái)，就是一個(gè)等比數(shù)列。

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

這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復(fù)雜度是 O(n)。也就是說(shuō)，如果將包含 n 個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近 n 個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。那我們有沒(méi)有辦法降低索引占用的內(nèi)存空間呢？我們前面都是每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)到上級(jí)索引，如果我們每三個(gè)結(jié)點(diǎn)或五個(gè)結(jié)點(diǎn)，抽一個(gè)結(jié)點(diǎn)到上級(jí)索引，這樣是不是就不用那么多索引結(jié)點(diǎn)了呢？

通過(guò)等比數(shù)列求和公式，總的索引結(jié)點(diǎn)大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復(fù)雜度還是 O(n)，但比上面的每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法，要減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間。

實(shí)際上，在程序開(kāi)發(fā)中，我們一般不必太在意索引占用的額外空間。因?yàn)楫?dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。