Redis數(shù)據(jù)結(jié)構(gòu)SortedSet的底層原理解析

更新時間：2022年07月13日 15:59:08 作者：空指針異常1

這篇文章主要介紹了Redis數(shù)據(jù)結(jié)構(gòu)SortedSet的底層原理解析，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

概述

一些常用命令

存儲：zadd key score value
獲取：zrange key start end
獲?。和瑫r獲取分?jǐn)?shù)：zrange key start end with score
刪除：zrem key value

存儲的時候我們可以發(fā)現(xiàn)，是有一個score（分?jǐn)?shù)）的，這個就是用來排序的字段。

實(shí)現(xiàn)

先說結(jié)論，SortedSet底層，根據(jù)配置會在不同的時候選用兩種不同的數(shù)據(jù)結(jié)構(gòu)zset，或ziplist進(jìn)行存儲：

首先，我們來看幾個參數(shù)：

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

if (
    field-value對的數(shù)量 > ziplist.entries.size ||
    任意一個filed或value長度 > zset-max-ziplist-value
) {
    // 使用 zset 進(jìn)行存儲
} else {
    // 使用 ziplist 進(jìn)行存儲

zset的結(jié)構(gòu)如下：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset

可以發(fā)現(xiàn)，是由字典+跳躍表實(shí)現(xiàn)的。

zset 結(jié)構(gòu)體里有兩個元素，一個是 dict，用來維護(hù) 數(shù)據(jù) 到分?jǐn)?shù) 的關(guān)系，一個是 zskiplist，用來維護(hù) 分?jǐn)?shù)所在鏈表的關(guān)系
dict 里通過維護(hù) 哈希表存儲了張三=>100，李四=>90 的分?jǐn)?shù)關(guān)系。

而跳表則是排序的關(guān)鍵

跳躍表

先上圖：

我們知道，鏈表的檢索效率是非常低的，如果要拿到100條數(shù)據(jù)中間的數(shù)據(jù)，則需要遍歷50個數(shù)據(jù)才行，為了解決這個問題，跳表應(yīng)運(yùn)而生

如上圖，就是常規(guī)的跳表，會在原有的數(shù)據(jù)上加上若干層，指向當(dāng)前層的下一個節(jié)點(diǎn)。

跳表的插入

如上圖所示：其實(shí)每個節(jié)點(diǎn)的層數(shù)是隨機(jī)的，而且新插入一個節(jié)點(diǎn)不會影響其它節(jié)點(diǎn)的層數(shù)。因此，插入操作只需要修改插入節(jié)點(diǎn)前后的指針，而不需要對很多節(jié)點(diǎn)都進(jìn)行調(diào)整。這就降低了插入操作的復(fù)雜度。實(shí)際上，這是skiplist跳表的一個很重要的特性，這讓它在插入性能上明顯優(yōu)于平衡樹的方案。

如下圖，假如我們需要查詢23，查詢的路徑如下。