摘要：前言本章將介紹中和的基本使用和內(nèi)部原理因?yàn)檫@兩種數(shù)據(jù)結(jié)構(gòu)有很多相似的地方所以把他們放到一章中介紹并且重點(diǎn)介紹內(nèi)部一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)跳躍表基本介紹先來(lái)看看中集合很像中鍵值對(duì)無(wú)序唯一不為空值重復(fù)無(wú)序是中最特別的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)其他幾個(gè)都能和大致對(duì)

本章將介紹 Redis中 set 和 zset的基本使用和內(nèi)部原理.因?yàn)檫@兩種數(shù)據(jù)結(jié)構(gòu)有很多相似的地方所以把他們放到一章中介紹.并且重點(diǎn)介紹zset 內(nèi)部一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu):跳躍表.

先來(lái)看看 set

Redis 中 set 集合很像Java 中 HashSet,鍵值對(duì)無(wú)序、唯一、不為空.

> sadd books Java
(integer 1)
> sadd books Java
(integer 0)            # value 值重復(fù)
> sadd books Go
(integer 1)
> smembers books        # 無(wú)序
1) "Go"
2) "Java"

zset 是 Redis 中最特別的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu),其他幾個(gè)都能和 Java 大致對(duì)應(yīng)上.它基本上還是一個(gè) set 但是添加了一個(gè) score 屬性去保證有序性.其內(nèi)部實(shí)現(xiàn)為跳躍表稍后將會(huì)著重介紹.

> zadd books 1 Java
(integer) 1
> zadd books 2 Go
(integer) 1
> zadd books 3 Python
(integer) 1
> zrange books 0 -1     #按 score 有序取出
1) "Java"
2) "Go"
3) "Python"

在 zset 中 score 的類(lèi)型為 double 所以有時(shí)會(huì)出現(xiàn)小數(shù)點(diǎn)精度問(wèn)題.

當(dāng) zset 中最后一個(gè) value 被刪除后,這個(gè)和 zset 就會(huì)被自動(dòng)刪除,內(nèi)存被回收.

Redis 的 zset 是個(gè)復(fù)合結(jié)構(gòu),是由一個(gè) hash 和 skiplist 組成的,其中 hash 用來(lái)保存 value 和 score 對(duì)應(yīng)關(guān)系.skiplist 用來(lái)給 score 排序.關(guān)于hash 的內(nèi)部實(shí)現(xiàn)請(qǐng)參閱之前的一篇文章:《你確定不來(lái)了解一下Redis中 Hash的原理嗎》,在這里我們著重介紹 skiplist 的實(shí)現(xiàn).

因?yàn)閦set需要高效的插入和刪除,所以底層不適合使用數(shù)組實(shí)現(xiàn),需要使用鏈表的結(jié)構(gòu).當(dāng)插入新元素時(shí)需要根據(jù) score插入到鏈表合適的位置,保證鏈表的有序性.高效的辦法是通過(guò)二分查找去找到插入點(diǎn).

那么問(wèn)題就來(lái)了,二分查找的對(duì)象必須是有序數(shù)組,只有數(shù)組支持快速定位,鏈表做不到該怎么辦呢?這時(shí),就該跳躍表出場(chǎng)了.

如圖所示,跳躍表在鏈表的基礎(chǔ)上加入了層級(jí)L0~L3的概念,Redis 的跳躍表共有 64 層,可容納 $2^{64}$ 個(gè)元素.每個(gè)元素的層級(jí)是隨機(jī)分配的,分配 L0 的概率是 100%,就是說(shuō)每個(gè)元素至少會(huì)有一層.分配L1 的概率是 50%,分配 L2 的概率是 25%,往上以此類(lèi)推.

每個(gè) kv 對(duì)應(yīng)的結(jié)構(gòu)為zslnode.kv 之間使用指針形成有序的雙向鏈表.同一層的 kv 會(huì)使用指針串起來(lái).每層元素的遍歷都是從跳躍表的頭指針 kv header 出發(fā).

header 的結(jié)構(gòu)也是 zslnode,當(dāng)中 value 為 null,score 為 Double.MIN_VALUE排在最前面.

struct zslnode{
    string value;
    double score;
    zslnode*[] forwards;    //多層連接的指針
    zslnode* backward;        //回溯指針
}

struct zsl{
    zslnode* header;            //跳躍表頭指針
    int maxLevel;                //當(dāng)前節(jié)點(diǎn)的最高層
    map ht;    //hash 中的鍵值對(duì)
}

介紹完 skiplist的數(shù)據(jù)結(jié)構(gòu)后,我們來(lái)具體看下skiplist 是怎樣快速定位元素的.

在上圖中,假設(shè)我們要查找 3 這個(gè)節(jié)點(diǎn).skiplist 會(huì)從 header 的頂層出發(fā)遍歷搜索找到第一個(gè)比目標(biāo)元素小的開(kāi)始降一層,直到降到最底層找到 3這個(gè)節(jié)點(diǎn),搜索路徑為:

L3:header -> 4 -> header

L2:header -> 2 -> 4 -> 2

L1: 2 -> 4 ->2

L0: 2 -> 3

說(shuō)明:

L3 層header找到 4比 3大,回退到 header 同時(shí)降一層

L2層header 找到 2比 3 小,繼續(xù)遍歷找到 4,回退到 2 同時(shí)降一層

L1 層 2 找到 4 比 3 大,回退到 2 降一層

L0 層 2 找到 3 期望節(jié)點(diǎn)

整個(gè)查找過(guò)程算法的時(shí)間復(fù)雜度為$O(lg(n))$.