聊一聊Redis之數據結構-魔扣目錄

基本數據結構

簡單動態字符串

redis中的字符串使用“簡單動態字符串”（SDS）表示，無論是字符串值還是鍵底層都采用“簡單動態字符串”。

free：未使用空間大小；
len：字符串長度；
buf：以空字符結尾的char數組。

為了減少內存重新分配次數，SDS做出了以下優化：

空間預分配：額外分配的未使用空間數量由以下公式決定：如果對SDS進行修改之后，SDS的長小于1MB，那么程序分配和len 屬性同樣大小的未使用空間，如果對SDS進行修改之后，SDS的長度將大于等千1MB, 那么程序會分配 1MB 的未使用空間。
惰性空間釋放：程序并不立即使用內存重分配來回收縮短后多出來的字節，而是使用free屬性將這些字節的數量記錄起來，并等待將來使用。

鏈表

鏈表是Redis列表鍵實現之一，也是很多其他功能實現的基礎，鏈表節點定義如下：

鏈表的完整結構體定義如下

head為表頭指針；
tail為表尾指針；
len為鏈表長度計數器；
dup為函數指針，用于復制鏈表節點所保存的值；
free為函數指針，用于釋放鏈表節點所保存的值；
match為函數指針，則用于對比鏈表節點所保存的值和另一個輸入值是否相等。

字典

字典將鍵和值進行關聯，當哈希鍵中的鍵值對數量比較多，或者鍵值對中的元素比較大的時候，采用字典作為底層實現。字節的數據結構如下

哈希表結構dict中，table屬性是一個數組，每個元素都是指向dictEntry結構的指針，size屬性記錄了哈希表的大小，sizemask屬性的值總是等于size-1，而used屬性則記錄了哈希表目前已有節點（鍵值對）的數量。

字典結構dictType中有兩個哈希表ht[0]和ht[1]，ht[l]哈希表只會在對 ht[0]哈希表進行rehash時使用，rehashidx它記錄了rehash目前的進度。type屬性是一個指向dictType結構的指針，dictType結構保存了一簇用于操作特定類型鍵值對的函數，例如計算哈希值、復制鍵、復制值、對比鍵、銷毀鍵和銷毀值的函數。而privdata屬性則保存了需要傳給那些類型特定函數的可選參數。

為了讓哈希表的負載因子維持在一個合理的范圍之內，當哈希表保存的鍵值對數量太多或者太少時，程序需要對哈希表的大小進行相應的擴展或者收縮。

如果執行的是擴展操作，那么ht[l]的大小為第一個大于等于ht[0].used*2的；
如果執行的是收縮操作，那么ht[1]的大小為第一個大于等于ht[O].used的。

字典采用漸進式rehash，好處在千它采取分而治之的方式，將 rehash鍵值對所需的計算工作均攤到對字典的每個添加、刪除、查找和更新操作上。

跳躍表

跳躍表可以用于有序集合鍵的底層實現，數據結構如下

zskiplist結構包含以下屬性：

header: 指向跳躍表的表頭節點。
tail: 指向跳躍表的表尾節點。
level: 記錄目前跳躍表內，層數最大的那個節點的層數。
length: 記錄跳躍表的長度。

zskiplistNode 結構，該結構包含以下屬性：

層 (level) : 每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節點，而跨度則記錄了前進指針所指向節點和當前節點的距離。
后退 (backward) 指針：指向位于當前節點的前一個節點。
分值 (score): 節點按各自所保存的分值從小到大排列。
成員對象 (obj): 節點所保存的成員對象。

整數集合

當一個集合只包含整數值元素，并且這個集合的元素數董不多時， Redis 就會使用整數集合作為集合鍵的底層實現。

contents數組是整數集合的底層數據存放位置，各個項在數組中按值的大小從小到大有序地排列，并且數組中不包含任何重復項。length屬性記錄了整數集合包含的元素數量，encoding屬性決定了整數類型（INTSET_ENC_INT16/INTSET_ENC_INT32/INTSET_ENC_INT64）。新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級。