????????最近在網(wǎng)上閑逛，無意中看見了“跳躍表”，記得之前了解redis的時(shí)候，依稀的記得redis中視乎也是提到了跳躍表；出于好奇，對(duì)跳躍表做了更多的學(xué)習(xí)。

? ? ? ? 什么是跳躍表呢？這是一種只可意會(huì)，不可言傳的的神秘?cái)?shù)據(jù)結(jié)構(gòu)，下面讓我們來看一下這種神奇的數(shù)據(jù)結(jié)構(gòu)；

? ? ? ? 我們都知道，在數(shù)據(jù)結(jié)構(gòu)中有一種叫做鏈表的結(jié)構(gòu)，他的優(yōu)點(diǎn)是的插入高效方便，我們可以在已有的鏈表的任何位置插入表一個(gè)新的節(jié)點(diǎn)；但是他也存在一個(gè)致命的缺點(diǎn)，就是查找效率非常的低，當(dāng)我們要查找某個(gè)節(jié)點(diǎn)的時(shí)候，我們需要從鏈表的表頭開始，依次遍歷訪問每一個(gè)節(jié)點(diǎn)，運(yùn)氣好的話，我們會(huì)在鏈表的表頭查找到節(jié)點(diǎn)，如果運(yùn)氣差的話，那我們就得訪問完整個(gè)鏈表；鏈表的查找的時(shí)間復(fù)雜度為O(n)；

? ? ? ?有人會(huì)問， 如果我們現(xiàn)在將數(shù)據(jù)存在一個(gè)有序的鏈表中，那查找的效率是會(huì)提高嗎？一看你就是上數(shù)據(jù)結(jié)構(gòu)的課的時(shí)候看妹子去了，鏈表一般都是由指針串聯(lián)起來的，盡管我們知道該鏈表有序，但是我們還是不能快速的定位到需要查找的數(shù)據(jù)的位置，只能一個(gè)一個(gè)的遍歷訪問，所以其時(shí)間復(fù)雜度還是O(n);

? ? 有人會(huì)說，我們說的是跳躍表，和鏈表有什么關(guān)系呢？和有序鏈表由有什么關(guān)系呢？

? ? 其實(shí)跳躍表就是在有序鏈表的基礎(chǔ)上實(shí)現(xiàn)的，剛才講了，有序鏈表只能一個(gè)一個(gè)的訪問節(jié)點(diǎn)，盡管他是有序的，也只能這么干；如果我們給有序鏈表加上索引，查找起來會(huì)不會(huì)快一點(diǎn)？答案是肯定的，但是這個(gè)索引怎么加呢？如果加索引耗費(fèi)的內(nèi)存比較多，那我們還不如換一種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)；所以人們就想到了跳躍表的數(shù)據(jù)結(jié)構(gòu)；綜上所述：跳躍表是在有序列的基礎(chǔ)上，增加了索引，以達(dá)到快速查找的目的；具體如圖示：

? ? ????當(dāng)我們對(duì)有序鏈表進(jìn)行操作的時(shí)候，首先需要找到操作的數(shù)據(jù)的對(duì)應(yīng)位置，接下來在做相關(guān)的操作，下面我們看一下對(duì)跳躍表，我們?cè)撛趺醋觥?/p>

? ? 從上圖，我們可以知道，最下面一層的數(shù)據(jù)量最多，也就是整個(gè)鏈表的完整的數(shù)據(jù)，而越往上，數(shù)據(jù)量越少，為了提高查找效率，我們從最上層網(wǎng)下依次逐層查找，用待處理數(shù)據(jù)與，對(duì)應(yīng)層上的數(shù)據(jù)進(jìn)行比較，當(dāng)待處理數(shù)據(jù)比跳躍表改層的數(shù)據(jù)小的時(shí)候，就到下一層接著查找。依次類推，可以找到需要操作的數(shù)據(jù)。