一、課前思考

兩節(jié)我們講了二分查找算法。當(dāng)時我講到，因為二分查找底層依賴的是數(shù)組隨機(jī)訪問的特性，所以只能用數(shù)組來實現(xiàn)。如果數(shù)據(jù)存儲在鏈表中，就真的沒法用二分查找算法了嗎？

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

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

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

二、如何理解跳表

1、單鏈表

2、怎么提高查詢效率

1、18個節(jié)點一級索引

2、18個節(jié)點二級索引

3、64個節(jié)點建立五級索引

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

三、用跳表查詢到底有多快

1、如果鏈表?有n個結(jié)點，會有多少級索引？

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

3、M值為什么是3

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

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

1、索引節(jié)點數(shù)是一個等比數(shù)列

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

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

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

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

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

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

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

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

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

七、解答開篇

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

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

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

3、迭代輸出有序序列。

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

3、跳表也不能完全替代紅?樹

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

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

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

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

九、課后思考

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

經(jīng)典留言escray

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

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

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

?