因?yàn)槎植檎业讓右蕾嚨氖菙?shù)組隨機(jī)訪問(wèn)的特性寓搬，所以只能用數(shù)組來(lái)實(shí)現(xiàn)珍昨。如果數(shù)據(jù)存儲(chǔ)在鏈表中，就真的沒(méi)法用二分查找算法了嗎句喷？
實(shí)際上镣典，我們只需要對(duì)鏈表稍加改造，就可以支持類似“二分”的查找算法唾琼。我們把改造之后的數(shù)據(jù)結(jié)構(gòu)叫作跳表（Skip list）
它確實(shí)是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)兄春，可以支持快速的插入、刪除锡溯、查找操作赶舆，寫起來(lái)也不復(fù)雜，甚至可以替代紅黑樹(shù)（Red-black tree）祭饭。
Redis 中的有序集合（Sorted Set）就是用跳表來(lái)實(shí)現(xiàn)的芜茵。如果你有一定基礎(chǔ)，應(yīng)該知道紅黑樹(shù)也可以實(shí)現(xiàn)快速的插入倡蝙、刪除和查找操作夕晓。那 Redis 為什么會(huì)選擇用跳表來(lái)實(shí)現(xiàn)有序集合呢？ 為什么不用紅黑樹(shù)呢悠咱？
1如何理解“跳表”？
對(duì)于一個(gè)單鏈表來(lái)講征炼，即便鏈表中存儲(chǔ)的數(shù)據(jù)是有序的析既，如果我們要想在其中查找某個(gè)數(shù)據(jù)，也只能從頭到尾遍歷鏈表谆奥。這樣查找效率就會(huì)很低眼坏，時(shí)間復(fù)雜度會(huì)很高，是 O(n)酸些。
那怎么來(lái)提高查找效率呢宰译？如果像圖中那樣，對(duì)鏈表建立一級(jí)“索引”魄懂，查找起來(lái)是不是就會(huì)更快一些呢沿侈？每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽出來(lái)的那一級(jí)叫作索引或索引層市栗。你可以看我畫(huà)的圖缀拭。圖中的 down 表示 down 指針咳短，指向下一級(jí)結(jié)點(diǎn)。
如果我們現(xiàn)在要查找某個(gè)結(jié)點(diǎn)蛛淋，比如 16咙好。我們可以先在索引層遍歷，當(dāng)遍歷到索引層中值為 13 的結(jié)點(diǎn)時(shí)褐荷，我們發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)是 17勾效，那要查找的結(jié)點(diǎn) 16 肯定就在這兩個(gè)結(jié)點(diǎn)之間。然后我們通過(guò)索引層結(jié)點(diǎn)的 down 指針叛甫，下降到原始鏈表這一層层宫，繼續(xù)遍歷。這個(gè)時(shí)候合溺，我們只需要再遍歷 2 個(gè)結(jié)點(diǎn)卒密，就可以找到值等于 16 的這個(gè)結(jié)點(diǎn)了。這樣棠赛，原來(lái)如果要查找 16哮奇，需要遍歷 10 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 7 個(gè)結(jié)點(diǎn)睛约。
從這個(gè)例子里鼎俘，我們看出，加來(lái)一層索引之后辩涝，查找一個(gè)結(jié)點(diǎn)需要遍歷的結(jié)點(diǎn)個(gè)數(shù)減少了贸伐，也就是說(shuō)查找效率提高了。那如果我們?cè)偌右患?jí)索引呢怔揩？效率會(huì)不會(huì)提升更多呢捉邢？
跟前面建立第一級(jí)索引的方式相似，我們?cè)诘谝患?jí)索引的基礎(chǔ)之上商膊，每?jī)蓚€(gè)結(jié)點(diǎn)就抽出一個(gè)結(jié)點(diǎn)到第二級(jí)索引》ィ現(xiàn)在我們?cè)賮?lái)查找 16，只需要遍歷 6 個(gè)結(jié)點(diǎn)了晕拆，需要遍歷的結(jié)點(diǎn)數(shù)量又減少了藐翎。
了讓你能真切地感受索引提升查詢效率。我畫(huà)了一個(gè)包含 64 個(gè)結(jié)點(diǎn)的鏈表实幕，按照前面講的這種思路吝镣，建立了五級(jí)索引。
從圖中我們可以看出昆庇，原來(lái)沒(méi)有索引的時(shí)候末贾，查找 62 需要遍歷 62 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 11 個(gè)結(jié)點(diǎn)凰锡，速度是不是提高了很多未舟？所以圈暗，當(dāng)鏈表的長(zhǎng)度 n 比較大時(shí)，比如 1000裕膀、10000 的時(shí)候员串，在構(gòu)建索引之后，查找效率的提升就會(huì)非常明顯昼扛。
這種鏈表加多級(jí)索引的結(jié)構(gòu)寸齐，就是跳表。我通過(guò)例子給你展示了跳表是如何減少查詢次數(shù)的抄谐，現(xiàn)在你應(yīng)該比較清晰地知道渺鹦，跳表確實(shí)是可以提高查詢效率的。接下來(lái)蛹含，我會(huì)定量地分析一下毅厚，用跳表查詢到底有多快。
2 用跳表查詢到底有多快浦箱？
前面我講過(guò)吸耿，算法的執(zhí)行效率可以通過(guò)時(shí)間復(fù)雜度來(lái)度量，這里依舊可以用酷窥。我們知道咽安，在一個(gè)單鏈表中查詢某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是 O(n)。那在一個(gè)具有多級(jí)索引的跳表中蓬推，查詢某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢妆棒？
這個(gè)時(shí)間復(fù)雜度的分析方法比較難想到。我把問(wèn)題分解一下沸伏，先來(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玛瘸，依次類推蜕青，也就是說(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è)谔碇胁樵兡硞€(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷 m 個(gè)結(jié)點(diǎn)染苛，那在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(m*logn)鹊漠。
那這個(gè) m 的值是多少呢？按照前面這種索引結(jié)構(gòu)茶行，我們每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)躯概，也就是說(shuō) m=3，為什么是 3 呢畔师？我來(lái)解釋一下她倘。
假設(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)蹬蚁，依次類推恃泪，每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)。
通過(guò)上面的分析犀斋，我們得到 m=3贝乎，所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度就是 O(logn)。這個(gè)查找的時(shí)間復(fù)雜度跟二分查找是一樣的叽粹。換句話說(shuō)览效，我們其實(shí)是基于單鏈表實(shí)現(xiàn)了二分查找，是不是很神奇虫几？不過(guò)锤灿，天下沒(méi)有免費(fèi)的午餐，這種查詢效率的提升辆脸，前提是建立了很多級(jí)索引
3 跳表是不是很浪費(fèi)內(nèi)存但校？
比起單純的單鏈表，跳表需要存儲(chǔ)多級(jí)索引啡氢，肯定要消耗更多的存儲(chǔ)空間状囱。那到底需要消耗多少額外的存儲(chǔ)空間呢术裸？我們來(lái)分析一下跳表的空間復(fù)雜度。
跳表的空間復(fù)雜度分析并不難亭枷，我在前面說(shuō)了袭艺，假設(shè)原始鏈表大小為 n，那第一級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)奶栖，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)匹表，以此類推，每上升一級(jí)就減少一半宣鄙，直到剩下 2 個(gè)結(jié)點(diǎn)袍镀。如果我們把每層索引的結(jié)點(diǎn)數(shù)寫出來(lái)，就是一個(gè)等比數(shù)列冻晤。
這幾級(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)了呢？我畫(huà)了一個(gè)每三個(gè)結(jié)點(diǎn)抽一個(gè)的示意圖笨篷，你可以看下瞳秽。
從圖中可以看出，第一級(jí)索引需要大約 n/3 個(gè)結(jié)點(diǎn)率翅，第二級(jí)索引需要大約 n/9 個(gè)結(jié)點(diǎn)练俐。每往上一級(jí)，索引結(jié)點(diǎn)個(gè)數(shù)都除以 3冕臭。為了方便計(jì)算腺晾，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)是 1。我們把每級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)都寫下來(lái)辜贵，也是一個(gè)等比數(shù)列丘喻。
通過(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ā)中，我們不必太在意索引占用的額外空間窟感。在講數(shù)據(jù)結(jié)構(gòu)和算法時(shí)讨彼，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實(shí)際的軟件開(kāi)發(fā)中柿祈，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象哈误，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象躏嚎，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)蜜自，那索引占用的額外空間就可以忽略了。
4 高效的動(dòng)態(tài)插入和刪除
跳表長(zhǎng)什么樣子我想你應(yīng)該已經(jīng)很清楚了卢佣，它的查找操作我們剛才也講過(guò)了重荠。實(shí)際上，跳表這個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)虚茶，不僅支持查找操作戈鲁，還支持動(dòng)態(tài)的插入、刪除操作嘹叫，而且插入婆殿、刪除操作的時(shí)間復(fù)雜度也是 O(logn)
我們現(xiàn)在來(lái)看下， 如何在跳表中插入一個(gè)數(shù)據(jù)罩扇，以及它是如何做到 O(logn) 的時(shí)間復(fù)雜度的婆芦？
我們知道，在單鏈表中暮蹂，一旦定位好要插入的位置寞缝，插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是很低的，就是 O(1)仰泻。但是荆陆，這里為了保證原始鏈表中數(shù)據(jù)的有序性，我們需要先找到要插入的位置集侯，這個(gè)查找操作就會(huì)比較耗時(shí)被啼。
對(duì)于純粹的單鏈表，需要遍歷每個(gè)結(jié)點(diǎn)棠枉，來(lái)找到插入的位置浓体。但是，對(duì)于跳表來(lái)說(shuō)辈讶，我們講過(guò)查找某個(gè)結(jié)點(diǎn)的的時(shí)間復(fù)雜度是 O(logn)命浴，所以這里查找某個(gè)數(shù)據(jù)應(yīng)該插入的位置，方法也是類似的，時(shí)間復(fù)雜度也是 O(logn)生闲。我畫(huà)了一張圖媳溺，你可以很清晰地看到插入的過(guò)程
如果這個(gè)結(jié)點(diǎn)在索引中也有出現(xiàn)，我們除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)碍讯，還要?jiǎng)h除索引中的悬蔽。因?yàn)閱捂湵碇械膭h除操作需要拿到要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后通過(guò)指針操作完成刪除捉兴。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候蝎困，一定要獲取前驅(qū)結(jié)點(diǎn)。當(dāng)然倍啥，如果我們用的是雙向鏈表禾乘，就不需要考慮這個(gè)問(wèn)題了。
5 跳表索引動(dòng)態(tài)更新
當(dāng)我們不停地往跳表中插入數(shù)據(jù)時(shí)逗栽，如果我們不更新索引盖袭，就有可能出現(xiàn)某 2 個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況。極端情況下彼宠，跳表還會(huì)退化成單鏈表鳄虱。
作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡凭峡，也就是說(shuō)拙已，如果鏈表中結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些摧冀，避免復(fù)雜度退化倍踪，以及查找、插入索昂、刪除操作性能下降建车。
跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)前面提到的“平衡性”。
當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候椒惨，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中缤至。如何選擇加入哪些索引層呢？
我們通過(guò)一個(gè)隨機(jī)函數(shù)康谆，來(lái)決定將這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引中领斥，比如隨機(jī)函數(shù)生成了值 K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第 K 級(jí)這 K 級(jí)索引中沃暗。
隨機(jī)函數(shù)的選擇很有講究月洛，從概率上來(lái)講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性孽锥，不至于性能過(guò)度退化嚼黔。
