摘要：前言本章將介紹中和的基本使用和內部原理因為這兩種數(shù)據(jù)結構有很多相似的地方所以把他們放到一章中介紹并且重點介紹內部一個很重要的數(shù)據(jù)結構跳躍表基本介紹先來看看中集合很像中鍵值對無序唯一不為空值重復無序是中最特別的基礎數(shù)據(jù)結構其他幾個都能和大致對

本章將介紹 Redis中 set 和 zset的基本使用和內部原理.因為這兩種數(shù)據(jù)結構有很多相似的地方所以把他們放到一章中介紹.并且重點介紹zset 內部一個很重要的數(shù)據(jù)結構:跳躍表.

先來看看 set

Redis 中 set 集合很像Java 中 HashSet,鍵值對無序、唯一、不為空.

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

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

> 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 的類型為 double 所以有時會出現(xiàn)小數(shù)點精度問題.

當 zset 中最后一個 value 被刪除后,這個和 zset 就會被自動刪除,內存被回收.

Redis 的 zset 是個復合結構,是由一個 hash 和 skiplist 組成的,其中 hash 用來保存 value 和 score 對應關系.skiplist 用來給 score 排序.關于hash 的內部實現(xiàn)請參閱之前的一篇文章:《你確定不來了解一下Redis中 Hash的原理嗎》,在這里我們著重介紹 skiplist 的實現(xiàn).

因為zset需要高效的插入和刪除,所以底層不適合使用數(shù)組實現(xiàn),需要使用鏈表的結構.當插入新元素時需要根據(jù) score插入到鏈表合適的位置,保證鏈表的有序性.高效的辦法是通過二分查找去找到插入點.

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

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

每個 kv 對應的結構為zslnode.kv 之間使用指針形成有序的雙向鏈表.同一層的 kv 會使用指針串起來.每層元素的遍歷都是從跳躍表的頭指針 kv header 出發(fā).

header 的結構也是 zslnode,當中 value 為 null,score 為 Double.MIN_VALUE排在最前面.

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

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

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

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

L3:header -> 4 -> header

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

L1: 2 -> 4 ->2

L0: 2 -> 3

說明:

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

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

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

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

整個查找過程算法的時間復雜度為$O(lg(n))$.