一、課前思考

兩節(jié)我們講了二分查找算法。當(dāng)時(shí)我講到，因?yàn)槎植檎业讓右蕾?lài)的是數(shù)組隨機(jī)訪(fǎng)問(wèn)的特性，所以只能用數(shù)組來(lái)實(shí)現(xiàn)。如果數(shù)據(jù)存儲(chǔ)在鏈表中，就真的沒(méi)法用二分查找算法了嗎？

實(shí)際上，我們只需要對(duì)鏈表稍加改造，就可以支持類(lèi)似“二分”的查找算法。我們把改造之后的數(shù)據(jù)結(jié)構(gòu)叫作跳表（Skiplist），也就是今天要講的內(nèi)容。

跳表這種數(shù)據(jù)結(jié)構(gòu)對(duì)你來(lái)說(shuō)，可能會(huì)比較陌生，因?yàn)橐话愕臄?shù)據(jù)結(jié)構(gòu)和算法書(shū)籍里都不怎么會(huì)講。但是它確實(shí)是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以支持快速的插入、刪除、查找操作，
寫(xiě)起來(lái)也不復(fù)雜，甚至可以替代紅黑樹(shù)（Red-blacktree）。

Redis中的有序集合（Sorted Set）就是?跳表來(lái)實(shí)現(xiàn)的。如果你有一定基礎(chǔ)，應(yīng)該知道紅黑樹(shù)也可以實(shí)現(xiàn)快速的插入、刪除和查找操作。那Redis為什么會(huì)選擇用跳表來(lái)實(shí)現(xiàn)有序集合呢？
?為什么不用紅黑樹(shù)呢？學(xué)完今天的內(nèi)容，你就知道答案了。

二、如何理解跳表

1、單鏈表

2、怎么提高查詢(xún)效率

1、18個(gè)節(jié)點(diǎn)一級(jí)索引

2、18個(gè)節(jié)點(diǎn)二級(jí)索引

3、64個(gè)節(jié)點(diǎn)建立五級(jí)索引

3、當(dāng)鏈表的?度n?較?時(shí)

三、用跳表查詢(xún)到底有多快

1、如果鏈表?有n個(gè)結(jié)點(diǎn)，會(huì)有多少級(jí)索引？

2、復(fù)雜度推算過(guò)程

3、M值為什么是3

4、基于單鏈表實(shí)現(xiàn)二分查找

四、跳表是不是很浪費(fèi)內(nèi)存

1、索引節(jié)點(diǎn)數(shù)是一個(gè)等比數(shù)列

2、通過(guò)等?數(shù)列求和公式

3、實(shí)際上，在軟件開(kāi)發(fā)中，我們不必太在意索引占?的額外空間

五、高效的動(dòng)態(tài)插入刪除

1、在跳表單鏈表中插??個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度

2、在跳表中刪除?個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度

六、跳表索引動(dòng)態(tài)更新

1、如果鏈表中結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加?些

2、跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)前?提到的“平衡性”

3、如何選擇加?哪些索引層呢？

七、解答開(kāi)篇

1、如果你去查看Redis的開(kāi)發(fā)?冊(cè)，就會(huì)發(fā)現(xiàn)Redis中的有序集合?持的核?操作主要有下?這?個(gè)

1、插??個(gè)數(shù)據(jù)；刪除?個(gè)數(shù)據(jù)；查找?個(gè)數(shù)據(jù)；

2、按照區(qū)間查找數(shù)據(jù)（?如查找值在[100, 356]之間的數(shù)據(jù)

3、迭代輸出有序序列。

2、Redis之所以?跳表來(lái)實(shí)現(xiàn)有序集合，還有其他原因

3、跳表也不能完全替代紅?樹(shù)

跳表的實(shí)現(xiàn)還是稍微有點(diǎn)復(fù)雜的，我將Java實(shí)現(xiàn)的代碼放到了GitHub中，你可以根據(jù)我剛剛的講解，對(duì)照著代碼仔細(xì)思考?下。你不?死記硬背代碼，跳表的實(shí)現(xiàn)并不是我們這節(jié)的重點(diǎn)

八、內(nèi)容小結(jié)

今天我們講了跳表這種數(shù)據(jù)結(jié)構(gòu)。跳表使用空間換時(shí)間的設(shè)計(jì)思路，通過(guò)構(gòu)建多級(jí)索引來(lái)提高查詢(xún)的效率，實(shí)現(xiàn)了基于鏈表的“二分查找”。跳表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，支持快速的插入、刪除、查找操作，時(shí)間復(fù)雜度都是O(logn)。

跳表的空間復(fù)雜度是O(n)。不過(guò)，跳表的實(shí)現(xiàn)非常靈活，可以通過(guò)改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。雖然跳表的代碼實(shí)現(xiàn)并不簡(jiǎn)單，但是作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，比起紅黑樹(shù)來(lái)說(shuō)，
實(shí)現(xiàn)要簡(jiǎn)單多了。所以很多時(shí)候，我們?yōu)榱舜a的簡(jiǎn)單、易讀，比起紅黑樹(shù)，我們更傾向用跳表。

九、課后思考

在今天的內(nèi)容中，對(duì)于跳表的時(shí)間復(fù)雜度分析，我分析了每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)作為索引的時(shí)間復(fù)雜度。如果每三個(gè)或者五個(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)作為上級(jí)索引，
對(duì)應(yīng)的在跳表中查詢(xún)數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢

經(jīng)典留言escray

如果每三個(gè)或者五個(gè)節(jié)點(diǎn)提取一個(gè)節(jié)點(diǎn)作為上級(jí)索引，那么對(duì)應(yīng)的查詢(xún)數(shù)據(jù)時(shí)間復(fù)雜度，應(yīng)該也還是 O(logn)。

假設(shè)每 5 個(gè)節(jié)點(diǎn)提取，那么最高一層有 5 個(gè)節(jié)點(diǎn)，而跳表高度為 log5n，每層最多需要查找 5 個(gè)節(jié)點(diǎn)，即 O(mlogn) 中的 m = 5，最終，時(shí)間復(fù)雜度為 O(logn)。
空間復(fù)雜度也還是 O(logn)，雖然省去了一部分索引節(jié)點(diǎn)，但是似乎意義不大。

不知道在一般的生產(chǎn)系統(tǒng)，跳表的提取是按照多少個(gè)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)？還是每個(gè)系統(tǒng)根據(jù)實(shí)際情況，都不一樣。
看了跳表的 Java 實(shí)現(xiàn)，查找部分的代碼真是漂亮，插入部分看了半天才看明白。

?