Redis 跳表(Skip List)原理實(shí)現(xiàn)
引言:為什么 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集群版所遇到的問題解決方案及redis可重入鎖是否會(huì)有死鎖的問題等,具有一定的參考價(jià)值,感興趣的可以了解一下2024-02-02多維度深入分析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-11Linux安裝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-01Redis使用bloom-filter過濾器實(shí)現(xiàn)推薦去重
這篇文章主要介紹了Redis使用bloom-filter過濾器實(shí)現(xiàn)推薦去重,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11Redis持久化方式之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-06redis哨兵模式分布式鎖實(shí)現(xiàn)與實(shí)踐方式(redisson)
這篇文章主要介紹了redis哨兵模式分布式鎖實(shí)現(xiàn)與實(shí)踐方式(redisson),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-03-03