Sortedset底層存儲(chǔ)結(jié)構(gòu)
sortedset同時(shí)會(huì)由兩種數(shù)據(jù)結(jié)構(gòu)支持,ziplist和skiplist.
只有同時(shí)滿足如下條件是,使用的是ziplist,其他時(shí)候則是使用skiplist
- 有序集合保存的元素?cái)?shù)量小于128個(gè)
- 有序集合保存的所有元素的長度小于64字節(jié)
當(dāng)ziplist作為存儲(chǔ)結(jié)構(gòu)時(shí)候,每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表結(jié)點(diǎn)來保存,第一個(gè)節(jié)點(diǎn)保存元素的成員,第二個(gè)元素保存元素的分值.
當(dāng)使用skiplist作為存儲(chǔ)結(jié)構(gòu)時(shí),使用skiplist按序保存元素分值,使用dict來保存元素和分值的對應(yīng)關(guān)系
參考資料
跳躍表(skiplist)
跳躍表是一種基于有序鏈表的擴(kuò)展,簡稱跳表.跳表會(huì)維護(hù)多個(gè)索引鏈表和原鏈表.
不斷得提升新的關(guān)鍵節(jié)點(diǎn)形成新的有序鏈表,通過空間換時(shí)間.
對有序鏈表進(jìn)行關(guān)鍵點(diǎn)的提升,作為插入對比的索引
插入邏輯
鏈表插入新的元素,只需對比新元素的值和關(guān)鍵點(diǎn)鏈表,這樣就能將對比次數(shù)縮減.
關(guān)鍵節(jié)點(diǎn)提取邏輯
因?yàn)樵谔碇?使用空間換時(shí)間,會(huì)有多層的索引鏈表,每一層索引鏈表都是上一層的一半,當(dāng)數(shù)據(jù)量較大的時(shí)候,就能夠很輕松的降低鏈表查詢消耗的性能.
至于提取的極限,是同一層只有兩個(gè)節(jié)點(diǎn)
一個(gè)節(jié)點(diǎn)是沒有比較意義的
這樣的多層鏈表結(jié)構(gòu),就是所謂的跳躍表
提取新的索引節(jié)點(diǎn)
跳表采用拋硬幣的做法,在插入之后會(huì)隨機(jī)判斷新插入的元素是否稱為新的關(guān)鍵點(diǎn)
跳表插入節(jié)點(diǎn)的流程
- 1.新節(jié)點(diǎn)和各層索引節(jié)點(diǎn)逐一比較,確定原鏈表的插入位置O(logN)
- 2.把索引插入到原鏈表,O(1)
- 3.利用拋硬幣的隨機(jī)方式,決定新界店是否提升為上一級(jí)索引.O(logN)
總體上跳表插入的時(shí)間復(fù)雜度是O(logN),空間復(fù)雜度是O(N)
節(jié)點(diǎn)刪除的流程
- 1.在索引層找到響應(yīng)節(jié)點(diǎn)進(jìn)行刪除,刪除每一層的相同節(jié)點(diǎn)O(logN)
- 3.如果某一層在刪除節(jié)點(diǎn)后只剩下一個(gè)節(jié)點(diǎn),那么這個(gè)鏈表就可以刪除了.O(logN)
跳表刪除的時(shí)間復(fù)雜度是O(logN)
