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

更新時間：2025年02月07日 10:38:37 作者：空說

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

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

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

每個節(jié)點包含一個值和指向下一層節(jié)點的指針

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

原理

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

如下圖所示：

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

接下來我們通過查詢和添加元素來了解其功能流程：

1) 查詢元素: 這里我們與傳統(tǒng)的鏈表進行對比，來了解跳表查詢的高效。

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

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

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

補充插入的隨機層級

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

具體解釋

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

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

定位層級后，再將每一層的鏈表節(jié)點進行補齊，就是在 40 與 50 之間插入一個新的鏈表節(jié)點48，插入過程與鏈表插入是一樣的。

redis的跳表

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

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

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

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

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