redis(4)跳躍表

1、跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu),它通過每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針,從而達(dá)到快速訪問節(jié)點(diǎn)的目的

2、跳躍表支持平均O(logN) 最壞o(N)復(fù)雜度的節(jié)點(diǎn)查找,還可以通過順序操作來批量處理節(jié)點(diǎn),大部分情況下效率媲美平衡樹,實(shí)現(xiàn)比平衡樹簡單,所以不少程序員用跳躍表來代替平衡樹

3、使用場景,有序集合包含元素數(shù)量比較多,或者成員member是比較長的字符串時。

4、跳躍表實(shí)現(xiàn),包含zskiplistnode zskiplist

4.1、zskiplist

header:指向跳躍表的表頭節(jié)點(diǎn) tail:指向跳躍表的表尾節(jié)點(diǎn),level:跳躍表內(nèi),層數(shù)最大的那個節(jié)點(diǎn)的層數(shù)(表頭節(jié)點(diǎn)層數(shù)不計算在內(nèi)) length:跳躍表長度,,,?包含的節(jié)點(diǎn)數(shù)量,表頭不計在內(nèi)

4.2、zskiplistnode

level:層 每個跳躍表節(jié)點(diǎn)層高都是1到32之間的隨機(jī)數(shù)

每個層有兩個屬性,前進(jìn)指針和跨度,前進(jìn)指針用戶訪問位于表尾方向的其他節(jié)點(diǎn),跨度則記錄前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離 后退(backward)指針:bw字樣標(biāo)記節(jié)點(diǎn)后退指針,后退指針從表尾向頭遍歷時使用

分值,各個節(jié)點(diǎn)按照各自保存的分值從小到大排列

成員對象obj

得分相同,則按照字典順序排序

5、僅通過多個跳躍表節(jié)點(diǎn)就能組成一個跳躍表,但是通過zskiplist結(jié)構(gòu)來持有這些節(jié)點(diǎn),程序可以更方便的對整個跳躍表進(jìn)行處理

5.1、查找表頭表尾復(fù)雜度為o(1) 計算長度length復(fù)雜度為o(1)

漫畫跳躍表http://www.itdecent.cn/p/ac351674d8eb?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容