欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

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

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

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

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

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

原理

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

如下圖所示:

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

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

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

  • 假設我們要查找 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é)點能否新加一層( 即前面如何從下往上構建出跳表 )的概率是 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)建跳表時頭結點就等于層高)

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

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

redis的跳表

就是在此基礎上添加回退指針,且score能重復

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

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

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

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

總結

以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關文章

  • 淺談我是如何用redis做實時訂閱推送的

    淺談我是如何用redis做實時訂閱推送的

    這篇文章主要介紹了淺談我是如何用redis做實時訂閱推送的,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-03-03
  • 使用Redis實現(xiàn)令牌桶算法原理解析

    使用Redis實現(xiàn)令牌桶算法原理解析

    這篇文章主要介紹了使用Redis實現(xiàn)令牌桶算法,該算法可以應對短暫的突發(fā)流量,這對于現(xiàn)實環(huán)境中流量不怎么均勻的情況特別有用,不會頻繁的觸發(fā)限流,對調(diào)用方比較友好,需要的朋友可以參考下
    2021-12-12
  • 基于Redis實現(xiàn)短信驗證碼登錄項目示例(附源碼)

    基于Redis實現(xiàn)短信驗證碼登錄項目示例(附源碼)

    手機登錄驗證在很多網(wǎng)頁上都得到使用,本文主要介紹了基于Redis實現(xiàn)短信驗證碼登錄項目示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-05-05
  • 如何查看redis服務的版本

    如何查看redis服務的版本

    這篇文章主要介紹了如何查看redis服務的版本問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • Redis動態(tài)字符串SDS的實現(xiàn)

    Redis動態(tài)字符串SDS的實現(xiàn)

    SDS在Redis中是實現(xiàn)字符串對象的工具,本文主要介紹了Redis動態(tài)字符串SDS的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2023-11-11
  • Redis cluster集群模式的原理解析

    Redis cluster集群模式的原理解析

    這篇文章主要介紹了Redis cluster集群模式的原理解析,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-04-04
  • redis yml配置的用法小結

    redis yml配置的用法小結

    RedisYML配置是Redis的一種配置文件格式,,對Redis的配置進行統(tǒng)一管理,本文就來介紹了redis yml配置的用法小結,具有一定的參考價值,感興趣的可以了解一下
    2024-02-02
  • Redis學習教程之命令的執(zhí)行過程詳解

    Redis學習教程之命令的執(zhí)行過程詳解

    這篇文章主要給大家介紹了關于Redis學習教程之命令的執(zhí)行過程的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧。
    2018-03-03
  • Redis Caffeine實現(xiàn)兩級緩存的項目實踐

    Redis Caffeine實現(xiàn)兩級緩存的項目實踐

    本文介紹了使用Redis和Caffeine實現(xiàn)兩級緩存,以提高查詢接口的性能,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-12-12
  • RedisDesktopManager無法遠程連接Redis的完美解決方法

    RedisDesktopManager無法遠程連接Redis的完美解決方法

    下載RedisDesktopManager客戶端,輸入服務器IP地址,端口(缺省值:6379);點擊Test Connection按鈕測試連接,連接失敗,怎么回事呢?下面小編給大家?guī)砹薘edisDesktopManager無法遠程連接Redis的完美解決方法,一起看看吧
    2018-03-03

最新評論