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

Redis 跳表(Skip List)原理實(shí)現(xiàn)

 更新時(shí)間:2025年04月07日 10:04:10   作者:xiaoyu?  
跳表是zset有序集合的底層實(shí)現(xiàn)之一,本文主要介紹了Redis 跳表(Skip List)原理實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

引言:為什么 Redis 選擇跳表?

在有序集合(ZSET)的實(shí)現(xiàn)中,Redis 開發(fā)者面臨一個(gè)關(guān)鍵抉擇:如何在高性能讀寫和代碼簡(jiǎn)潔性之間找到平衡?傳統(tǒng)平衡樹(如紅黑樹)雖然能保證 O(logN) 時(shí)間復(fù)雜度,但實(shí)現(xiàn)復(fù)雜且難以支持范圍查詢。跳表(Skip List) 以媲美平衡樹的性能、極簡(jiǎn)的實(shí)現(xiàn)(約 200 行代碼)和天然支持范圍查詢的特性,成為 Redis ZSET 的核心數(shù)據(jù)結(jié)構(gòu)。本文將深入剖析跳表的實(shí)現(xiàn)細(xì)節(jié)與 Redis 的工程優(yōu)化。

一、跳表核心思想:概率化的多層索引

1.1 從鏈表到跳表的進(jìn)化

  • 普通鏈表:插入/刪除 O(1),但查詢需要 O(N)
  • 跳表創(chuàng)新:通過隨機(jī)化多層索引,實(shí)現(xiàn)對(duì)數(shù)級(jí)查詢效率

1.2 跳表結(jié)構(gòu)可視化

Level 3: Head -> 37 --------------------------> 99 -> NULL  
Level 2: Head -> 37 -------> 71 -------> 99 -> NULL  
Level 1: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  
Level 0: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  

關(guān)鍵特性

每個(gè)節(jié)點(diǎn)隨機(jī)生成層數(shù)(Redis 最大層數(shù) 64)

高層索引跨越更多節(jié)點(diǎn),加速搜索

底層鏈表存儲(chǔ)完整數(shù)據(jù)

二、Redis 跳表實(shí)現(xiàn)深度解剖

2.1 數(shù)據(jù)結(jié)構(gòu)定義(redis.h)

// 跳表節(jié)點(diǎn)
typedef struct zskiplistNode {
    sds ele;                          // 成員對(duì)象(SDS字符串)
    double score;                     // 排序分值
    struct zskiplistNode *backward;   // 后退指針(雙向鏈表)
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進(jìn)指針
        unsigned long span;            // 跨度(用于排名計(jì)算)
    } level[];                        // 柔性數(shù)組,層級(jí)隨機(jī)生成
} zskiplistNode;

// 跳表結(jié)構(gòu)
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;             // 節(jié)點(diǎn)總數(shù)
    int level;                        // 當(dāng)前最大層數(shù)
} zskiplist;

設(shè)計(jì)亮點(diǎn)

  • span 字段:記錄節(jié)點(diǎn)在某一層的跨度,支持 O(1) 時(shí)間復(fù)雜度計(jì)算元素排名(ZRANK
  • backward 指針:構(gòu)成雙向鏈表,支持逆序遍歷
  • 柔性數(shù)組(level[]):內(nèi)存緊湊,避免指針冗余

2.2 關(guān)鍵操作源碼解析

2.2.1 節(jié)點(diǎn)層數(shù)生成算法

// redis.h 源碼節(jié)選
int zslRandomLevel(void) {
    int level = 1;
    // 0xFFFF 對(duì)應(yīng) 1/4 概率提升層級(jí)(基于位運(yùn)算優(yōu)化)
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

數(shù)學(xué)原理

  • 使用 冪次定律(Power Law),高層節(jié)點(diǎn)指數(shù)級(jí)減少
  • 每個(gè)節(jié)點(diǎn)有 50% 概率進(jìn)入 L1,25% 進(jìn)入 L2,12.5% 進(jìn)入 L3...
  • Redis 實(shí)際使用 1/4 的概率因子(優(yōu)化內(nèi)存與性能平衡)

2.2.2 插入節(jié)點(diǎn)流程(zslInsert)

  • 搜索路徑記錄:從最高層開始,記錄每層的前驅(qū)節(jié)點(diǎn)和跨度
  • 生成隨機(jī)層數(shù):調(diào)用 zslRandomLevel
  • 創(chuàng)建新節(jié)點(diǎn):分配層級(jí)并連接前后指針
  • 更新跨度:調(diào)整相鄰節(jié)點(diǎn)的 span 值
  • 維護(hù)后退指針:設(shè)置新節(jié)點(diǎn)的 backward 指針

2.2.3 范圍查詢(ZRANGEBYSCORE)

  • 從高層索引快速定位起點(diǎn)
  • 利用底層鏈表遍歷范圍
  • 復(fù)雜度:O(logN + M)(M 為返回元素?cái)?shù)量)

三、性能分析與優(yōu)化策略

3.1 時(shí)間復(fù)雜度對(duì)比

操作跳表(平均)跳表(最壞)平衡樹
插入O(logN)O(N)O(logN)
刪除O(logN)O(N)O(logN)
查找O(logN)O(N)O(logN)
范圍查詢O(logN + M)O(N)O(logN + M)

:跳表最壞情況(所有節(jié)點(diǎn)高度相同)概率極低(例如 1億節(jié)點(diǎn)出現(xiàn)概率為 1/(2^50))

3.2 內(nèi)存占用分析

  • 理論空間復(fù)雜度:O(NlogN)
  • Redis 優(yōu)化實(shí)踐:通過 1/4 概率因子,實(shí)際空間占用約為 O(1.33N)(實(shí)測(cè) 100 萬節(jié)點(diǎn)內(nèi)存約 64MB)

3.3 調(diào)優(yōu)參數(shù)

  • ZSKIPLIST_MAXLEVEL:控制最大層數(shù)(默認(rèn) 64,可調(diào)整內(nèi)存與性能平衡)
  • ZSKIPLIST_P:調(diào)整層數(shù)生成概率(默認(rèn) 0.25)

四、跳表在 Redis 中的應(yīng)用場(chǎng)景

4.1 有序集合(ZSET)

元素?cái)?shù)量 > 128 或 元素長(zhǎng)度 > 64 字節(jié) 時(shí),ZSET 內(nèi)部使用跳表

支持操作

  • ZADD/ZREM:插入刪除
  • ZRANK/ZSCORE:排名查詢
  • ZRANGE:范圍查詢

4.2 集群元數(shù)據(jù)管理

用于維護(hù)槽位(slot)與節(jié)點(diǎn)的映射關(guān)系

五、跳表 vs 平衡樹:工程角度的選擇

維度跳表紅黑樹
實(shí)現(xiàn)復(fù)雜度約 200 行代碼約 500 行代碼
范圍查詢天然支持(鏈表特性)需要額外遍歷
并發(fā)控制更易實(shí)現(xiàn)無鎖優(yōu)化需要復(fù)雜鎖機(jī)制
調(diào)試難度可視化調(diào)試友好樹旋轉(zhuǎn)邏輯難追蹤

Redis 作者 Antirez 的評(píng)價(jià):“跳表在理論上不如平衡樹優(yōu)雅,但實(shí)際工程中更簡(jiǎn)單、更快,尤其適合需要范圍查詢的場(chǎng)景。”

總結(jié):

跳表的精妙之處在于 用概率換結(jié)構(gòu),通過隨機(jī)化層級(jí)分布避免復(fù)雜的再平衡操作。這種“以空間換時(shí)間” + “以概率換簡(jiǎn)單性”的設(shè)計(jì)哲學(xué),在分布式系統(tǒng)開發(fā)中具有重要借鑒意義。理解跳表不僅有助于掌握 Redis 源碼,更能啟發(fā)我們思考如何在高性能與可維護(hù)性之間找到平衡。

到此這篇關(guān)于Redis 跳表(Skip List)原理實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Redis 跳表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • redis cluster集群模式下實(shí)現(xiàn)批量可重入鎖

    redis cluster集群模式下實(shí)現(xiàn)批量可重入鎖

    本文主要介紹了使用redis cluster集群版所遇到的問題解決方案及redis可重入鎖是否會(huì)有死鎖的問題等,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-02-02
  • 多維度深入分析Redis的5種基本數(shù)據(jù)結(jié)構(gòu)

    多維度深入分析Redis的5種基本數(shù)據(jù)結(jié)構(gòu)

    此篇文章主要對(duì)Redis的5種基本數(shù)據(jù)類型,即字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted?Set),從使用場(chǎng)景和底層結(jié)構(gòu)出發(fā),進(jìn)行多維度深入分析。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-11-11
  • Redis的4種緩存模式分享

    Redis的4種緩存模式分享

    這篇文章主要介紹了Redis的4種緩存模式分享,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,感興趣的小伙伴可以參考一下
    2022-07-07
  • Redis大key和多key拆分的解決方案

    Redis大key和多key拆分的解決方案

    大key會(huì)導(dǎo)致內(nèi)存使用過高,多key可能導(dǎo)致查詢效率低下,本文主要介紹了Redis大key和多key拆分的解決方案,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-03-03
  • Linux安裝Redis、后臺(tái)運(yùn)行、系統(tǒng)自啟動(dòng)的設(shè)置方法

    Linux安裝Redis、后臺(tái)運(yùn)行、系統(tǒng)自啟動(dòng)的設(shè)置方法

    Redis是用C語言編寫的開源免費(fèi)的高性能的分布式內(nèi)存數(shù)據(jù)庫,基于內(nèi)存運(yùn)行并支持持久化的NoSQL數(shù)據(jù)庫。這篇文章主要介紹了Linux安裝Redis、后臺(tái)運(yùn)行、系統(tǒng)自啟動(dòng),需要的朋友可以參考下
    2020-01-01
  • Redis使用bloom-filter過濾器實(shí)現(xiàn)推薦去重

    Redis使用bloom-filter過濾器實(shí)現(xiàn)推薦去重

    這篇文章主要介紹了Redis使用bloom-filter過濾器實(shí)現(xiàn)推薦去重,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-11-11
  • 利用redis實(shí)現(xiàn)排行榜的小秘訣

    利用redis實(shí)現(xiàn)排行榜的小秘訣

    這篇文章主要給大家介紹了關(guān)于如何利用redis實(shí)現(xiàn)排行榜的小秘訣,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用redis具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-03-03
  • Redis和Memcached的區(qū)別詳解

    Redis和Memcached的區(qū)別詳解

    這篇文章主要介紹了Redis和Memcached的區(qū)別詳解,本文從各方面總結(jié)了兩個(gè)數(shù)據(jù)庫的不同之處,需要的朋友可以參考下
    2015-03-03
  • Redis持久化方式之RDB和AOF的原理及優(yōu)缺點(diǎn)

    Redis持久化方式之RDB和AOF的原理及優(yōu)缺點(diǎn)

    在Redis中,數(shù)據(jù)可以分為兩類,即內(nèi)存數(shù)據(jù)和磁盤數(shù)據(jù),Redis?提供了兩種不同的持久化方式,其中?RDB?是快照備份機(jī)制,AOF?則是追加寫操作機(jī)制,本文將詳細(xì)給大家介紹Redis?持久化方式RDB和AOF的原理及優(yōu)缺點(diǎn),感興趣的同學(xué)可以跟著小編一起來學(xué)習(xí)
    2023-06-06
  • redis哨兵模式分布式鎖實(shí)現(xiàn)與實(shí)踐方式(redisson)

    redis哨兵模式分布式鎖實(shí)現(xiàn)與實(shí)踐方式(redisson)

    這篇文章主要介紹了redis哨兵模式分布式鎖實(shí)現(xiàn)與實(shí)踐方式(redisson),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-03-03

最新評(píng)論