學習使用Redis,其實並不需要去研究其底層數據的實現。我們只需要了解他有哪些常用的數據類型,然後熟練使用,就可以很好的掌握Redis 這個工具了。但是這樣的學習方法只適合Redis 的入門,“工欲善其事必先利其器”,我們想要用好Redis,則必須深入了解Redis 的底層到底是如何實現的,我們在選擇數據結構的時候才能做出正確的選擇。
在上一篇博客《深入淺出Redis-redis底層數據結構(上)》中,我們已經講解了Redis 中的 動態字符串,鏈表,字典
在這裡我們簡單回顧一下他們的特點:
1、動態字符串SDS:區別於C語言字符串,具有良好的伸縮性,在獲取字符串長度,字符串修改,防止緩存區溢出等性能都比C語言字符串好
2、鏈表:順序存儲對象信息,有用於緩存鏈表長度的屬性,在插入刪除對象功能中有良好性能,避免環的產生
3、字典:key-value 存儲方式,通過hash值計算,判斷key的存儲,當容量過大,會通過rehash重新分配字典大小
跳躍表(skiplist)是一種有序數據結構,它通過在每個節點中維持多個指向其他節點的指針,從而達到快速訪問節點的目的。跳躍表是一種隨機化的數據,跳躍表以有序的方式在層次化的鏈表中保存元素,效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在對數期望時間下完成,並且比起平衡樹來說,跳躍表的實現要簡單直觀得多。
Redis 只在兩個地方用到了跳躍表,一個是實現有序集合鍵,另外一個是在集群節點中用作內部數據結構。
我們先來看一下一整個跳躍表的完整結構:
Redis 的跳躍表 主要由兩部分組成:zskiplist(鏈表)和zskiplistNode (節點)
5.2.1 zskiplistNode(節點) 數據結構:
typedef struct zskiplistNode{
//層 struct zskiplistLevel{
//前進指針 struct zskiplistNode *forward;
//跨度 unsigned int span; } level[];
//後退指針 struct zskiplistNode *backward;
//分值 double score; //成員對象 robj *obj; }
1、層:level 數組可以包含多個元素,每個元素都包含一個指向其他節點的指針。
2、前進指針:用於指向表尾方向的前進指針
3、跨度:用於記錄兩個節點之間的距離
4、後退指針:用於從表尾向表頭方向訪問節點
5、分值和成員:跳躍表中的所有節點都按分值從小到大排序。成員對象指向一個字符串,這個字符串對象保存著一個SDS值
5.2. zskiplist 數據結構:
typedef struct zskiplist { //表頭節點和表尾節點 structz skiplistNode *header,*tail; //表中節點數量 unsigned long length; //表中層數最大的節點的層數 int level; }zskiplist;
從結構圖中我們可以清晰的看到,header,tail分別指向跳躍表的頭結點和尾節點。level 用於記錄最大的層數,length 用於記錄我們的節點數量。
《Redis 設計與實現》 中這樣定義整數集合:“整數集合是集合建的底層實現之一,當一個集合中只包含整數,且這個集合中的元素數量不多時,redis就會使用整數集合intset作為集合的底層實現。”
我們可以這樣理解整數集合,他其實就是一個特殊的集合,裡面存儲的數據只能夠是整數,並且數據量不能過大。
typedef struct intset{ //編碼方式 uint32_t enconding; // 集合包含的元素數量 uint32_t length; //保存元素的數組 int8_t contents[]; }
我們觀察一下一個完成的整數集合結構圖:
1、encoding:用於定義整數集合的編碼方式
2、length:用於記錄整數集合中變量的數量
3、contents:用於保存元素的數組,雖然我們在數據結構圖中看到,intset將數組定義為int8_t,但實際上數組保存的元素類型取決於encoding
在上述數據結構圖中我們可以看到,intset 在默認情況下會幫我們設定整數集合中的編碼方式,但是當我們存入的整數不符合整數集合中的編碼格式時,就需要使用到Redis 中的升級策略來解決
Intset 中升級整數集合並添加新元素共分為三步進行:
1、根據新元素的類型,擴展整數集合底層數組的空間大小,並為新元素分配空間
2、將底層數組現有的所有元素都轉換成新的編碼格式,重新分配空間
3、將新元素加入到底層數組中
比如,我們現在有如下的整數集合:
我們現在需要插入一個32位的整數,這顯然與整數集合不符合,我們將進行編碼格式的轉換,並為新元素分配空間:
第二步,將原有數據他們的數據類型轉換為與新數據相同的類型:(重新分配空間後的數據)
第三部,將新數據添加到數組中:
6.3.1 整數集合升級的好處
1、提升靈活性
2、節約內存
整數集合是集合建的底層實現之一
整數集合的底層實現為數組,這個數組以有序,無重復的范式保存集合元素,在有需要時,程序會根據新添加的元素類型改變這個數組的類型
升級操作為整數集合帶來了操作上的靈活性,並且盡可能地節約了內存
整數集合只支持升級操作,不支持降級操作
壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只把汗少量列表項,並且每個列表項要麼就是小整數,要麼就是長度比較短的字符串,那麼Redis 就會使用壓縮列表來做列表鍵的底層實現。
一個壓縮列表的組成如下:
1、zlbytes:用於記錄整個壓縮列表占用的內存字節數
2、zltail:記錄要列表尾節點距離壓縮列表的起始地址有多少字節
3、zllen:記錄了壓縮列表包含的節點數量。
4、entryX:要說列表包含的各個節點
5、zlend:用於標記壓縮列表的末端
壓縮列表是一種為了節約內存而開發的順序型數據結構
壓縮列表被用作列表鍵和哈希鍵的底層實現之一
壓縮列表可以包含多個節點,每個節點可以保存一個字節數組或者整數值
添加新節點到壓縮列表,可能會引發連鎖更新操作。