改造之后的數(shù)據(jù)結(jié)構(gòu)叫做跳表，支持類似”二分“的查找算法。
怎么提高鏈表查找效率？
正常鏈表的查詢，因為要從頭開始遍歷，所以時間復(fù)雜度是O(n)。
試想一下給鏈表建立一個索引，我們先按照每2個節(jié)點提取1個節(jié)點，那么就可
以建立這樣的節(jié)點索引
如果我們要查找某個節(jié)點，比如8，我們可以現(xiàn)在第一層索引遍歷，找到8所在的區(qū)間節(jié)點，8比節(jié)點7大，比9節(jié)點小，那么從7的down指針找到原鏈表這一層，繼續(xù)往后遍歷就找到8所在的節(jié)點位置了。這樣，原來如果查找8需要遍歷8個節(jié)點，現(xiàn)在只需要遍歷5個節(jié)點。
我們還可以在第一層的索引基礎(chǔ)上，繼續(xù)按每兩個節(jié)點抽取一個節(jié)點來建立索引。
跳表查詢有多快？
按每兩個節(jié)點抽一個節(jié)點來算，第一級索引的節(jié)點個數(shù)為：n_2，第二級的節(jié)點個數(shù)為：n/4，以此類推，第k級的節(jié)點個數(shù)為：n_(2^k)。
假設(shè)索引有h級，最高級的索引有2個節(jié)點，則可以得到這樣一個公式：
n/(2^h) = 2
=>
h = log(2)n - 1
如果包含原始鏈這一層，那么h的高度就是log(2)n。
如果每一層都要遍歷m個節(jié)點，那么跳表中查詢一個數(shù)據(jù)的時間復(fù)雜度為O(m*logn)。
那么m的值是多少呢？
按照前面每2個取1一個節(jié)點的規(guī)則，那么m的值應(yīng)為3。當(dāng)遍歷到某個層級的某個節(jié)點x時，除了要和x比較，還要和x的下一級節(jié)點y比較，如果在x和y之間，那么到x的down指向的下一級，根據(jù)之前的規(guī)則，x和y分別對應(yīng)的下一級節(jié)點之間只有一個節(jié)點，所以每一層最多只需要遍歷3個。
所以，在跳表中，查詢一個數(shù)據(jù)的時間復(fù)雜度為O(logn)，和二分查找的時間復(fù)雜度是一樣的。
跳表消耗多少內(nèi)存？
我覺得所有時間復(fù)雜度低的算法，在空間復(fù)雜度上一定是有抵消的。跳表也是如此，它查詢快的原因，是建立在增加了很多層索引的基礎(chǔ)上。每層索引的節(jié)點數(shù)減半，知道減少到2個節(jié)點為止，就是一個等比數(shù)列。
原始鏈表大小為n，每2個節(jié)點抽1個節(jié)點，每層索引的節(jié)點數(shù)為：
n/2, n/4, n/8, ..., 8, 4, 2
節(jié)點總和就是
n/2+n/4+n/8…+8+4+2 = n-2
也就是說，我們需要額外增加n個節(jié)點的空間。
關(guān)于跳表的插入和刪除
關(guān)于插入操作和鏈表是一樣的，都是O(1)的時間復(fù)雜度，區(qū)別在于定位的查找上，跳表在查找上是O(logn)的時間復(fù)雜度，而鏈表是O(n)。
關(guān)于刪除，跳表不光要刪除原鏈表中的，還需要刪除索引中的。
跳表索引動態(tài)更新
如果我們不停的往跳表中插入數(shù)據(jù)，不更新索引，就又可能出現(xiàn)某2個節(jié)點間數(shù)據(jù)非常多的情況下，極端情況下，還會退化成單鏈表。
所以需要某種手段來維護索引與原始鏈表大小間的平衡，如果鏈表中節(jié)點多了，索引節(jié)點就相應(yīng)增加。
和紅黑樹、AVL樹這樣的平衡二叉樹，通過左右旋的方式保持左右子樹的大小平衡不同，跳表是通過隨機函數(shù)來維護前面提到的”平衡性“。
當(dāng)我們往跳表中插入數(shù)據(jù)的時候，通過一個隨機函數(shù)，來決定將這個節(jié)點插入到哪幾級索引中，比如隨機函數(shù)生成了值K，就將這個節(jié)點添加到第1級到第k級的索引中。
這里的隨機函數(shù)選擇，以后再研究。。。
Redis為什么要用跳表來實現(xiàn)有序集合，而不是紅黑樹
Redis中的有序集合支持的核心操作主要有下面這幾個：
- 插入一個數(shù)據(jù)
- 刪除一個數(shù)據(jù)
- 查找一個數(shù)據(jù)
- 按照區(qū)間查找數(shù)據(jù)
- 迭代輸出有序序列
其中插入、刪除、查找以及迭代輸出有序序列紅黑樹也可以完成，效率是一樣的，但是按照區(qū)間查找這個操作，跳表可以做到O(logn)的時間復(fù)雜度定位區(qū)間的起點，然后在原始鏈表中順序往后遍歷就可以了，非常高效。
而且，跳表更容易代碼實現(xiàn)，相比紅黑樹來說更易懂，跳表更加靈活，可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。
