Redis的跳躍表是什么

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

 前言

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

Linked List 的時間復雜度

Array 的時間復雜度

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

跳表 Skip List

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

鏈表元素有序的時候

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

一個有序的數組里面存在，那么問題來了，如果是有序的，但是是鏈表的情況下應該怎樣有效地加速呢?于是在近代1990年前后，一種新的數據結構出現了，它的名字叫做  跳表。

跳表的特點

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

所以，跳表(skip list)對表的是平衡樹(AVL Tree)和 二分查找，是一種 插入/刪除/搜索 都是 O(logn) 的數據結構。1989  年出現。

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

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

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

如何給有序的鏈表加速

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

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

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

• 簡單優化：添加頭尾指針

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

添加第一級索引

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

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

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

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

添加第二級索引

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

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

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

添加多級索引

以此類推，增加多級索引

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

跳表查詢的時間復雜度分析

跳表的時間復雜度計算

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

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

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

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

現實中跳表的形態

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

在跳表中查詢任意數據的時平均時間復雜度就是 O(logn)。

跳表查詢的空間復雜度分析

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

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

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

• 空間復雜度是 O(n)

跳躍表的構成

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

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

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

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

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

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

Redis 跳躍表的實現

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

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

• header ：指向跳躍表的表頭節點。

• tail ：指向跳躍表的表尾節點。

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

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

位于 zskiplist 結構右方的是四個 zskiplistNode 結構， 該結構包含以下屬性：

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

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

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

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

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

跳躍表節點

跳躍表節點的實現由 redis.h/zskiplistNode 結構定義：

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

層

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

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

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

前進指針

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

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

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

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

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

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

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

跨度

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

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

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

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

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

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

后退指針

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

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

分值和成員

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

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

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

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

跳躍表

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

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

zskiplist 結構的定義如下：

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

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

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

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

跳躍表API

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

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

skiplist的復雜度和紅黑樹一樣，而且實現起來更簡單。

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

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

總結

• 跳躍表是有序集合的底層實現之一， 除此之外它在 Redis 中沒有其他應用。

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

• 每個跳躍表節點的層高都是 1 至 32 之間的隨機數。

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

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

到此，相信大家對“Redis的跳躍表是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！