Redis學習筆記（四） 跳躍表與整數集合

（一）跳躍表

跳躍表是一種有序的數據結構，它通過每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。

Redis使用跳躍表作為有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，或者有序集合中元素的成員是比較長的字元串時，Redis就會使用跳躍表作為有序集合鍵的底層實現。

Redis中的兩個地方用到了跳躍表，一個是實現有序集合鍵，另一個是在集群節點中用作內部數據結構。

Redis的跳躍表由zskiplistNode 與 zskiplist 兩個結構定義。其中zskiplistNode 結構用於標識跳躍表節點，zskiplist結構用於保存跳躍表節點的相關信息（表頭、表尾節點、節點數量等）。

zskiplistNode

typedef struct zskiplistNode{
　　//層
　　struct zskiplistLevel{
　　　　struct zskiplistNode *forward;//前進指針
　　　　unsigned int span;//跨度
　　} level[];
　　//後退指針
　　struct zskiplistNode *backward;
　　//分值
　　double score;
　　//成員對象
　　robj *obj;
}

層中包含多個元素，每個元素是指向其他節點的指針，通過這些層可以加快訪問其他節點的速度，層越多，訪問其他節點的速度越快。沒增加一個跳躍節點，程式根據冪次定律（越大的數出現概率越小）生成1-32之間的值作為層高。

1、每層都有一個指向表尾方向的前進指針，作為表頭向表尾方向訪問節點。

2、層中的跨度用於記錄兩個節點之間的距離。

3、後退指針則只能一次跨1個節點進行訪問。

4、跳躍表的排序是按照所有節點的分值來排序的。

5、節點中的對象則是保存了一個SDS的字元串。

6、同一個跳躍表的對象必須唯一，但分值可以重覆。（相同分數，成員小的靠前排）。

跳躍表zskiplist

typedef struct zskiplist{
    struct skiplistNode *header,*tail;//表頭節點與表尾節點
    unsigned long length;//表中節點的數量
    int level;//表中層數最大的節點的層數(表頭不計算在內)
} zskiplist;

（二）整數集合

整數集合是集合鍵的底層實現之一，當一個集合只包含整數值元素，並且集合的元素數量不多時，Redis就會使用整數集合作為集合鍵的底層實現，並且保證集合中不會出現重覆元素。

intset

typedef struct intset{
    uint32_t encoding;//編碼方式
    uint32_t length;//集合包含的元素數量。
    int8_t contents[];//保存元素的數組 
} intset;

contents數組是這個數集合的底層實現：整數集合的每個元素都是contents數組的一個數組項，各個項的數組中按值的大小從小到大有序地排列，並且數組中不包含任何重覆項。

升級

當我們要將一個新元素添加到整數集合裡面時，並且新元素類型比整數集合現有的所有元素類型都長時，整數集合需要先進性升級，然後才能將新的元素添加到整數集合中。

1、根據新元素的類型，擴展整數集合底層數組的空間大小，併為新元素分配空間。

2、將底層數組現有的所有元素都轉換為與新元素相同的類型，並將類型轉換後的元素放置到正確位置上，而且在放置元素過程中，需要繼續維持底層數組的有序性質不變。

3、將新元素添加到底層數組裡面。

4、修改整數集合encoding屬性。

因為每次向整數集合添加新元素都有可能引起升級，而每次升級都需要將底層數組中已有的所有元素進行類型轉換，所以向整數集合中添加新元素的時間複雜度為O(N);

---- end ----

每天學一點，總會有收穫。

說明：尊重作者知識產權，文中內容參考《Redis設計與實現》，僅在此做學習與大家分享。