Redis的跳躍表是什么

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

 前言

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

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

Array 的時(shí)間復(fù)雜度

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

跳表 Skip List

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

鏈表元素有序的時(shí)候

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

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

跳表的特點(diǎn)

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

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

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

它的最大優(yōu)勢(shì)是原理簡(jiǎn)單、容易實(shí)現(xiàn)、方便擴(kuò)展、效率更高。因此在一些熱門(mén)的項(xiàng)目里用來(lái)替代平衡樹(shù)，如 Redis、LevelDB等。

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

如何給有序的鏈表加速

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

我們可以思考一些，如果你來(lái)比如說(shuō)我要很快地查到 7 ，有沒(méi)有在鏈表中存在和它的位置在哪兒的話，你能夠非常快的查詢出來(lái)嗎?

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

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

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

添加第一級(jí)索引

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

具體我們來(lái)看上圖，在原始鏈表的情況下，我們?cè)僭黾右粋€(gè)維度，也就是在上面再增加一層索引，我們叫做第一級(jí)索引，那么第一級(jí)索引的話就不是指向它元素的 next  元素了，而是指向它的 next next ，也就是說(shuō)你可以理解為 next + 1  就行了，所以第一級(jí)索引的話就是第一個(gè)元素，馬上第三個(gè)元素、第五個(gè)元素、第七個(gè)元素。

• 這里你就會(huì)發(fā)現(xiàn)如果你要找7的話，我們?cè)趺崔k?我們這么查找，先查找第一級(jí)索引看有沒(méi)有1 4 7 ，如果有那就說(shuō)明 7  存在這個(gè)鏈表里面是存在的，說(shuō)明我們查詢到了。

• 我們?cè)倏匆榱硪粋€(gè)元素，比如說(shuō) 8，我們?cè)趺醋?還是先找第一級(jí)，8是大于 1 的，所以后繼往后到達(dá) 4 索引的值，8 是大于 4的，繼續(xù)往后到了7，8  也大于7的，再繼續(xù)往后發(fā)現(xiàn) 9 大于 8 了。說(shuō)明 8 是存在于 7 和 9  這兩個(gè)索引之間的元素里面的，那么這個(gè)時(shí)候從第一級(jí)元素向下走到原始的鏈表了，從對(duì)應(yīng)的位置挨個(gè)找就會(huì)發(fā)現(xiàn) 8 找到了，說(shuō)明 8 也是存在的。

添加第二級(jí)索引

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

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

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

添加多級(jí)索引

以此類推，增加多級(jí)索引

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

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

跳表的時(shí)間復(fù)雜度計(jì)算

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

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

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

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

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

在現(xiàn)實(shí)中我們?cè)谟锰淼那闆r下，它會(huì)由于這個(gè)元素的增加和刪除而導(dǎo)致的它的索引的話，有些數(shù)它并不是完全非常工整的，最后經(jīng)過(guò)多次改動(dòng)后，它最后索引有些地方會(huì)跨幾步，有些地方會(huì)少只跨兩步，這是因?yàn)槔锩娴囊恍┰貢?huì)被增加和刪除了，而且它的維護(hù)成本相對(duì)較高，也是說(shuō)當(dāng)你增加一個(gè)元素，你會(huì)把它的索引要更新一遍，你要?jiǎng)h除一個(gè)元素，也需要把它的索引更新一遍。在這種過(guò)程中它在增加和刪除的話，它的時(shí)間復(fù)雜度就會(huì)變成  O(logn) 了。

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

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

在這里的話，我們假設(shè)它的長(zhǎng)度為 n，然后按照之前的例子，每?jī)蓚€(gè)節(jié)點(diǎn)抽一個(gè)做成一個(gè)索引的話，那么它的一級(jí)索引為二分之 n 對(duì)吧。最后如下：

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

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

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

跳躍表的構(gòu)成

以下是個(gè)典型的跳躍表例子：

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

• 表頭(head)：負(fù)責(zé)維護(hù)跳躍表的節(jié)點(diǎn)指針。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 成員對(duì)象(obj)：各個(gè)節(jié)點(diǎn)中的 o1 、 o2 和 o3 是節(jié)點(diǎn)所保存的成員對(duì)象。

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

跳躍表節(jié)點(diǎn)

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

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

層

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

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

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

前進(jìn)指針

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

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

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

2. 迭代程序首先訪問(wèn)跳躍表的第一個(gè)節(jié)點(diǎn)(表頭)， 然后從第四層的前進(jìn)指針移動(dòng)到表中的第二個(gè)節(jié)點(diǎn)。

3. 在第二個(gè)節(jié)點(diǎn)時(shí)， 程序沿著第二層的前進(jìn)指針移動(dòng)到表中的第三個(gè)節(jié)點(diǎn)。

4. 在第三個(gè)節(jié)點(diǎn)時(shí)， 程序同樣沿著第二層的前進(jìn)指針移動(dòng)到表中的第四個(gè)節(jié)點(diǎn)。

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

跨度

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

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

• 指向 NULL 的所有前進(jìn)指針的跨度都為 0 ， 因?yàn)樗鼈儧](méi)有連向任何節(jié)點(diǎn)。

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

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

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

后退指針

節(jié)點(diǎn)的后退指針(backward 屬性)用于從表尾向表頭方向訪問(wèn)節(jié)點(diǎn)： 跟可以一次跳過(guò)多個(gè)節(jié)點(diǎn)的前進(jìn)指針不同， 因?yàn)槊總€(gè)節(jié)點(diǎn)只有一個(gè)后退指針，  所以每次只能后退至前一個(gè)節(jié)點(diǎn)。

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

分值和成員

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

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

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

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

跳躍表

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

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

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

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

• header 和 tail 指針?lè)謩e指向跳躍表的表頭和表尾節(jié)點(diǎn)， 通過(guò)這兩個(gè)指針， 程序定位表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 。

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

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

跳躍表API

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

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

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

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

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

總結(jié)

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

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

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

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

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

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