本篇內(nèi)容主要講解“redis的跳躍表是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“Redis的跳躍表是什么”吧!

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、小程序設(shè)計、集團企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了西鄉(xiāng)塘免費建站歡迎大家使用！

 前言

在這里我們先回憶一下普通鏈表的時間復(fù)雜度，可以看到除了 look up 操作是 O(n) 的，其他操作都是 O(1)  的時間復(fù)雜度。也就是說你需要隨機訪問里面的任何一個元素的話，它的時間復(fù)雜度平均值是 O(n)  的，這也就是鏈表它的問題所在。從這里可以看到并沒有所謂完美的一種數(shù)據(jù)結(jié)構(gòu)，如果完美那就不需要 Array 或者 LInked List  這兩個數(shù)據(jù)結(jié)構(gòu)并存了，就直接使用最牛逼的數(shù)據(jù)結(jié)構(gòu)即可。所以相當(dāng)于各有優(yōu)劣，看你的使用場景在什么地方，作為完整性比較，我這里把兩種時間復(fù)雜度都列出來。

Linked List 的時間復(fù)雜度

Array 的時間復(fù)雜度

注意：正常情況下數(shù)組的 prepend 操作的時間復(fù)雜度是 O(n) ，但是可以進行特殊優(yōu)化到  O(1)。采用的方式是申請稍微大一些的內(nèi)存空間，然后在數(shù)組開始預(yù)留一部分空間，然后 prepend 的操作則是把頭下標(biāo)前移一個位置即可。

跳表 Skip List

前面回顧了 Array 和 Linked List 的兩種結(jié)構(gòu)的時間復(fù)雜度，有一種情況下鏈表它的速度在 O(n)  這一塊，就會覺得不太夠用，我們來看一下這種情況指的是什么?

鏈表元素有序的時候

注意是指整個元素，如果是有序的話，在有些時候，比如在數(shù)據(jù)庫里面也好，或者是在其他對一些有序的樹進行查詢的時候，即使用鏈表這種方式存儲的話，我們發(fā)現(xiàn)它的元素是有序的，比如說下面這個升序鏈表，134578910  它是升序排列的，這個時候我們要快速地查詢，比如 9 在什么地方或者查詢  5，是不是在這個鏈表里面出現(xiàn)，這時候你會發(fā)現(xiàn)，如果是用普通的數(shù)組可以進行二分查找可以很快查到5所在的位置，以及查詢到一個元素是否存在。

一個有序的數(shù)組里面存在，那么問題來了，如果是有序的，但是是鏈表的情況下應(yīng)該怎樣有效地加速呢?于是在近代1990年前后，一種新的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)了，它的名字叫做  跳表。

跳表的特點

注意：只能用于元素有序的情況。

所以，跳表(skip list)對表的是平衡樹(AVL Tree)和 二分查找，是一種 插入/刪除/搜索 都是 O(logn) 的數(shù)據(jù)結(jié)構(gòu)。1989  年出現(xiàn)。

• 不管是平衡樹、二叉搜索樹其他哪些樹的話都是在1960年和196幾年就已經(jīng)出現(xiàn)了，它的出現(xiàn)比平衡樹和二分查找以及所謂的一些高級數(shù)據(jù)結(jié)構(gòu)出現(xiàn)的要晚。比其他的晚了接近30年，最后才出現(xiàn)，這就是為什么很多老的數(shù)據(jù)結(jié)構(gòu)的話，用平衡二叉樹會多一點，而一些比較新的，特別是在元素個數(shù)不多的情況的情況下，用的全部都是跳表，也就是說在更新?lián)Q代了。

它的最大優(yōu)勢是原理簡單、容易實現(xiàn)、方便擴展、效率更高。因此在一些熱門的項目里用來替代平衡樹，如 Redis、LevelDB等。

• 跳躍表(skiplist)是一種隨機化的數(shù)據(jù)， 由 William Pugh 在論文《Skip lists: a probabilistic  alternative to balanced trees》中提出， 跳躍表以有序的方式在層次化的鏈表中保存元素， 效率和平衡樹媲美 ——  查找、刪除、添加等操作都可以在對數(shù)期望時間下完成， 并且比起平衡樹來說， 跳躍表的實現(xiàn)要簡單直觀得多。

如何給有序的鏈表加速

假設(shè)有一個有序的鏈表，1 3 4 5 7 8 9 10 這么一個原始的鏈表。它的時間復(fù)雜度查詢肯定是 O(n)  的，那么問一下如何優(yōu)化?如何進行簡單優(yōu)化?可以讓它的查詢時間復(fù)雜度變低，也就是加速它的查詢。

我們可以思考一些，如果你來比如說我要很快地查到 7 ，有沒有在鏈表中存在和它的位置在哪兒的話，你能夠非?？斓牟樵兂鰜韱?

• 時間復(fù)雜度：查詢 O(n)

• 簡單優(yōu)化：添加頭尾指針

上面這么一個結(jié)構(gòu)，它是一維的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在它是有序了，也就是說我們有附加的信息了，那么如何加速對吧?一般來說這種加速的方式的話，就類似于星際穿越里面這有點玄學(xué)，但是你一定要記住一個概念就行了，一維的數(shù)據(jù)結(jié)構(gòu)要加速的話，經(jīng)常采用的方式就是升維也就是說變成二維。為什么要多一層維度，因為你多了一個維度之后，就會有多一級的信息在里面，這樣多一級的信息就可以幫助你可以很快地得到一維里面你必須挨個走才能走到的那些元素

添加第一級索引

如何提高鏈表線性查找的效率?

具體我們來看上圖，在原始鏈表的情況下，我們再增加一個維度，也就是在上面再增加一層索引，我們叫做第一級索引，那么第一級索引的話就不是指向它元素的 next  元素了，而是指向它的 next next ，也就是說你可以理解為 next + 1  就行了，所以第一級索引的話就是第一個元素，馬上第三個元素、第五個元素、第七個元素。

• 這里你就會發(fā)現(xiàn)如果你要找7的話，我們怎么辦?我們這么查找，先查找第一級索引看有沒有1 4 7 ，如果有那就說明 7  存在這個鏈表里面是存在的，說明我們查詢到了。

• 我們再看要查另一個元素，比如說 8，我們怎么走?還是先找第一級，8是大于 1 的，所以后繼往后到達 4 索引的值，8 是大于 4的，繼續(xù)往后到了7，8  也大于7的，再繼續(xù)往后發(fā)現(xiàn) 9 大于 8 了。說明 8 是存在于 7 和 9  這兩個索引之間的元素里面的，那么這個時候從第一級元素向下走到原始的鏈表了，從對應(yīng)的位置挨個找就會發(fā)現(xiàn) 8 找到了，說明 8 也是存在的。

添加第二級索引

那么有的朋友可能就會想了，你加一級索引的話，每次相當(dāng)于步伐加 2  了，但是它的速度的話也就是比原來稍微快了一點，能不能更快呢?對你這個想法是非常有道理的，也是很好的。

那么在一級索引的基礎(chǔ)上，我們可以再加索引就行了，也就是說同理可得，在第一級索引的基礎(chǔ)上，我們把它當(dāng)作是一個原始鏈表一樣，往上再加一級索引，也就是說每次針對第一級索引走兩步。那么它相等于原始鏈表相當(dāng)于每次就走了四步。對不對，就乘于  2，那這樣的話，速度就更加高效了。

• 比如我舉個例子要查8，先找 1，8 比 1要大，再找 7 ，這時候你會發(fā)現(xiàn) 8 也是比 7 大的，再找，假設(shè)這個元素后面的話是 11 或者 12  好了，這時候你會發(fā)現(xiàn) 8 是小于它后面的元素，所以 7 這里的話就必須向下再走一級索引了，走到第一級索引的 7 來，再類似于之前 7 和 9 之間，然后再走到8  這樣一直走下來。

添加多級索引

以此類推，增加多級索引

假設(shè)有五級索引的這么一個原始鏈表，那么我們要查一個元素，比如說要查 62  元素或者中間元素，就類似于下圖，一級一級一級一級走下來，最后的話就可以查到我們需要的62這個元素。當(dāng)然的話你最后查到原始鏈表，你會發(fā)現(xiàn)比如說是我們要查63或者61，原始鏈表里面沒有，我們就說元素不存在，在我們這個有序的鏈表里面，也就是說在跳表里面查不到這么一個元素，最后也可以得出這樣的結(jié)論。

跳表查詢的時間復(fù)雜度分析

跳表的時間復(fù)雜度計算

• n/2、n/4、n/8、第 k 級索引結(jié)點的個數(shù)就是 n/(2^k)

• 假設(shè)索引有 h 級，最高級的索引有 2 個結(jié)點。n/(2^h) = 2，從而求得 h = log2(n)-1

舉一個例子，跳表在查詢的時候，假設(shè)索引的高度：logn，每層索引遍歷的結(jié)點個數(shù)：3，假設(shè)要走到第 8 個節(jié)點。

每層要遍歷的元素總共是3個，所以這里的話 log28  的話，就是它的時間復(fù)雜度。最后的話得出證明出來：時間復(fù)雜度為log2n。也就是從最樸素的原始鏈表的話，它的 O(n) 的時間復(fù)雜度降到 log2n  的時間復(fù)雜度。這已經(jīng)是一個很大的改進了。假設(shè)是1024的話，你會發(fā)現(xiàn)原始鏈表要查1024次最后得到這個元素，那么這里的話就只需要查(2的10次方是1024次)十次這樣一個數(shù)量級。

現(xiàn)實中跳表的形態(tài)

在現(xiàn)實中我們在用跳表的情況下，它會由于這個元素的增加和刪除而導(dǎo)致的它的索引的話，有些數(shù)它并不是完全非常工整的，最后經(jīng)過多次改動后，它最后索引有些地方會跨幾步，有些地方會少只跨兩步，這是因為里面的一些元素會被增加和刪除了，而且它的維護成本相對較高，也是說當(dāng)你增加一個元素，你會把它的索引要更新一遍，你要刪除一個元素，也需要把它的索引更新一遍。在這種過程中它在增加和刪除的話，它的時間復(fù)雜度就會變成  O(logn) 了。

在跳表中查詢?nèi)我鈹?shù)據(jù)的時平均時間復(fù)雜度就是 O(logn)。

跳表查詢的空間復(fù)雜度分析

在這里的話，我們假設(shè)它的長度為 n，然后按照之前的例子，每兩個節(jié)點抽一個做成一個索引的話，那么它的一級索引為二分之 n 對吧。最后如下：

• 原始鏈表大小為 n，每 2 個結(jié)點抽 1 個，每層索引的結(jié)點數(shù): n2,n4,n8...,8,4,2

• 原始鏈表大小為 n，每 3 個結(jié)點抽 1 個，每層索引的結(jié)點數(shù): n3,n9,n27...,9,3,1

• 空間復(fù)雜度是 O(n)

跳躍表的構(gòu)成

以下是個典型的跳躍表例子：

從圖中可以看到， 跳躍表主要由以下部分構(gòu)成：

• 表頭(head)：負責(zé)維護跳躍表的節(jié)點指針。

• 跳躍表節(jié)點：保存著元素值，以及多個層。

• 層：保存著指向其他元素的指針。高層的指針越過的元素數(shù)量大于等于低層的指針，為了提高查找的效率，程序總是從高層先開始訪問，然后隨著元素值范圍的縮小，慢慢降低層次。

• 表尾：全部由 NULL 組成，表示跳躍表的末尾。

Redis 跳躍表的實現(xiàn)

Redis 的跳躍表由 redis.h/zskiplistNode 和 redis.h/zskiplist 兩個結(jié)構(gòu)定義， 其中  zskiplistNode 結(jié)構(gòu)用于表示跳躍表節(jié)點， 而 zskiplist 結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息， 比如節(jié)點的數(shù)量，  以及指向表頭節(jié)點和表尾節(jié)點的指針， 等等。

上圖展示了一個跳躍表示例，位于圖片最左邊的是 zskiplist 結(jié)構(gòu)，該結(jié)構(gòu)包含以下屬性：

• header ：指向跳躍表的表頭節(jié)點。

• tail ：指向跳躍表的表尾節(jié)點。

• level ：記錄目前跳躍表內(nèi)，層數(shù)最大的那個節(jié)點的層數(shù)(表頭節(jié)點的層數(shù)不計算在內(nèi))。

• length ：記錄跳躍表的長度，也即是，跳躍表目前包含節(jié)點的數(shù)量(表頭節(jié)點不計算在內(nèi))。

位于 zskiplist 結(jié)構(gòu)右方的是四個 zskiplistNode 結(jié)構(gòu)， 該結(jié)構(gòu)包含以下屬性：

• 層(level)：節(jié)點中用 L1 、 L2 、 L3 等字樣標(biāo)記節(jié)點的各個層， L1 代表第一層， L2  代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節(jié)點，而跨度則記錄了前進指針?biāo)赶蚬?jié)點和當(dāng)前節(jié)點的距離。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進指針，而那個數(shù)字就是跨度。當(dāng)程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。

• 后退(backward)指針：節(jié)點中用 BW 字樣標(biāo)記節(jié)點的后退指針，它指向位于當(dāng)前節(jié)點的前一個節(jié)點。后退指針在程序從表尾向表頭遍歷時使用。

• 分值(score)：各個節(jié)點中的 1.0 、 2.0 和 3.0 是節(jié)點所保存的分值。在跳躍表中，節(jié)點按各自所保存的分值從小到大排列。

• 成員對象(obj)：各個節(jié)點中的 o1 、 o2 和 o3 是節(jié)點所保存的成員對象。

注意：表頭節(jié)點和其他節(jié)點的構(gòu)造是一樣的： 表頭節(jié)點也有后退指針、分值和成員對象， 不過表頭節(jié)點的這些屬性都不會被用到， 所以圖中省略了這些部分，  只顯示了表頭節(jié)點的各個層。

跳躍表節(jié)點

跳躍表節(jié)點的實現(xiàn)由 redis.h/zskiplistNode 結(jié)構(gòu)定義：

typedef struct zskiplistNode {     // 后退指針     struct zskiplistNode *backward;     // 分值     double score;     // 成員對象     robj *obj;     // 層     struct zskiplistLevel {         // 前進指針         struct zskiplistNode *forward;         // 跨度         unsigned int span;     } level[]; } zskiplistNode;

層

跳躍表節(jié)點的 level  數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點的速度就越快。

每次創(chuàng)建一個新跳躍表節(jié)點的時候， 程序都根據(jù)冪次定律 (power law，越大的數(shù)出現(xiàn)的概率越小) 隨機生成一個介于 1 和 32 之間的值作為  level 數(shù)組的大小， 這個大小就是層的“高度”。

下圖分別展示了三個高度為 1 層、 3 層和 5 層的節(jié)點， 因為 C 語言的數(shù)組索引總是從 0 開始的， 所以節(jié)點的第一層是 level[0] ，  而第二層是 level[1] ， 以此類推。

前進指針

每個層都有一個指向表尾方向的前進指針(level[i].forward 屬性)， 用于從表頭向表尾方向訪問節(jié)點。

上圖用虛線表示出了程序從表頭向表尾方向， 遍歷跳躍表中所有節(jié)點的路徑：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 迭代程序首先訪問跳躍表的第一個節(jié)點(表頭)， 然后從第四層的前進指針移動到表中的第二個節(jié)點。

3. 在第二個節(jié)點時， 程序沿著第二層的前進指針移動到表中的第三個節(jié)點。

4. 在第三個節(jié)點時， 程序同樣沿著第二層的前進指針移動到表中的第四個節(jié)點。

5. 當(dāng)程序再次沿著第四個節(jié)點的前進指針移動時， 它碰到一個 NULL ， 程序知道這時已經(jīng)到達了跳躍表的表尾， 于是結(jié)束這次遍歷。

跨度

層的跨度(level[i].span 屬性)用于記錄兩個節(jié)點之間的距離：

• 兩個節(jié)點之間的跨度越大， 它們相距得就越遠。

• 指向 NULL 的所有前進指針的跨度都為 0 ， 因為它們沒有連向任何節(jié)點。

初看上去， 很容易以為跨度和遍歷操作有關(guān)， 但實際上并不是這樣 —— 遍歷操作只使用前進指針就可以完成了， 跨度實際上是用來計算排位(rank)的：  在查找某個節(jié)點的過程中， 將沿途訪問過的所有層的跨度累計起來， 得到的結(jié)果就是目標(biāo)節(jié)點在跳躍表中的排位。

舉個例子， 如下用虛線標(biāo)記了在跳躍表中查找分值為 3.0 、 成員對象為 o3 的節(jié)點時， 沿途經(jīng)歷的層： 查找的過程只經(jīng)過了一個層， 并且層的跨度為 3  ， 所以目標(biāo)節(jié)點在跳躍表中的排位為 3 。

再舉個例子， 如下用虛線標(biāo)記了在跳躍表中查找分值為 2.0 、 成員對象為 o2 的節(jié)點時， 沿途經(jīng)歷的層： 在查找節(jié)點的過程中， 程序經(jīng)過了兩個跨度為  1 的節(jié)點， 因此可以計算出， 目標(biāo)節(jié)點在跳躍表中的排位為 2 。

后退指針

節(jié)點的后退指針(backward 屬性)用于從表尾向表頭方向訪問節(jié)點： 跟可以一次跳過多個節(jié)點的前進指針不同， 因為每個節(jié)點只有一個后退指針，  所以每次只能后退至前一個節(jié)點。

上圖用虛線展示了如果從表尾向表頭遍歷跳躍表中的所有節(jié)點： 程序首先通過跳躍表的 tail指針訪問表尾節(jié)點， 然后通過后退指針訪問倒數(shù)第二個節(jié)點，  之后再沿著后退指針訪問倒數(shù)第三個節(jié)點， 再之后遇到指向 NULL 的后退指針， 于是訪問結(jié)束。

分值和成員

• 節(jié)點的分值(score 屬性)是一個 double 類型的浮點數(shù)， 跳躍表中的所有節(jié)點都按分值從小到大來排序。

• 節(jié)點的成員對象(obj 屬性)是一個指針， 它指向一個字符串對象， 而字符串對象則保存著一個 SDS(簡單動態(tài)字符串) 值。

在同一個跳躍表中， 各個節(jié)點保存的成員對象必須是唯一的， 但是多個節(jié)點保存的分值卻可以是相同的： 分值相同的節(jié)點將按照成員對象在字典序中的大小來進行排序，  成員對象較小的節(jié)點會排在前面(靠近表頭的方向)， 而成員對象較大的節(jié)點則會排在后面(靠近表尾的方向)。

舉個例子， 在下圖所示的跳躍表中， 三個跳躍表節(jié)點都保存了相同的分值 10086.0 ， 但保存成員對象 o1 的節(jié)點卻排在保存成員對象 o2 和 o3  的節(jié)點之前， 而保存成員對象 o2 的節(jié)點又排在保存成員對象 o3 的節(jié)點之前， 由此可見， o1 、 o2 、 o3 三個成員對象在字典中的排序為 o1  <= o2 <= o3 。

跳躍表

雖然僅靠多個跳躍表節(jié)點就可以組成一個跳躍表， 如下圖 所示：

但通過使用一個 zskiplist 結(jié)構(gòu)來持有這些節(jié)點， 程序可以更方便地對整個跳躍表進行處理， 比如快速訪問跳躍表的表頭節(jié)點和表尾節(jié)點，  又或者快速地獲取跳躍表節(jié)點的數(shù)量(也即是跳躍表的長度)等信息， 如下所示：

zskiplist 結(jié)構(gòu)的定義如下：

typedef struct zskiplist {      // 表頭節(jié)點和表尾節(jié)點     struct zskiplistNode *header, *tail;      // 表中節(jié)點的數(shù)量     unsigned long length;      // 表中層數(shù)最大的節(jié)點的層數(shù)     int level;  } zskiplist;

• header 和 tail 指針分別指向跳躍表的表頭和表尾節(jié)點， 通過這兩個指針， 程序定位表頭節(jié)點和表尾節(jié)點的復(fù)雜度為 O(1) 。

• 通過使用 length 屬性來記錄節(jié)點的數(shù)量， 程序可以在 O(1) 復(fù)雜度內(nèi)返回跳躍表的長度。

• level 屬性則用于在 O(1) 復(fù)雜度內(nèi)獲取跳躍表中層高最大的那個節(jié)點的層數(shù)量， 注意表頭節(jié)點的層高并不計算在內(nèi)。

跳躍表API

列出了跳躍表的所有操作 API 。

面試：為啥 redis 使用跳表(skiplist)而不是使用 red-black?

skiplist的復(fù)雜度和紅黑樹一樣，而且實現(xiàn)起來更簡單。

在并發(fā)環(huán)境下skiplist有另外一個優(yōu)勢，紅黑樹在插入和刪除的時候可能需要做一些rebalance的操作，這樣的操作可能會涉及到整個樹的其他部分，而skiplist的操作顯然更加局部性一些，所需要盯住的節(jié)點更少，因此在這樣的情況下性能好一些。

附：開發(fā)者說的為什么選用skiplist The Skip list

總結(jié)

• 跳躍表是有序集合的底層實現(xiàn)之一， 除此之外它在 Redis 中沒有其他應(yīng)用。

• Redis 的跳躍表實現(xiàn)由 zskiplist 和 zskiplistNode 兩個結(jié)構(gòu)組成， 其中 zskiplist  用于保存跳躍表信息(比如表頭節(jié)點、表尾節(jié)點、長度)， 而 zskiplistNode 則用于表示跳躍表節(jié)點。

• 每個跳躍表節(jié)點的層高都是 1 至 32 之間的隨機數(shù)。

• 在同一個跳躍表中， 多個節(jié)點可以包含相同的分值， 但每個節(jié)點的成員對象必須是唯一的。

• 跳躍表中的節(jié)點按照分值大小進行排序， 當(dāng)分值相同時， 節(jié)點按照成員對象的大小進行排序。

到此，相信大家對“Redis的跳躍表是什么”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！