Redis中跳表的實現(xiàn)原理分析
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實現(xiàn)短信驗證碼登錄項目示例(附源碼)
手機登錄驗證在很多網(wǎng)頁上都得到使用,本文主要介紹了基于Redis實現(xiàn)短信驗證碼登錄項目示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-05-05Redis Caffeine實現(xiàn)兩級緩存的項目實踐
本文介紹了使用Redis和Caffeine實現(xiàn)兩級緩存,以提高查詢接口的性能,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-12-12RedisDesktopManager無法遠程連接Redis的完美解決方法
下載RedisDesktopManager客戶端,輸入服務器IP地址,端口(缺省值:6379);點擊Test Connection按鈕測試連接,連接失敗,怎么回事呢?下面小編給大家?guī)砹薘edisDesktopManager無法遠程連接Redis的完美解決方法,一起看看吧2018-03-03