快捷導(dǎo)航

Redis中跳表的實(shí)現(xiàn)原理分析

更新時(shí)間：2025年02月07日 10:38:37 作者：空說(shuō)

Redis中的跳表是一種高效的多層鏈表結(jié)構(gòu),通過(guò)隨機(jī)概率算法決定節(jié)點(diǎn)的層數(shù),從而實(shí)現(xiàn)快速的插入、刪除和查詢操作,跳表的平均時(shí)間復(fù)雜度為O(logn),最差情況為O(n),每個(gè)節(jié)點(diǎn)包含值和指向更高層節(jié)點(diǎn)的指針,以及回退指針以提高操作效率

Redis中跳表的實(shí)現(xiàn)原理

跳表: 主要通過(guò)多重鏈表實(shí)現(xiàn)，最底層包含所有元素，上層都是底層元素的跳躍索引，每一層的元素是從下一層中隨機(jī)選擇的，通常使用概率算法來(lái)決定一個(gè)元素是否出現(xiàn)在上一層。

每個(gè)節(jié)點(diǎn)包含一個(gè)值和指向下一層節(jié)點(diǎn)的指針

插入時(shí)，首先從最高層開(kāi)始查找插入位置，然后隨機(jī)決定新節(jié)點(diǎn)的層數(shù)，最后在相應(yīng)的層中插入節(jié)點(diǎn)并更新指針。
刪除時(shí)，同樣從最高層開(kāi)始查找要?jiǎng)h除的節(jié)點(diǎn)，并在各層中更新指針，以保持跳表的結(jié)構(gòu)。
查找時(shí)，從最高層開(kāi)始，逐層向下，直到找到目標(biāo)元素或確定元素不存在。查找效率高，時(shí)間復(fù)雜度為 O(logn)

原理

跳表，一句話概括：就是一個(gè)多層索引的鏈表，每一層索引的元素在最底層的鏈表中可以找到( 這一點(diǎn)和 B+樹(shù)是一樣的 )

如下圖所示：

這就是一個(gè)簡(jiǎn)單的跳表實(shí)現(xiàn)了，每個(gè)顏色代表一層，綠色的就是鏈表的最底層了

接下來(lái)我們通過(guò)查詢和添加元素來(lái)了解其功能流程：

1) 查詢?cè)? 這里我們與傳統(tǒng)的鏈表進(jìn)行對(duì)比，來(lái)了解跳表查詢的高效。

假設(shè)我們要查找 50 這個(gè)元素，如果通過(guò)傳統(tǒng)鏈表的話( 看最底層綠色的查詢路線 )，需要查找 4次，查找的時(shí)間復(fù)雜度為0(n)
但如果使用跳表的話，其只需要從最上面的 10 開(kāi)始，首先跳到 40 ，發(fā)現(xiàn)目標(biāo)元素比 40 大，然后對(duì)比后一個(gè)元素比 70 小。于是就前往下一層進(jìn)行查找，然后 40 的下一個(gè) 50 剛好符合目標(biāo)，就直接返回就可以了，類(lèi)似 B+樹(shù)二分查找
這個(gè)過(guò)程的跳轉(zhuǎn)次數(shù)是3次，即10->40(頂層)->40(第二層)->50(第二層)，跳表的平均時(shí)間查詢復(fù)雜度是 0(logn)，最差的時(shí)間復(fù)雜度是O(n)

2) 插入元素: 我們插入一條 score 為 48 的數(shù)據(jù)

先需要定位到第一個(gè)比 score 大的數(shù)據(jù)。如圖所示，一下子就可以定位到 50 了，這里和查詢的過(guò)程( 上文所示 )是一樣的。
在定位到對(duì)應(yīng)節(jié)點(diǎn)之后，將在節(jié)點(diǎn)所有應(yīng)該存在的層級(jí)上進(jìn)行插入操作，這里就是40-50之間的所有層

補(bǔ)充插入的隨機(jī)層級(jí)

一個(gè)節(jié)點(diǎn)有多少層，Redis 是采用隨機(jī)的概率函數(shù)來(lái)決定的。
在代碼中，跳表每一個(gè)節(jié)點(diǎn)能否新加一層( 即前面如何從下往上構(gòu)建出跳表 )的概率是 25 %
然后最多的層數(shù)在 Redis 5.0 中是 64 層，Redis 7.0 中是 32層。

具體解釋

跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會(huì)生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25，那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，這樣的做法，相當(dāng)于每增加一層的概率不超過(guò) 25%，層數(shù)越高，概率越低，層高最大限制是 64。（創(chuàng)建跳表時(shí)頭結(jié)點(diǎn)就等于層高）

//5層跳表
10
10        50
10  20    50
10  20 30 50
10  20 30 50
//比如插入20這個(gè)結(jié)點(diǎn)時(shí)會(huì)生成隨機(jī)數(shù)
    如果>0.25，那么這一層的高度+1，然后繼續(xù)生成隨機(jī)數(shù)
    								如果還是>0.25，高度繼續(xù)+1，依次類(lèi)推
    如果<0.25，終止，記錄 該結(jié)點(diǎn)的最終高度

定位層級(jí)后，再將每一層的鏈表節(jié)點(diǎn)進(jìn)行補(bǔ)齊，就是在 40 與 50 之間插入一個(gè)新的鏈表節(jié)點(diǎn)48，插入過(guò)程與鏈表插入是一樣的。

redis的跳表

就是在此基礎(chǔ)上添加回退指針，且score能重復(fù)

為什么 Redis 跳表實(shí)現(xiàn)多了個(gè)回退指針(前驅(qū)指針)？

回退指針主要是為了提高跳表的操作效率和靈活性，例如在進(jìn)行刪除操作時(shí)，需要找到要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)以便更新指針?；赝酥羔樖沟眠@一過(guò)程更為高效，避免了從最高層開(kāi)始逐層查找。

尤其是在頻繁插入和刪除的場(chǎng)景中，回退指針減少了節(jié)點(diǎn)之間指針的更新復(fù)雜度，提升性能。

typedef struct zskiplistNode {
    //Zset 對(duì)象的元素值
    sds ele;
    //元素權(quán)重值
    double score;
    //后退指針
    struct zskiplistNode *backward;
  
    //節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;