詳解Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表

1、簡介

我們先不談Redis，來看一下跳表。

1.1、業(yè)務(wù)場景

場景來自小灰的算法之旅，我們需要做一個(gè)拍賣行系統(tǒng)，用來查閱和出售游戲中的道具，類似于魔獸世界中的拍賣行那樣，還有以下需求：

拍賣行拍賣的商品需要支持四種排序方式，分別是：按價(jià)格、按等級、按剩余時(shí)間、按出售者ID排序，排序查詢要盡可能地快。還要支持輸入道具名稱的精確查詢和不輸入名稱的全量查詢。

這樣的業(yè)務(wù)場景所需要的數(shù)據(jù)結(jié)構(gòu)該如何設(shè)計(jì)呢？拍賣行商品列表是線性的，最容易表達(dá)線性結(jié)構(gòu)的是數(shù)組和鏈表。假如用有序數(shù)組，雖然查找的時(shí)候可以使用二分法（時(shí)間復(fù)雜度O(logN)），但是插入的時(shí)間復(fù)雜度是O(N)，總體時(shí)間復(fù)雜度是O(N)；而如果要使用有序鏈表，雖然插入的時(shí)間復(fù)雜度是O(1)，但是查找的時(shí)間復(fù)雜度是O(N)，總體還是O(N)。

那有沒有一種數(shù)據(jù)結(jié)構(gòu)，查找時(shí)，有二分法的效率，插入時(shí)有鏈表的簡單呢？有的，就是 跳表。

1.2、skiplist

skiplist，即跳表，又稱跳躍表，也是一種數(shù)據(jù)結(jié)構(gòu)，用于解決算法問題中的查找問題。

一般問題中的查找分為兩大類，一種是基于各種平衡術(shù)，時(shí)間復(fù)雜度為O(logN)，一種是基于哈希表，時(shí)間復(fù)雜度O(1)。但是skiplist比較特殊，沒有在這里面

2、跳表

2.1、跳表簡介

跳表也是鏈表的一種，是在鏈表的基礎(chǔ)上發(fā)展出來的，我們都知道，鏈表的插入和刪除只需要改動(dòng)指針就行了，時(shí)間復(fù)雜度是O(1)，但是插入和刪除必然伴隨著查找，而查找需要從頭/尾遍歷，時(shí)間復(fù)雜度為O(N)，如下圖所示是一個(gè)有序鏈表（最左側(cè)的灰色表示一個(gè)空的頭節(jié)點(diǎn)）（圖片來自網(wǎng)絡(luò)，以下同）：

鏈表中，每個(gè)節(jié)點(diǎn)都指向下一個(gè)節(jié)點(diǎn)，想要訪問下下個(gè)節(jié)點(diǎn)，必然要經(jīng)過下個(gè)節(jié)點(diǎn)，即無法跳過節(jié)點(diǎn)訪問，假設(shè)，現(xiàn)在要查找22，我們要先后查找 3->7->11->19->22，需要五次查找。

但是如果我們能夠?qū)崿F(xiàn)跳過一些節(jié)點(diǎn)訪問，就可以提高查找效率了，所以對鏈表進(jìn)行一些修改，如下圖：

我們每個(gè)一個(gè)節(jié)點(diǎn)，都會(huì)保存指向下下個(gè)節(jié)點(diǎn)的指針，這樣我們就能跳過某個(gè)節(jié)點(diǎn)進(jìn)行訪問，這樣，我們其實(shí)是構(gòu)造了兩個(gè)鏈表，新的鏈表之后原來鏈表的一半。

我們姑且稱原鏈表為第一層，新鏈表為第二層，第二層是在第一層的基礎(chǔ)上隔一個(gè)取一個(gè)。假設(shè)，現(xiàn)在還是要查找22，我們先從第二層查找，從7開始，7小于22，再往后，19小于22，再往后，26大于22，所以從節(jié)點(diǎn)19轉(zhuǎn)到第一層，找到了22，先后查找 7->19->26->22，只需要四次查找。

以此類推，如果再提取一層鏈表，查找效率豈不是更高，如下圖：

現(xiàn)在，又多了第三層鏈表，第三層是在第二層的基礎(chǔ)上隔一個(gè)取一個(gè)，假設(shè)現(xiàn)在還是要查找22，我們先從第三層開始查找，從19開始，19小于22，再往后，發(fā)現(xiàn)是空的，則轉(zhuǎn)到第二層，19后面的26大于22，轉(zhuǎn)到第一層，19后面的就是22，先后查找 19->26>22，只需要三次查找。

由上例可見，在查找時(shí)，跳過多個(gè)節(jié)點(diǎn)，可以大大提高查找效率，skiplist 就是基于此原理。

上面的例子中，每一層的節(jié)點(diǎn)個(gè)數(shù)都是下一層的一半，這種查找的過程有點(diǎn)類似二分法，查找的時(shí)間復(fù)雜度是O(logN)，但是例子中的多層鏈表有一個(gè)致命的缺陷，就是一旦有節(jié)點(diǎn)插入或者刪除，就會(huì)破壞這種上下層鏈表節(jié)點(diǎn)個(gè)數(shù)是2:1的結(jié)構(gòu)，如果想要繼續(xù)維持，則需要在插入或者刪除節(jié)點(diǎn)之后，對后面的所有節(jié)點(diǎn)進(jìn)行一次重新調(diào)整，這樣一來，插入/刪除的時(shí)間復(fù)雜度就變成了O(N)。

2.2、跳表層級之間的關(guān)系

如上所述，跳表為了解決插入和刪除節(jié)點(diǎn)時(shí)造成的后續(xù)節(jié)點(diǎn)重新調(diào)整的問題，引入了隨機(jī)層數(shù)的做法。相鄰層數(shù)之間的節(jié)點(diǎn)個(gè)數(shù)不再是嚴(yán)格的2:1的結(jié)構(gòu)，而是為每個(gè)新插入的節(jié)點(diǎn)賦予一個(gè)隨機(jī)的層數(shù)。下圖展示了如何通過一步步的插入操作從而形成一個(gè)跳表：

每一個(gè)節(jié)點(diǎn)的層數(shù)都是隨機(jī)算法得出的，插入一個(gè)新的節(jié)點(diǎn)不會(huì)影響其他節(jié)點(diǎn)的層數(shù)，因此，插入操作只需要修改插入節(jié)點(diǎn)前后的指針即可，避免了對后續(xù)節(jié)點(diǎn)的重新調(diào)整。這是跳表的一個(gè)很重要的特性，也是跳表性能明顯由于平衡樹的原因，因?yàn)槠胶鈽湓谑テ胶庵笠残枰M(jìn)行平衡調(diào)整。

上圖最后的跳表中，我們需要查找節(jié)點(diǎn)22，則遍歷到的節(jié)點(diǎn)依次是：7->37->19->22，可見，這種隨機(jī)層數(shù)的跳表的查找時(shí)可能沒有2:1結(jié)構(gòu)的效率，但是卻解決了插入/刪除節(jié)點(diǎn)的問題。

2.3、跳表的復(fù)雜度

跳表搜索的時(shí)間復(fù)雜度平均 O(logN)，最壞O(N)，空間復(fù)雜度O(2N)，即O(N)

3、Redis中的跳表

在理解 Redis 的跳躍表之前，我們先回憶一下 Redis 的有序集合（sorted set）操作

• 不重復(fù)但有序的字符串元素集合；
• 每個(gè)元素均關(guān)聯(lián)一個(gè)double類型的score，Redis 根據(jù)score進(jìn)行從小到大排序；
• score可以重復(fù)，重復(fù)的按照插入順序進(jìn)行排序；

示例如下：

redis 127.0.0.1:6379> ZADD runoobkey 1 redis
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 2 mongodb
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 3 mysql
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 3 mysql
(integer) 0
redis 127.0.0.1:6379> ZADD runoobkey 4 mysql
(integer) 0
redis 127.0.0.1:6379> ZRANGE runoobkey 0 10 WITHSCORES

"redis"
"1"
"mongodb"
"2"
"mysql"
"4"

這個(gè)是 Redis 中的有序列表的基本操作，我們答題可以看出，在有序列表中，有一個(gè)浮點(diǎn)數(shù)作為 score， 當(dāng)對應(yīng)一個(gè)值，可以根據(jù) score 精確查找和范圍查找，且效率很高

Redis 里面的這種操作的底層實(shí)現(xiàn)就是跳表。

上面理解了跳表，再去看 Redis 中的跳表就輕松多了，跳表的實(shí)現(xiàn)在 Redis 源碼目錄下 redis.h 文件中

3.1、zskiplistNode

zskiplistNode 表示跳表的一個(gè)節(jié)點(diǎn)，聲明如下：

typedef struct zskiplistNode {
  robj *obj;
  double score;
  struct zskiplistNode *backward;
  struct zskiplistLevel {
    struct zskiplistNode *forward;
    unsigned int span;
  } level[];
} zskiplistNode;

robj 類型是 Redis 中用C語言實(shí)現(xiàn)一種集合數(shù)據(jù)結(jié)構(gòu)，它可以表示 string、hash、list、set 和 zset 五種數(shù)據(jù)類型，這里不做詳細(xì)說明，在跳表節(jié)點(diǎn)中，這個(gè)類型的指針表示節(jié)點(diǎn)的成員對象

score 表示分值，用于排序和范圍查找

level 是一個(gè)柔性數(shù)組，它表示節(jié)點(diǎn)的層級，每層都有一個(gè)前進(jìn)指針 forward，用于指向相同層級指向表尾方向的下一個(gè)節(jié)點(diǎn)，而 span 則表示當(dāng)前節(jié)點(diǎn)在當(dāng)前層級中距離下一個(gè)節(jié)點(diǎn)的跨度，即兩個(gè)節(jié)點(diǎn)之間的距離。

初看上去，很容易以為跨度和遍歷節(jié)點(diǎn)有關(guān)，實(shí)際并不是，遍歷操作只用前進(jìn)指針就夠了，跨度是用來計(jì)算排位（rank）的：在查找某個(gè)節(jié)點(diǎn)的過程中，沿途訪問過的所有層的跨度累計(jì)起來，就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。

下圖中，查找成員o3，只經(jīng)歷了一層，排位為3

在 Redis 中，每個(gè)節(jié)點(diǎn)的層級都是根據(jù)冪次定律（power law，越大的樹出現(xiàn)的概率越?。╇S機(jī)生成的，它是1~32之間的一個(gè)數(shù)，作為level數(shù)組的大小，即高度

下圖分別展示了三個(gè)高度為1、3、5層的節(jié)點(diǎn)

backward 是一個(gè)后退指針，每個(gè)節(jié)點(diǎn)都有一個(gè)，指向當(dāng)前節(jié)點(diǎn)的表頭方向的下一個(gè)節(jié)點(diǎn)，用于從表尾進(jìn)行遍歷

3.2、zskiplist

zskiplist 表示一個(gè)跳表，聲明如下：

typedef struct zskiplist {
  struct zskiplistNode *header, *tail;
  unsigned long length;
  int level;
} zskiplist;

header 和 tail 指針分別指向表頭和表尾節(jié)點(diǎn)

length 記錄了節(jié)點(diǎn)數(shù)量

level 記錄了所有節(jié)點(diǎn)中層級最高的節(jié)點(diǎn)的層級，表頭節(jié)點(diǎn)的層高不計(jì)算在內(nèi)

下圖是一個(gè)跳表的示例，最左側(cè)是一個(gè) zskiplist 結(jié)構(gòu)，其右側(cè)是四個(gè) zskiplistNode 節(jié)點(diǎn)，從左向右分別有32層、4層、2層、5層。每個(gè)節(jié)點(diǎn)向右的指針即前進(jìn)指針 forward， BW 則表示后退指針 backward，每個(gè)節(jié)點(diǎn)依據(jù)節(jié)點(diǎn)的分值 score 進(jìn)行排列

到此這篇關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)中的跳躍表的文章就介紹到這了,更多相關(guān)Redis數(shù)據(jù)結(jié)構(gòu)跳躍表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！