第一層面，從使用者的角度value有這幾種結構：
string、list、hash、set、sortedset
第二層面，從內部實現的角度，有如下幾種結構：
dict、sds、ziplist、quicklist、skiplist
Redis透過組合第一層面的資料結構來實現第二層面的資料結構
一、dict實現原理
在Redis中，dict是一個基於雜湊表的演算法，採用拉鍊法解決衝突，並在裝載因子超過預定值時自動擴充套件，引發重雜湊
重雜湊：這是一種增量試重雜湊，在需要擴充套件記憶體時避免一次性對所有key進行重雜湊，而是將重雜湊操作分散到對每個dict的各個增刪該查的操作中去，這種方法能做到每次只對一小部分key進行重雜湊，而每次重雜湊之間不影響dict的操作。之所以這樣設計是為了避免重雜湊期間單個請求的響應時間劇烈增加。
為了實現重雜湊，dict的資料結構裡包含兩個雜湊表ht［0］和ht［1］，在重雜湊期間，資料從第一個雜湊表向第二個雜湊表遷移， 當資料全部從ht［0］遷移到ht［1］上後，整個重雜湊就結束， ht［0］變成ht［1］的內容，而ht［1］則重置為空
此外，一個狀態rehashidx可標記當前重雜湊的狀態
下面分三種操作來說明底層執行的邏輯，分別是查詢、插入和刪除
共同點：三個操作都會觸發重雜湊過程向前推進至少n步，即重雜湊一部分key，從而將整個重雜湊分散到每個增刪改查操作中
每步重雜湊key的數量：一個bucket，即一個dictEntry連結串列（衝突連結串列）
a、dict查詢
從從ht［0］中查詢，如果找到則返回； 如果沒找到並且當前正在衝雜湊，則從ht［1］上查詢
b、dict插入
如果正在重雜湊，將資料插入到ht［1］，否則插入到ht［0］
c、dict刪除
如果正在重雜湊，則從ht［0］和ht［1］中查詢並刪除；否則從ht［0］中查詢並刪除
二、sds實現原理
全稱：Simple Dynamic String
這種儲存結構的特點：
可動態擴充套件記憶體，sds表示的字串其內容可以修改也可以追加
二進位制安全，sds能儲存任意二進位制資料，而不僅僅是可列印字元
sds字串的資料結構：
由兩部分組成，他們在記憶體地址上前後相鄰，從而節省記憶體
一個header， 通常包含字串的長度len、最大容量alloc和flags，但是sdshdr5有所不同，sds總共有5種類型的header
一個字元陣列，儲存真正的有效字串資料
這種結構的優點：
header和資料相鄰，不用分成兩塊記憶體空間來單獨分配，有利於減少記憶體碎片，提高儲存效率
sds的一些基礎函式：
* sdslen（const sds s）： 獲取sds字串長度。* sdssetlen（sds s， size_t newlen）： 設定sds字串長度。* sdsinclen（sds s， size_t inc）： 增加sds字串長度。* sdsalloc（const sds s）： 獲取sds字串容量。* sdssetalloc（sds s， size_t newlen）： 設定sds字串容量。* sdsavail（const sds s）： 獲取sds字串空餘空間（即alloc - len）。* sdsHdrSize（char type）： 根據header型別得到header大小。* sdsReqType（size_t string_size）： 根據字串資料長度計算所需要的header型別。
淺談sds和Redis的string型別的關係：
Redis的命令append底層用sds的sdscatlen實現
Redis的setbit和getrange命令都是先根據key取得整個sds字串，然後再從字串選取或修改制定的部分
上面說的是當value儲存的是字串時的情況；當value儲存的值是一個數字的時候，它會支援incr/decr操作，此時的內部儲存就不是sds了
三、robj實現原理（redisObject）
Redis中的資料的key都是string型別，value可以是多種型別，比如string，list，hash等
那麼這個從key到value的對映關係，內部是用一個前面講的dict來維護的，dict的key因為都是string型別，所以用sds來表達就足夠了， 而value比較複雜，為了在同一個dict內能儲存不同型別的value，就定義了一種通用的資料結構robj， 全名是redisObject
比如，如果value是一個list，那麼它的內部儲存結構是一個quicklist； 如果value是一個string，那麼它的內部儲存結構一般情況下是sds，當然實際更復雜一點，比如當string型別的value是數字時，redis內部還會把它轉換成long來節省記憶體
一個robj型別包含如下5個欄位：
type：物件的資料型別，可能的取值OBJ_STRING、OBJ_LIST、OBJ_SET、OBJ_ZSET、OBJ_HASH， 分別對應Redis對外暴露的5種資料結構encoding：物件的內部標識方式，不同的表示方式佔用的記憶體不同，對查詢效能也有影響lru：做lru演算法用refcount：引用計數，它允許robj物件在某些情況下被共享ptr：資料指標，指向真正的資料，比如一個代表string的robj，它的pt可能指向一個sds結構；一個代表list的robj，它的ptr可能指向一個quicklist
robj物件的作用：
為多種資料型別提供統一的表示方式
允許同一型別的資料採用不同的內部表示，從而在某些情況下儘量節省記憶體
支援物件共享和引用計數，當物件被共享的時候，只佔用一份記憶體複製，進一步節省空間
深談sds和Redis的string型別的關係：
確切的說，string在Redis中是用一個robj來表示的
用來表示string的robj，如果string是數字，那麼會被轉換成long儲存
在對string進行incr/decr等操作的時候，若內部是OBJ_ENCODING_INT編碼，則直接加減；否則，會先試圖把sds儲存的字串轉成long型再加減
在對一個內部表示成long型的string執行append、setbit或getrange操作的時候，針對的仍然是string的值（即仍然操作的是十進位制表示的字串）， 比如字串“32”，它是整數，執行這幾個操作的時候，直接操作的字串“32”對應位，而不是32對應的整形0x0000000000000020的位
四、ziplist實現原理
ziplist是一個經過特殊編碼的雙向連結串列，設計的目標是為了提高儲存效率，ziplist可以用於儲存字串或者整數，其中整數是按照二進位制表示進行編碼的，而不是編碼成字串序列。
ziplist不是普通的雙向連結串列， 普通的雙向連結串列每一項都佔用獨立的一塊記憶體，各項之間用地址指標連線起來，這會造成大量的記憶體碎片，而且地址指標也佔用額外的記憶體。 ziplist是將表中每一項放在前後連續的地址空間中，一個ziplist整體佔用一大塊記憶體，它是一個表（list）， 但其實不是一個連結串列
另外，ziplist為了在細節上節省記憶體，對於值的儲存採用了變長的編碼方式，即對於大的整數，就多用一些位元組來儲存，對於小的整數就少用一些位元組存
ziplist的資料結構定義：
這各個部分在記憶體上是前後相鄰的
。
再來看下
hash與ziplist的關係：
hash結構隨著資料量的增大，其底層資料結構的實現會發生變化，儲存效率也就不同了
在hash中field比較少時，各個value值也比較小的時候，hash採用ziplist來實現；而隨著field增多和value值增大，hash可能會變成dict來實現。
那麼到底插入多少後才會從ziplist轉成dict呢？ 跟redis的如下兩個配置有關：
hash-max-ziplist-entries 512 hash-max-ziplist-value 64
Redis的hash這樣設計的原因，是因為ziplist變得很大的時候，它有如下缺點：
。每次插入或修改引發的realloc（擴容）操作會有更大的機率造成記憶體複製，從而降低效能。一旦發生記憶體複製，記憶體複製的成本也相應增加，因為要複製更大的一塊資料。當ziplist資料項過多的時候，在它上面查詢指定的資料項就會效能變得很低，因為ziplist上的查詢需要進行遍歷
五、quicklist實現原理
Redis對外暴露的List資料型別，底層實現用的就是quicklist
quicklist的實現是一個雙向連結串列，連結串列的每一個節點都是一個ziplist， 為什麼quicklist要這樣設計呢？ 其實也是一個空間和時間的折中
。雙向連結串列便於在表的兩端進行push和pop操作，但是它的記憶體開銷比較大。 首先它在每個節點上除了要儲存資料之外，還要額外儲存兩個指標；其次雙向連結串列的各個節點是單獨的記憶體塊，地址不連續，節點多了容易產生記憶體碎片
。ziplist由於是一整塊連續記憶體，所以儲存效率很高，但是它不利於修改操作，每次資料變動都會引發一次記憶體的realloc。特別是當ziplist長度很長的時候，一次realloc可能會導致大批次的資料複製，進一步降低效能
這樣設計的問題， 到底一個quicklist節點包含多長的ziplist合適？這是一個找平衡的問題：
。每個quicklist節點上的ziplist越短，則記憶體碎片越多，極端情況是一個ziplist只包含一個數據項，這就退化成了普通的雙向連結串列
。每個quicklist節點上的ziplist越長，則為一個ziplist分配大塊連續記憶體的難度就越大，有可能出現記憶體裡有很多小塊的記憶體空間，但卻找不到一塊足夠大的空閒空間分給ziplist。極端情況是整個quicklist只有一個節點，這就退化成了一個ziplist了
這個平衡問題可基於如下Redis引數配置：
list-max-ziplist-size -2
六、skiplist（跳躍表）
skiplist是為了實現sorted set這種對外的資料結構， 其結構如下：
比較好的策略是：上下相鄰的兩層連結串列節點個數的關係是2：1， 如果要維護這種比例關係，當插入節點的時候，就需要把它後面的所有節點重新調整，刪除也是，這會讓時間複雜度蛻化成O（n）。
skiplist採用的策略：它不要求上下相鄰兩層連結串列之間的節點個數有嚴格的對應關係，而是為每個新插入的節點隨機出一個層數， 因此插入操作只需要修改插入節點前後的指標，而不需要對很多節點進行調整，這降低了複雜度，這是它在插入效能上明顯優於平衡樹的方案
實際應用中skiplist每個節點應該包含key和value兩部分，列表是按照key進行排序的，查詢過程也是根據key在比較
在Redis中，skiplist被用於實現暴露給外部的sorted set，但是準確的說，sorted set底層不僅適用了skiplist，還是用了ziplist和dict
總結來說：
。當資料較少時，sorted set是用一個ziplist來實現，插入時插入兩個資料項：資料在前，score在後，查詢時順序查詢
。當資料多的時候，sorted set由zset實現，即由一個dict+一個skiplist來實現。 dict用來查詢資料到分數的對應關係，而skiplist用來根據分數查詢資料（可能是範圍查詢）
那麼什麼時候開始切換實現方式呢？ 基於如下兩個配置：兩個條件滿足一個就會切換zset
zset-max-ziplist-entries 128zset-max-ziplist-value 64
zset的結構定義如下： 可以看到它就是基於dict+ziplist
typedef struct zset { dict *dict； zskiplist *zsl；} zset；
另外，Redis中對skiplist做了擴充套件： （Redis中的skiplist和經典的skiplist的比較）
。分數允許重複，即skiplist的key允許重複（分數是skiplist中的key），這在經典的skiplist中是不允許的
。在比較時，不僅比較分數（skiplist的key），還比較資料本身
。第1層連結串列不是一個單向連結串列，而是一個雙向連結串列，這是為了方便以倒序方式獲取一個範圍內的元素
七、intset實現原理
它是整數的集合，確切的說是整陣列成的有序集合，從而便於在上面進行二分查詢，從而快速判斷一個元素是否屬於這個集合，它在記憶體分配上與ziplist類似，是連續的一整塊記憶體空間， 並且對於大整數和小整數採取不同的編碼，進來對記憶體進行最佳化， 其結構如下：
typedef struct intset { uint32_t encoding； uint32_t length； int8_t contents［］；} intset；
encoding：資料編碼，表示每個整數用幾個位元組來儲存length：表示intset中的元素個數contents：資料元素
intset和ziplist的比較：
。ziplist可以儲存任意二進位制串，intset只能儲存整數
。ziplist是無序的，而intset是從小到大有序的，因此在ziplist上查詢只能遍歷，而在intset上可以進行二分查詢，效能更高
。ziplist可以對每個資料項進行不同的變長編碼，而intset只能整體用一個統一的編碼， 所以intset隨著新元素的新增，需要根據元素大小決定是否對資料編碼進行升級
Redis的Set的底層實現：
。當Set中新增的元素都是整型切元素資料較少時，Set使用intset作為底層資料結構
。否則，Set底層使用dict作為資料結構（即元素不是整型或者元素是整型但是資料已經較多了用dict）
這透過如下引數來配置：
set-max-intset-entries 512
最後總結下第一層面的資料型別和第二層面的資料型別對應關係：
