Redis中跳表的實(shí)現(xiàn)原理分析
Redis中跳表的實(shí)現(xiàn)原理
跳表: 主要通過多重鏈表實(shí)現(xiàn),最底層包含所有元素,上層都是底層元素的跳躍索引,每一層的元素是從下一層中隨機(jī)選擇的,通常使用概率算法來決定一個(gè)元素是否出現(xiàn)在上一層。
每個(gè)節(jié)點(diǎn)包含一個(gè)值和指向下一層節(jié)點(diǎn)的指針
- 插入時(shí),首先從最高層開始查找插入位置,然后隨機(jī)決定新節(jié)點(diǎn)的層數(shù),最后在相應(yīng)的層中插入節(jié)點(diǎn)并更新指針。
- 刪除時(shí),同樣從最高層開始查找要?jiǎng)h除的節(jié)點(diǎn),并在各層中更新指針,以保持跳表的結(jié)構(gòu)。
- 查找時(shí),從最高層開始,逐層向下,直到找到目標(biāo)元素或確定元素不存在。查找效率高,時(shí)間復(fù)雜度為 O(logn)
原理
跳表,一句話概括:就是一個(gè)多層索引的鏈表,每一層索引的元素在最底層的鏈表中可以找到( 這一點(diǎn)和 B+樹是一樣的 )
如下圖所示:
這就是一個(gè)簡(jiǎn)單的跳表實(shí)現(xiàn)了,每個(gè)顏色代表一層,綠色的就是鏈表的最底層了
接下來我們通過查詢和添加元素來了解其功能流程:
1) 查詢?cè)? 這里我們與傳統(tǒng)的鏈表進(jìn)行對(duì)比,來了解跳表查詢的高效。
- 假設(shè)我們要查找 50 這個(gè)元素,如果通過傳統(tǒng)鏈表的話( 看最底層綠色的查詢路線 ),需要查找 4次,查找的時(shí)間復(fù)雜度為0(n)
- 但如果使用跳表的話,其只需要從最上面的 10 開始,首先跳到 40 ,發(fā)現(xiàn)目標(biāo)元素比 40 大,然后對(duì)比后一個(gè)元素比 70 小。于是就前往下一層進(jìn)行查找,然后 40 的下一個(gè) 50 剛好符合目標(biāo),就直接返回就可以了,類似 B+樹二分查找
- 這個(gè)過程的跳轉(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 了,這里和查詢的過程( 上文所示 )是一樣的。
- 在定位到對(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ù)來決定的。
- 在代碼中,跳表每一個(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)于每增加一層的概率不超過 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,依次類推 如果<0.25,終止,記錄 該結(jié)點(diǎn)的最終高度
定位層級(jí)后,再將每一層的鏈表節(jié)點(diǎn)進(jìn)行補(bǔ)齊,就是在 40 與 50 之間插入一個(gè)新的鏈表節(jié)點(diǎn)48,插入過程與鏈表插入是一樣的。
redis的跳表
就是在此基礎(chǔ)上添加回退指針,且score能重復(fù)
為什么 Redis 跳表實(shí)現(xiàn)多了個(gè)回退指針(前驅(qū)指針)?
回退指針主要是為了提高跳表的操作效率和靈活性,例如在進(jìn)行刪除操作時(shí),需要找到要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)以便更新指針。回退指針使得這一過程更為高效,避免了從最高層開始逐層查找。
尤其是在頻繁插入和刪除的場(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;
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
淺談我是如何用redis做實(shí)時(shí)訂閱推送的
這篇文章主要介紹了淺談我是如何用redis做實(shí)時(shí)訂閱推送的,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03基于Redis實(shí)現(xiàn)短信驗(yàn)證碼登錄項(xiàng)目示例(附源碼)
手機(jī)登錄驗(yàn)證在很多網(wǎng)頁上都得到使用,本文主要介紹了基于Redis實(shí)現(xiàn)短信驗(yàn)證碼登錄項(xiàng)目示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05Redis動(dòng)態(tài)字符串SDS的實(shí)現(xiàn)
SDS在Redis中是實(shí)現(xiàn)字符串對(duì)象的工具,本文主要介紹了Redis動(dòng)態(tài)字符串SDS的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11Redis學(xué)習(xí)教程之命令的執(zhí)行過程詳解
這篇文章主要給大家介紹了關(guān)于Redis學(xué)習(xí)教程之命令的執(zhí)行過程的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-03-03Redis Caffeine實(shí)現(xiàn)兩級(jí)緩存的項(xiàng)目實(shí)踐
本文介紹了使用Redis和Caffeine實(shí)現(xiàn)兩級(jí)緩存,以提高查詢接口的性能,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-12-12RedisDesktopManager無法遠(yuǎn)程連接Redis的完美解決方法
下載RedisDesktopManager客戶端,輸入服務(wù)器IP地址,端口(缺省值:6379);點(diǎn)擊Test Connection按鈕測(cè)試連接,連接失敗,怎么回事呢?下面小編給大家?guī)砹薘edisDesktopManager無法遠(yuǎn)程連接Redis的完美解決方法,一起看看吧2018-03-03