更多數(shù)據(jù)結(jié)構(gòu)內(nèi)容，請參考：數(shù)據(jù)結(jié)構(gòu) - 概要
簡介
疑問中理解技術(shù)
跳表產(chǎn)生的背景
任何技術(shù)，都是為了解決特定問題而出現(xiàn)的。
跳表要解決的就是list這種數(shù)據(jù)結(jié)構(gòu)查詢速度過慢的問題。
與list常做對比的數(shù)據(jù)結(jié)構(gòu)是數(shù)組。數(shù)組中元素的查找可以使用二分查找，可以使查找降低到O(logN)的時間復(fù)雜度度
但是對于list來講，查找只能從頭或尾部一個個遍歷，時間復(fù)雜度是O(n)的。
二分查找的效率高，是因?yàn)槊看螌Ρ群螅寄芘懦话氲臄?shù)據(jù)，使要搜索的元素集合大大減少。這類似于一種索引技術(shù)，而數(shù)組下標(biāo)就是索引。
對于list來講，可以通過額外存儲一些數(shù)據(jù)，當(dāng)做list的索引：即在原來list的基礎(chǔ)上，再存儲些數(shù)據(jù)，這些數(shù)據(jù)也都是用list存儲的。通過逐層對比這些數(shù)據(jù)，實(shí)現(xiàn)縮小搜索范圍的目的。這個在Redis 為什么用跳表而不用平衡樹？中講的比較清楚。
但是跳表并沒有實(shí)現(xiàn)嚴(yán)格的二分。要實(shí)現(xiàn)嚴(yán)格的二分要調(diào)整已經(jīng)存儲的數(shù)據(jù)，會增加工作量。
跳表選擇了一種變通做法，通過隨機(jī)函數(shù)，決定新插入元素的層高。這種實(shí)現(xiàn)雖然不能保證查詢效率是嚴(yán)格的O(logN)，但是平均值和絕大多數(shù)情況下，都能達(dá)到O(logN)的效率。
這是一種折中，但折中折中在沒有降低太多查詢性能的情況下，大大提升了插入效率。這個想法跟紅黑樹的實(shí)現(xiàn)有相似之處。 數(shù)據(jù)結(jié)構(gòu) - 紅黑樹
跳表與平衡樹的比較
跳表會經(jīng)常被用來跟平衡樹，尤其是紅黑樹來比較。
這是因?yàn)樘砗图t黑樹能做的事幾乎相同。
- 跳表實(shí)現(xiàn)比紅黑樹簡單太多了
- 跳表的存儲空間比紅黑樹大，但也大不了多少
- 查詢效率而言，紅黑樹更穩(wěn)定，但絕大多數(shù)情況下區(qū)別不大。
- 跳表數(shù)據(jù)存放是緊湊的，也就是順序遞增的數(shù)據(jù)是挨著的，這樣就非常適合范圍查找。紅黑樹的范圍查找就不怎么樣了
像redis中sorted set數(shù)據(jù)結(jié)構(gòu)是用跳表來實(shí)現(xiàn)的。而JDK中的TreeMap使用紅黑樹來實(shí)現(xiàn)的。
只能說跳表和紅黑樹各有千秋。個人在選擇其中一個實(shí)現(xiàn)時，需要結(jié)合自己的實(shí)際情況，如能力、時間和需求等。
為啥 redis 使用跳表(skiplist)而不是使用 red-black？ 文中討論了redis為何使用的是跳表而非紅黑樹。里面一個共識就是，跳表實(shí)現(xiàn)起來比紅黑樹簡單太多了(redis作者也把這個列為了一個因素)，又能滿足需求。
