一、為什么Redis一定要用跳表來實現(xiàn)有序集合
跳表的全稱是跳躍表,它的基礎是有序鏈表,在有序鏈表的基礎上,增加多級索引,實現(xiàn)快速查找。跳表的所有額外索引結(jié)點總數(shù)為 n2+n4+n8+…+4+2=n?2n2+n4+n8+…+4+2=n?2,所以跳表的空間復雜度為 O(n)O(n)。
用跳表查找效率到底可以提升多少
前面我講過,算法的執(zhí)行效率可以通過時間復雜度來度量,這里依舊可以用。我們知道,在一個單鏈表中查詢某個數(shù)據(jù)的時間復雜度是 O(n)。那在一個具有多級索引的跳表中,查詢某個數(shù)據(jù)的時間復雜度是多少呢?
這里先來看一個問題,如果鏈表里有 n 個結(jié)點,會有多少級索引呢?
按照我們剛才講的,每兩個結(jié)點會抽出一個結(jié)點作為上一級索引的結(jié)點,那名列前茅級索引的結(jié)點個數(shù)大概就是 n/2,第二級索引的結(jié)點個數(shù)大約就是 n/4,第三級索引的結(jié)點個數(shù)大約就是 n/8,依次類推,也就是說,第 k 級索引的結(jié)點個數(shù)是第 k-1 級索引的結(jié)點個數(shù)的 1/2,那第 k 級索引結(jié)點的個數(shù)就是 n/(2k)。
假設索引有 h 級,較高級的索引有 2 個結(jié)點。通過上面的公式,我們可以得到 n/(2h)=2,從而求得 h=log2n-1。如果包含原始鏈表這一層,整個跳表的高度就是 log2n。
我們在跳表中查詢某個數(shù)據(jù)的時候,如果每一層都要遍歷 m 個結(jié)點,那在跳表中查詢一個數(shù)據(jù)的時間復雜度就是 O(m*logn)。那這個 m 的值是多少呢?按照前面這種索引結(jié)構(gòu),我們每一級索引都非常多只需要遍歷 3 個結(jié)點,也就是說 m=3,為什么是 3 呢?這里解釋一下:
假設我們要查找的數(shù)據(jù)是 x,在第 k 級索引中,我們遍歷到 y 結(jié)點之后,發(fā)現(xiàn) x 大于 y,小于后面的結(jié)點 z,所以我們通過 y 的 down 指針,從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中,y 和 z 之間只有 3 個結(jié)點(包含 y 和 z),所以,我們在 K-1 級索引中非常多只需要遍歷 3 個結(jié)點,依次類推,每一級索引都非常多只需要遍歷 3 個結(jié)點。通過上面的分析,我們得到 m=3,所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復雜度就是 O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說,我們其實是基于單鏈表實現(xiàn)了二分查找,但是,有一個比較雞肋的地方就是:這種查詢效率的提升,前提是建立了很多級索引,即需要占用額外的內(nèi)存空間。
延伸閱讀:
二、跳表內(nèi)存使用情況
比起單純的單鏈表,跳表需要存儲多級索引,肯定要消耗更多的存儲空間。下面來看下跳表的空間復雜度。
假設原始鏈表大小為 n,那名列前茅級索引大約有 n/2 個結(jié)點,第二級索引大約有 n/4 個結(jié)點,以此類推,每上升一級就減少一半,直到剩下 2 個結(jié)點。如果我們把每層索引的結(jié)點數(shù)寫出來,就是一個等比數(shù)列。
原始鏈表大小為n,每2個節(jié)點取1個,則每層索引的節(jié)點數(shù):n/2, n/4, n/8, … , 8, 4, 2。
這幾級索引的結(jié)點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空間復雜度是 O(n)。也就是說,如果將包含 n 個結(jié)點的單鏈表構(gòu)造成跳表,我們需要額外再用接近 n 個結(jié)點的存儲空間。那我們有沒有辦法降低索引占用的內(nèi)存空間呢?我們前面都是每兩個結(jié)點抽一個結(jié)點到上級索引,如果我們每三個結(jié)點或五個結(jié)點,抽一個結(jié)點到上級索引,這樣是不是就不用那么多索引結(jié)點了呢?
通過等比數(shù)列求和公式,總的索引結(jié)點大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復雜度還是 O(n),但比上面的每兩個結(jié)點抽一個結(jié)點的索引構(gòu)建方法,要減少了一半的索引結(jié)點存儲空間。
實際上,在程序開發(fā)中,我們一般不必太在意索引占用的額外空間。因為當對象比索引結(jié)點大很多時,那索引占用的額外空間就可以忽略了。