介紹
redis是一種常用的記憶體資料庫，對於使用者如果能從底層瞭解到各種資料型別的底層原理，可以讓我們能在特定的業務場景下選擇正確的資料型別。同時redis資料型別也是面試中頻繁出現的面試題，接下來大家可以帶著以下幾個問題來閱讀整篇文章。
各種結構，讀寫一條資料的時間複雜度是多少？
為什麼不同redis版本有不同的底層實現？
為什麼一種資料型別有多種底層實現？
原理
字串
字串型別是我用過最多的型別，使用的場景有：快取資料資訊、分散式鎖、計數器等。在Redis實現中並沒有直接採用C語言的字串，而是自定義了一個SDS（簡單動態字串）的結構體來標識字串。
在C語言中定義字串 char *str = "message"它會儲存如下圖的樣子：
以“\0”代表結束。這樣就會產生以下問題：
無法儲存“\0”這種特殊字元，因為“\0”代表結束；
每次字串擴容和縮容，都需要使用新的char陣列；
沒有記錄字串的長度，每次都需要進行遍歷到結束才能知道長度。
redis要解決上述問題，就自定義了一個SDS結構，如下圖：
len：目前已使用的長度；
alloc：buf的總長度，就是已經分配空間的長度;
flags：sds的型別，用低三位標識，高5位暫時不用。sdshdr5這種型別該欄位為空；sdshdr8、sdshdr16、sdshdr32、sdshdr64用標識進行表示。
buf：儲存具體的字串。注意這裏也會以\0結尾，但它不會計算在len中。
可以看到redis可以根據字串的大小使用不同型別的sds，這樣可以進一步的節省記憶體。這裏不需要擔心buf的長度不夠用，2的64次冪是一個非常巨大的數字，同時redis預設也會限制最大的字元為512M，在6.3版本開始可以對最大限制字元大小進行配置。注意：使用不同型別的sds並不是一次性分配這麼多空間，而是逐步分配的，例如：使用sdshdr16這種型別，存入一個長度為14的字串，那麼會根據存入的字串長度預留空閒長度，這裏是14；如果字串大小超過1M，那麼預留空間就是1M。
redis除了自定義了SDS型別來儲存字串，還定義了三種編碼：
int：8位元組的長整形，值時數字型別，並且數字長度小於20；
embstr：長度小於等於44位元組的字串；（3.2版本之前是39位元組）
raw：長度大於44位元組的字串。
List
List與java中的list類似，是一種線性有序的數據結構，可以透過：
LINDEX listKey 0獲取頭元素；LINDEX listKey -1獲取尾部元素。
這裏我們既可以把它當作佇列，也可以當作棧來使用。在C語言中並沒有執行緒的list，redis只好自己來實現一個list結構；對於list的底層結構，redis的不同版本採用的並不完全相同，它是從linkedlist、ziplist、quicklist、listpack一點點演進出來的。
linkedlist
它是3.2版本之前的實現，以下是它的部分程式碼定義：
typedef struct list {
// 頭指標
listNode *head;
// 尾指標
listNode *tail;
// 連結串列長度
unsigned long len;
} list;
typedef struct listNode {
// 前置指標
struct listNode *prev;
// 後值置針
struct listNode *next;
// 值
void *value;
} listNode;
透過上述程式碼可以知道，這就是一個雙端連結串列；爲了大家看的更清晰，這裏我畫了一張圖來表示:
根據圖大家可以看的更清晰會發現兩個問題：
就想存一個值，結果還要儲存各種指標，如果值比較小的話，指標佔用的空間比值還多；
找一個值需要逐個遍歷，但整個連結串列空間不是連續的這樣查詢的效率很低。
ziplist
爲了解決linkedlist存在的問題，redis還定義了另一個數據結構ziplist，在3.2版本之前，List的底層資料型別就由這兩個數據結構組成，當滿足以下兩種情況就會使用ziplist數據結構：
list中的每個元素佔用的位元組數都小於64；
list中的元素數量小於512個。
它的結構程式碼如下：
struct ziplist<T> {
// 整個壓縮列表佔用位元組數
int32 zlbytes;
// 最後一個元素距離壓縮列表起始位置的偏移量，用於快速定位到最後一個節點
int32 zltail_offset;
// 元素個數
int16 zllength;
// 元素內容列表，挨個挨個緊湊儲存
T[] entries;
// 標誌壓縮列表的結束，值恆為 0xFF
int8 zlend;
}
struct entry {
// 前一個 entry 的位元組長度
int<var> prevlen;
// 元素型別編碼
int<var> encoding;
// 元素內容
optional byte[] content;
}
讓我們來看一下ziplist的結構圖：
zlbytes：整個ziplist佔用的位元組數；（佔用4位元組空間）
zltail_offset：指向最後一個entry的偏移量；（佔用4位元組）
zllength：entry的總數；（佔用2位元組）
entry：存放的元素；
zlend：結束表示（值為255）。（佔用1位元組）
prevlen：記錄前一個entry佔用的位元組數，它佔用的位元組會根據上一個entry的長度改變而改變；
encoding：表示當前entry的型別和長度；當前兩位為11時，標識int型別資料，此時content中的資料內容也會儲存在encoding中；
content：實際存放資料的區域。
透過上圖可以瞭解到ziplist佔用一定的連續空間。這樣可以節省linkedlist中前後指標消耗的記憶體；同時記錄了上一個節點的prevlen，這樣每次都可以查詢上一個節點，上一個節點的開頭就是prevlen，可以節約查詢時間；同時對於int、string採用了不同的編碼進一步節約記憶體。
但ziplist查詢第k個數據還是需要進行全部遍歷，它的時間複雜度還是O(N)；由於空間是連續的插入新的entry時，如果沒有足夠連續的空間就需要再重新分配一塊連續的記憶體空間；prevlen還會隨著前一個entry的大小的改變而改變，當最前面的entry大小改變了還可能會導致連鎖更新把後面的entry全部更新了。
quicklist
quicklist是在3.2版本引進的，它結合了linkedlist和ziplist的優缺點，把他們兩個合併起來，整體上是一個linkedlist，每個節點是一個ziplist，
程式碼如下：
typedef struct quicklist {
// 頭指標
quicklistNode *head;
// 尾指標
quicklistNode *tail;
// 元素總數
unsigned long count;
// node的個數
unsigned long len;
......省略......
} quicklist;
typedef struct quicklistNode {
// 前置節點
struct quicklistNode *prev;
// 後置節點
struct quicklistNode *next;
// 指向ziplist的指標
unsigned char *entry;
// 位元組大小
size_t sz;
// ziplist中元素個數
unsigned int count : 16;
// 編碼格式，1=RAW,2=LZF（壓縮）
unsigned int encoding : 2;
......省略......
} quicklistNode;
下圖只是簡單的把linkedlist和ziplist合併起來的，和真實的quicklist有些差別如圖：
這樣的好處是可以控制每個ziplist的元素個數，控制好個數發生ziplist存在的問題時可以把影響降低；我們可以根據list-max-ziplist-size來控制ziplist的元素個數。 同時每個quicklistNode還儲存了當前節點包含元素的總數，這樣查詢第k個元素時的時間複雜度就時O(logN)。
listpack
quicklist只能降低ziplist帶來的影響，但依舊無法解決這些問題，所以在5.0版本時推出了listpack，並且在7.0版本中替換掉了ziplist，它也是一種使用連續記憶體空間來儲存資料的數據結構，並且使用多種編碼來節省記憶體空間。它的內部結構如下圖：
tot-bytes：記錄listpack佔用的總位元組數（佔用4位元組）；
num-elements：記錄element的個數（佔用2位元組）；
elements：儲存的元素；
listpack-end-byte：結束標識（1位元組）；
encoding-type：存放data部分的編碼型別和長度；
element-data：實際存放的資料；
element-tot-len：encoding-type + element-data的長度，不包含自身。
上述就是redis中list型別的進化過程。
Set
set結構類似java中的set，是一個無序並且元素唯一的集合。它的底層是透過map和intset來實現的。
intset
當set中的元素都是64位以內的整數，並且元素的數量不超過512就會使用intset結構來儲存。元素數量可以透過set-max-intset-entries來調整。intset結構程式碼：
typedef struct intset {
// 編碼方式，用於表示儲存的整數型別。
uint32_t encoding;
// intset 中包含的元素個數
uint32_t length;
// 儲存整數的陣列，是一塊連續記憶體區域，陣列中元素會按照從小到大儲存。
int8_t contents[];
} intset;
這個結構相對簡單，這裏就不畫圖描述了。要注意encoding分為int16_t、int32_t、int64_t，如果之前的元素都是int16_t，此時插入一個int64_t會導致所有的元素的型別都升級為int64_t，只能升級不能降級。而儲存的內容是連續的，這樣就可以透過二分法進行查詢，它的時間複雜度就可以最佳化到O(logN)。
map
map中的key就是set的值，map中的value為null。
Map
它類似於java的map集合，儲存的是N對fieId-value集合，它的底層由dict和ziplist(7.0之前)以及listpack三種數據結構組成。
ziplist、listpack
上面已經介紹過ziplist、listpack了，這裏不再詳細介紹。redis會把fieId和value組成一個entry進行儲存的，同時redis會對這兩個值前面加標識位的以便區分entry中哪一段是fieId 哪一段是value。使用這兩種數據結構時需要滿足如下條件:
每個fieId-value中的fieId和value的位元組都要小於
hash-max-listpack-value（預設64）；儲存的fieId-value數量小於
hash-max-listpack-entries（預設512）。
dict
由陣列和連結串列構成，陣列元素佔用的槽位叫做hash桶，當出現hash衝突時就在這個桶下面掛連結串列；
解決hash衝突的三種方法：連結串列法，開放地址法，再hash法。
dict實體程式碼如下：
struct dict {
// 型別 包括一些自定義函式 這些自定義函式使得key和value能夠儲存
dictType *type;
// 私有資料
dictEntry **ht_table[2];
// 兩張hash表
unsigned long ht_used[2];
// 漸進式hash標記 如果為-1 說明沒有在hash
long rehashidx;
int16_t pauserehash;
} dict;
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下一個 hash 節點
struct dictEntry *next;
} dictEntry;
爲了方便大家理解，我畫了一張圖可以先看一下：
type：存放函式的結構體（計算雜湊值函式、複製鍵的函式、複製值的函式等）；
ht_table：存放大小為2的雜湊表陣列，每個指標指向一個dictEntry陣列（預設初始大小為4）；
ht_used：記錄每個dictEntry用了多少槽位；
rehashidx：rehash標記位；
pauserehas：表示rehash的狀態；
key：fieId，是一個SDS型別；
v：具體的值；其中val是非數字型別時使用該指標儲存；u64是無符號整數時使用的儲存；s64是由符號整數時使用的儲存；d是浮點數時使用的儲存;
next：當爲連結串列時指向下一個dictEntry。
擴容和縮容
熟悉java的都知道hashMap和currentHashMap的擴容、縮容，那麼redis肯定也有擴容和縮容。擴縮容時機：
當前沒有執行備份命令
bgsave或bgrewriteaof時，負載因子大於等於1；當前執行備份命令
bgsave或bgrewriteaof時，負載因子大於等於5；負載因子 = dictEntry總數 / 雜湊桶個數；
每次擴容，擴容後的容量是使用桶數的2倍往上找到第一個接近2的N次冪的數字；縮容同理。例如現在使用數量為17，那麼擴容後的陣列為32。
當databaseCron定時執行時檢測到元素個數低於雜湊桶分配的個數的10%時，進行縮容。
當前執行備份命令
bgsave或bgrewriteaof等操作時不可縮容。
對於redis擴容，是一個漸進式擴容，它的擴容過程：
1、rehashidx設定為0，表示正在擴容；
2、在rehash時，每次處理對dict雜湊表執行命令時都會檢查是否處於擴容狀態，如果是就把ht_table[0]上的元素rehash到ht_table[1]中，並將rehashidx的值加1。
3、上述操作直至全部遷移完成，把rehashidx設定為-1，並把ht_table[0]指向ht_table[1],同時清空原table。
4、redis也有一個定時函式，用於幫助遷移防止一直漏掉一些entry導致無法遷移完成，此時會一直維護兩個table，進而影響redis效能。
Sorted Set
sorted set和set類似，都是儲存一堆不可重複的集合，他們的區別在於sorted set是有序的，它由兩部分member和score組成，如果score相同，則按照member字串的字典順序排序。它的底層結構分為dict+skiplist、ziplist(7.0之前)和listpack組成。
ziplist、listpack
ziplist、listpack這兩個數據結構上面有介紹，這裏就不再詳細介紹它倆了。zset會把member和score組成一個entry，redis會對這兩個值前面加標識位的以便區分entry中哪一段是member 哪一段是score；同時還會按照score對entry進行排序；當符合以下兩個條件會使用ziplist、listpack：
集合元素小於等於zset-max-listpack-entries（預設為128）;
member佔用位元組數小於等於zset-max-listpack-value（預設為64）。
skiplist + dict
sorted set在這裏是採用兩種型別儲存，其實是一種以空間換時間的最佳化。它會分別在skiplist和dict中儲存資料。
dict
把member儲存在key中，把score儲存在value中；這樣對於ZSCORE key member命令而言就是O(1)時間複雜度的。
skiplist
skiplist(跳錶)就是多層級有序連結串列（最多32層），上層是下層的索引，相比B-樹，b+ 樹等更消耗記憶體，但它實現起來更簡單不需要維護複雜的樹形結構。 程式碼如下：
//跳躍表節點
typedef struct zskiplistNode {
// 成員物件[必須唯一]
sds ele;
// 分值[用來排序][可以相同]
double score;
// 後退指標用於從表頭向表尾遍歷
struct zskiplistNode *backward;
// 陣列
struct zskiplistLevel { // 層
struct zskiplistNode *forward; // 前進指標
unsigned long span;// 跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
// 指向表頭節點和表尾節點
struct zskiplistNode *header, *tail;
// 表中節點的數量
unsigned long length;
// 表中層數最大的節點的層數
int level;
} zskiplist;
結構圖如下：
當想查詢節點6時，先從l3層查詢，查詢節點1、節點5，第3層後面是null，第2層後面是7，此時查詢第1層就查詢到節點6了。注意：一個節點是存在於多層的。
redis中不會嚴格要求跳錶中兩層的數量比例，這樣在插入的過程中維護層級比較消耗效能，它是採用隨機的方式來告訴節點要出現在哪層，如果沒有則建立一層，如果刪除節點剛好該層沒有節點則刪除該層。同時在zskiplistLevel中會記錄下來span跨度，這樣我們在查詢資料時只需要把經過的跨度都加起來就知道這條資料在整體中的排名了。
總結
以前看過很多篇介紹redis資料型別的，但幾乎都是描述一下哪些資料型別用了哪些資料型別，並沒有詳細說明為什麼以及每個數據結構是什麼樣子的，這樣就很難形成長期記憶，讀完本文了解了每個數據結構也就很容易記住redis的這些資料型別都採用了什麼數據結構了。
各種資料型別，讀寫一條資料的時間複雜度是多少？
每種資料型別採用的數據結構不同，當使用不同數據結構時他們的時間複雜度也不同，具體可以參考文章描述。
為什麼不同redis版本有不同的底層實現？
其實底層實現更改的只有linkedlist以及ziplist，因為ziplist會導致連鎖更新，linkedlist中前後指標佔用太多內容，同時記憶體不連續查詢效能慢，時間複雜度為O（n）.
為什麼一種資料型別有多種底層實現?
因為redis是一種記憶體型資料庫，比較吃記憶體，多種底層實現可以節約記憶體使用。
