大家好，我是小林。
Redis 為什麼那麼快？
除了它是記憶體資料庫，使得所有的操作都在記憶體上進行之外，還有一個重要因素，它實作的資料結構，使得我們對資料進行增删查改操作時，Redis 能高效的處理。
是以，這次我們就來好好聊一下 Redis 資料結構，這個在面試中太常問了。
注意，Redis 資料結構并不是指 String（字元串）對象、List（清單）對象、Hash（哈希）對象、Set（集合）對象和 Zset（有序集合）對象，因為這些是 Redis 鍵值對中值的資料類型，也就是資料的儲存形式，這些對象的底層實作的方式就用到了資料結構。
我畫了一張 Redis 資料類型（也叫 Redis 對象）和底層資料結構的對應關圖，左邊是 Redis 3.0版本的，也就是《Redis 設計與實作》這本書講解的版本，現在看還是有點過時了，右邊是現在 Github 最新的 Redis 代碼的（還未釋出正式版本）。
- 在 Redis 3.0 版本中 List 對象的底層資料結構由「雙向連結清單」或「壓縮表清單」實作，但是在 3.2 版本之後，List 資料類型底層資料結構是由 quicklist 實作的；
- 在最新的 Redis 代碼（還未釋出正式版本）中，壓縮清單資料結構已經廢棄了，交由 listpack 資料結構來實作了。
這次，小林把新舊版本的資料結構說圖解一遍，共有 9 種資料結構：SDS、雙向連結清單、壓縮清單、哈希表、跳表、整數集合、quicklist、listpack。
不多 BB 了，直接發車！
鍵值對資料庫是怎麼實作的？
在開始講資料結構之前，先給介紹下 Redis 是怎樣實作鍵值對（key-value）資料庫的。
Redis 的鍵值對中的 key 就是字元串對象，而 value 可以是字元串對象，也可以是集合資料類型的對象，比如 List 對象、Hash 對象、Set 對象和 Zset 對象。
舉個例子，我這裡列出幾種 Redis 新增鍵值對的指令：
> SET name "xiaolincoding"
OK
> HSET person name "xiaolincoding" age 18
0
> RPUSH stu "xiaolin" "xiaomei"
(integer) 4
這些指令代表着：
- 第一條指令：name 是一個字元串鍵，因為鍵的值是一個字元串對象；
- 第二條指令：person 是一個哈希表鍵，因為鍵的值是一個包含兩個鍵值對的哈希表對象；
- 第三條指令：stu 是一個清單鍵，因為鍵的值是一個包含兩個元素的清單對象；
這些鍵值對是如何儲存在 Redis 中的呢？
Redis 是使用了一個「哈希表」儲存所有鍵值對，哈希表的最大好處就是讓我們可以用 O(1) 的時間複雜度來快速查找到鍵值對。哈希表其實就是一個數組，數組中的元素叫做哈希桶。
Redis 的哈希桶是怎麼儲存鍵值對資料的呢？
哈希桶存放的是指向鍵值對資料的指針（dictEntry*），這樣通過指針就能找到鍵值對資料，然後因為鍵值對的值可以儲存字元串對象和集合資料類型的對象，是以鍵值對的資料結構中并不是直接儲存值本身，而是儲存了 void * key 和 void * value 指針，分别指向了實際的鍵對象和值對象，這樣一來，即使值是集合資料，也可以通過 void * value 指針找到。
我這裡畫了一張 Redis 儲存鍵值對所涉及到的資料結構。
這些資料結構的内部細節，我先不展開講，後面在講哈希表資料結構的時候，在詳細的說說，因為用到的資料結構是一樣的。這裡先大概說下圖中涉及到的資料結構的名字和用途：
- redisDb 結構，表示 Redis 資料庫的結構，結構體裡存放了指向了 dict 結構的指針；
- dict 結構，結構體裡存放了 2 個哈希表，正常情況下都是用「哈希表1」，「哈希表2」隻有在 rehash 的時候才用，具體什麼是 rehash，我在本文的哈希表資料結構會講；
- ditctht 結構，表示哈希表的結構，結構裡存放了哈希表數組，數組中的每個元素都是指向一個哈希表節點結構（dictEntry）的指針；
- dictEntry 結構，表示哈希表節點的結構，結構裡存放了 void * key 和 void * value 指針， *key 指向的是 String 對象，而 *value 則可以指向 String 對象，也可以指向集合類型的對象，比如 List 對象、Hash 對象、Set 對象和 Zset 對象。
特别說明下，void * key 和 void * value 指針指向的是 Redis 對象，Redis 中的每個對象都由 redisObject 結構表示，如下圖：
對象結構裡包含的成員變量：
- type，辨別該對象是什麼類型的對象（String 對象、 List 對象、Hash 對象、Set 對象和 Zset 對象）；
- encoding，辨別該對象使用了哪種底層的資料結構；
- ptr，指向底層資料結構的指針。
我畫了一張 Redis 鍵值對資料庫的全景圖，你就能清晰知道 Redis 對象和資料結構的關系了：
接下裡，就好好聊一下底層資料結構！
SDS
字元串在 Redis 中是很常用的，鍵值對中的鍵是字元串類型，值有時也是字元串類型。
Redis 是用 C 語言實作的，但是它沒有直接使用 C 語言的 char* 字元數組來實作字元串，而是自己封裝了一個名為簡單動态字元串（simple dynamic string，SDS） 的資料結構來表示字元串，也就是 Redis 的 String 資料類型的底層資料結構是 SDS。
既然 Redis 設計了 SDS 結構來表示字元串，肯定是 C 語言的 char* 字元數組存在一些缺陷。
要了解這一點，得先來看看 char* 字元數組的結構。
C 語言字元串的缺陷
C 語言的字元串其實就是一個字元數組，即數組中每個元素是字元串中的一個字元。
比如，下圖就是字元串“xiaolin”的 char* 字元數組的結構：
沒學過 C 語言的同學，可能會好奇為什麼最後一個字元是“\0”？
在 C 語言裡，對字元串操作時，char * 指針隻是指向字元數組的起始位置，而字元數組的結尾位置就用“\0”表示，意思是指字元串的結束。
是以，C 語言标準庫中的字元串操作函數就通過判斷字元是不是 “\0” 來決定要不要停止操作，如果目前字元不是 “\0” ，說明字元串還沒結束，可以繼續操作，如果目前字元是 “\0” 是則說明字元串結束了，就要停止操作。
舉個例子，C 語言擷取字元串長度的函數
strlen
，就是通過字元數組中的每一個字元，并進行計數，等遇到字元為 “\0” 後，就會停止周遊，然後傳回已經統計到的字元個數，即為字元串長度。下圖顯示了 strlen 函數的執行流程：
很明顯，C 語言擷取字元串長度的時間複雜度是 O（N）（這是一個可以改進的地方）
C 語言字元串用 “\0” 字元作為結尾标記有個缺陷。假設有個字元串中有個 “\0” 字元，這時在操作這個字元串時就會提早結束，比如 “xiao\0lin” 字元串，計算字元串長度的時候則會是 4，如下圖：
是以，除了字元串的末尾之外，字元串裡面不能含有 “\0” 字元，否則最先被程式讀入的 “\0” 字元将被誤認為是字元串結尾，這個限制使得 C 語言的字元串隻能儲存文本資料，不能儲存像圖檔、音頻、視訊文化這樣的二進制資料（這也是一個可以改進的地方）
另外， C 語言标準庫中字元串的操作函數是很不安全的，對程式員很不友好，稍微一不注意，就會導緻緩沖區溢出。
舉個例子，strcat 函數是可以将兩個字元串拼接在一起。
c //将 src 字元串拼接到 dest 字元串後面 char *strcat(char *dest, const char* src);
C 語言的字元串是不會記錄自身的緩沖區大小的，是以 strcat 函數假定程式員在執行這個函數時，已經為 dest 配置設定了足夠多的記憶體，可以容納 src 字元串中的所有内容，而一旦這個假定不成立，就會發生緩沖區溢出将可能會造成程式運作終止，（這是一個可以改進的地方）。
而且，strcat 函數和 strlen 函數類似，時間複雜度也很高，也都需要先通過周遊字元串才能得到目标字元串的末尾。然後對于 strcat 函數來說，還要再周遊源字元串才能完成追加，對字元串的操作效率不高。
好了， 通過以上的分析，我們可以得知 C 語言的字元串不足之處以及可以改進的地方：
- 擷取字元串長度的時間複雜度為 O（N）；
- 字元串的結尾是以 “\0” 字元辨別，字元串裡面不能包含有 “\0” 字元，是以不能儲存二進制資料；
- 字元串操作函數不高效且不安全，比如有緩沖區溢出的風險，有可能會造成程式運作終止；
Redis 實作的 SDS 的結構就把上面這些問題解決了，接下來我們一起看看 Redis 是如何解決的。
SDS 結構設計
下圖就是 Redis 5.0 的 SDS 的資料結構：
結構中的每個成員變量分别介紹下：
- len，記錄了字元串長度。這樣擷取字元串長度的時候，隻需要傳回這個成員變量值就行，時間複雜度隻需要 O（1）。
- alloc，配置設定給字元數組的空間長度。這樣在修改字元串的時候，可以通過
alloc - len
- flags，用來表示不同類型的 SDS。一共設計了 5 種類型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，後面在說明差別之處。
- buf[]，字元數組，用來儲存實際資料。不僅可以儲存字元串，也可以儲存二進制資料。
總的來說，Redis 的 SDS 結構在原本字元數組之上，增加了三個中繼資料：len、alloc、flags，用來解決 C 語言字元串的缺陷。
O（1）複雜度擷取字元串長度
C 語言的字元串長度擷取 strlen 函數，需要通過周遊的方式來統計字元串長度，時間複雜度是 O（N）。
而 Redis 的 SDS 結構因為加入了 len 成員變量，那麼擷取字元串長度的時候，直接傳回這個成員變量的值就行，是以複雜度隻有 O（1）。
二進制安全
因為 SDS 不需要用 “\0” 字元來辨別字元串結尾了，而是有個專門的 len 成員變量來記錄長度，是以可存儲包含 “\0” 的資料。但是 SDS 為了相容部分 C 語言标準庫的函數， SDS 字元串結尾還是會加上 “\0” 字元。
是以， SDS 的 API 都是以處理二進制的方式來處理 SDS 存放在 buf[] 裡的資料，程式不會對其中的資料做任何限制，資料寫入的時候時什麼樣的，它被讀取時就是什麼樣的。
通過使用二進制安全的 SDS，而不是 C 字元串，使得 Redis 不僅可以儲存文本資料，也可以儲存任意格式的二進制資料。
不會發生緩沖區溢出
C 語言的字元串标準庫提供的字元串操作函數，大多數（比如 strcat 追加字元串函數）都是不安全的，因為這些函數把緩沖區大小是否滿足操作需求的工作交由開發者來保證，程式内部并不會判斷緩沖區大小是否足夠用，當發生了緩沖區溢出就有可能造成程式異常結束。
是以，Redis 的 SDS 結構裡引入了 alloc 和 len 成員變量，這樣 SDS API 通過
alloc - len
計算，可以算出剩餘可用的空間大小，這樣在對字元串做修改操作的時候，就可以由程式内部判斷緩沖區大小是否足夠用。
而且，當判斷出緩沖區大小不夠用時，Redis 會自動将擴大 SDS 的空間大小（小于 1MB 翻倍擴容，大于 1MB 按 1MB 擴容），以滿足修改所需的大小。
在擴充 SDS 空間之前，SDS API 會優先檢查未使用空間是否足夠，如果不夠的話，API 不僅會為 SDS 配置設定修改所必須要的空間，還會給 SDS 配置設定額外的「未使用空間」。
這樣的好處是，下次在操作 SDS 時，如果 SDS 空間夠的話，API 就會直接使用「未使用空間」，而無須執行記憶體配置設定，有效的減少記憶體配置設定次數。
是以，使用 SDS 即不需要手動修改 SDS 的空間大小，也不會出現緩沖區溢出的問題。
節省記憶體空間
SDS 結構中有個 flags 成員變量，表示的是 SDS 類型。
Redos 一共設計了 5 種類型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
這 5 種類型的主要差別就在于，它們資料結構中的 len 和 alloc 成員變量的資料類型不同。
比如 sdshdr16 和 sdshdr32 這兩個類型，它們的定義分别如下：
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
可以看到：
- sdshdr16 類型的 len 和 alloc 的資料類型都是 uint16_t，表示字元數組長度和配置設定空間大小不能超過 2 的 16 次方。
- sdshdr32 則都是 uint32_t，表示表示字元數組長度和配置設定空間大小不能超過 2 的 32 次方。
之是以 SDS 設計不同類型的結構體，是為了能靈活儲存不同大小的字元串，進而有效節省記憶體空間。比如，在儲存小字元串時，結構頭占用空間也比較少。
除了設計不同類型的結構體，Redis 在程式設計上還使用了專門的編譯優化來節省記憶體空間，即在 struct 聲明了
__attribute__ ((packed))
，它的作用是：告訴編譯器取消結構體在編譯過程中的優化對齊，按照實際占用位元組數進行對齊。
比如，sdshdr16 類型的 SDS，預設情況下，編譯器會按照 16 位元組對齊的方式給變量配置設定記憶體，這意味着，即使一個變量的大小不到 16 個位元組，編譯器也會給它配置設定 16 個位元組。
舉個例子，假設下面這個結構體，它有兩個成員變量，類型分别是 char 和 int，如下所示：
#include <stdio.h>
struct test1 {
char a;
int b;
} test1;
int main() {
printf("%lu\n", sizeof(test1));
return 0;
}
大家猜猜這個結構體大小是多少？我先直接說答案，這個結構體大小計算出來是 8。
這是因為預設情況下，編譯器是使用「位元組對齊」的方式配置設定記憶體，雖然 char 類型隻占一個位元組，但是由于成員變量裡有 int 類型，它占用了 4 個位元組，是以在成員變量為 char 類型配置設定記憶體時，會配置設定 4 個位元組，其中這多餘的 3 個位元組是為了位元組對齊而配置設定的，相當于有 3 個位元組被浪費掉了。
如果不想編譯器使用位元組對齊的方式進行配置設定記憶體，可以采用了
__attribute__ ((packed))
屬性定義結構體，這樣一來，結構體實際占用多少記憶體空間，編譯器就配置設定多少空間。
比如，我用
__attribute__ ((packed))
屬性定義下面的結構體 ，同樣包含 char 和 int 兩個類型的成員變量，代碼如下所示：
#include <stdio.h>
struct __attribute__((packed)) test2 {
char a;
int b;
} test2;
int main() {
printf("%lu\n", sizeof(test2));
return 0;
}
這時列印的結果是 5（1 個位元組 char + 4 位元組 int）。
可以看得出，這是按照實際占用位元組數進行配置設定記憶體的，這樣可以節省記憶體空間。
連結清單
大家最熟悉的資料結構除了數組之外，我相信就是連結清單了。
Redis 的 List 對象的底層實作之一就是連結清單。C 語言本身沒有連結清單這個資料結構的，是以 Redis 自己設計了一個連結清單資料結構。
連結清單節點結構設計
先來看看「連結清單節點」結構的樣子：
typedef struct listNode {
//前置節點
struct listNode *prev;
//後置節點
struct listNode *next;
//節點的值
void *value;
} listNode;
有前置節點和後置節點，可以看的出，這個是一個雙向連結清單。
連結清單結構設計
不過，Redis 在 listNode 結構體基礎上又封裝了 list 這個資料結構，這樣操作起來會更友善，連結清單結構如下：
typedef struct list {
//連結清單頭節點
listNode *head;
//連結清單尾節點
listNode *tail;
//節點值複制函數
void *(*dup)(void *ptr);
//節點值釋放函數
void (*free)(void *ptr);
//節點值比較函數
int (*match)(void *ptr, void *key);
//連結清單節點數量
unsigned long len;
} list;
list 結構為連結清單提供了連結清單頭指針 head、連結清單尾節點 tail、連結清單節點數量 len、以及可以自定義實作的 dup、free、match 函數。
舉個例子，下面是由 list 結構和 3 個 listNode 結構組成的連結清單。
連結清單的優勢與缺陷
Redis 的連結清單實作優點如下：
- listNode 連結清單節點的結構裡帶有 prev 和 next 指針，擷取某個節點的前置節點或後置節點的時間複雜度隻需O(1)，而且這兩個指針都可以指向 NULL，是以連結清單是無環連結清單；
- list 結構因為提供了表頭指針 head 和表尾節點 tail，是以擷取連結清單的表頭節點和表尾節點的時間複雜度隻需O(1)；
- list 結構因為提供了連結清單節點數量 len，是以擷取連結清單中的節點數量的時間複雜度隻需O(1)；
- listNode 連結清單節使用 void* 指針儲存節點值，并且可以通過 list 結構的 dup、free、match 函數指針為節點設定該節點類型特定的函數，是以連結清單節點可以儲存各種不同類型的值；
連結清單的缺陷也是有的：
- 連結清單每個節點之間的記憶體都是不連續的，意味着無法很好利用 CPU 緩存。能很好利用 CPU 緩存的資料結構就是數組，因為數組的記憶體是連續的，這樣就可以充分利用 CPU 緩存來加速通路。
- 還有一點，儲存一個連結清單節點的值都需要一個連結清單節點結構頭的配置設定，記憶體開銷較大。
是以，Redis 3.0 的 List 對象在資料量比較少的情況下，會采用「壓縮清單」作為底層資料結構的實作，它的優勢是節省記憶體空間，并且是記憶體緊湊型的資料結構。
不過，壓縮清單存在性能問題（具體什麼問題，下面會說），是以 Redis 在 3.2 版本設計了新的資料結構 quicklist，并将 List 對象的底層資料結構改由 quicklist 實作。
然後在 Redis 5.0 設計了新的資料結構 listpack，沿用了壓縮清單緊湊型的記憶體布局，最終在最新的 Redis 版本，将 Hash 對象和 Zset 對象的底層資料結構實作之一的壓縮清單，替換成由 listpack 實作。
壓縮清單
壓縮清單的最大特點，就是它被設計成一種記憶體緊湊型的資料結構，占用一塊連續的記憶體空間，不僅可以利用 CPU 緩存，而且會針對不同長度的資料，進行相應編碼，這種方法可以有效地節省記憶體開銷。
但是，壓縮清單的缺陷也是有的：
- 不能儲存過多的元素，否則查詢效率就會降低；
- 新增或修改某個元素時，壓縮清單占用的記憶體空間需要重新配置設定，甚至可能引發連鎖更新的問題。
是以，Redis 對象（List 對象、Hash 對象、Zset 對象）包含的元素數量較少，或者元素值不大的情況才會使用壓縮清單作為底層資料結構。
接下來，就跟大家詳細聊下壓縮清單。
壓縮清單結構設計
壓縮清單是 Redis 為了節約記憶體而開發的，它是由連續記憶體塊組成的順序型資料結構，有點類似于數組。
壓縮清單在表頭有三個字段：
- zlbytes，記錄整個壓縮清單占用對記憶體位元組數；
- zltail，記錄壓縮清單「尾部」節點距離起始位址由多少位元組，也就是清單尾的偏移量；
- zllen，記錄壓縮清單包含的節點數量；
- zlend，标記壓縮清單的結束點，固定值 0xFF（十進制255）。
在壓縮清單中，如果我們要查找定位第一個元素和最後一個元素，可以通過表頭三個字段的長度直接定位，複雜度是 O(1)。而查找其他元素時，就沒有這麼高效了，隻能逐個查找，此時的複雜度就是 O(N) 了，是以壓縮清單不适合儲存過多的元素。
另外，壓縮清單節點（entry）的構成如下：
壓縮清單節點包含三部分内容：
- prevlen，記錄了「前一個節點」的長度；
- encoding，記錄了目前節點實際資料的類型以及長度；
- data，記錄了目前節點的實際資料；
當我們往壓縮清單中插入資料時，壓縮清單就會根據資料是字元串還是整數，以及資料的大小，會使用不同空間大小的 prevlen 和 encoding 這兩個元素裡儲存的資訊，這種根據資料大小和類型進行不同的空間大小配置設定的設計思想，正是 Redis 為了節省記憶體而采用的。
分别說下，prevlen 和 encoding 是如何根據資料的大小和類型來進行不同的空間大小配置設定。
壓縮清單裡的每個節點中的 prevlen 屬性都記錄了「前一個節點的長度」，而且 prevlen 屬性的空間大小跟前一個節點長度值有關，比如：
- 如果前一個節點的長度小于 254 位元組，那麼 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值；
- 如果前一個節點的長度大于等于 254 位元組，那麼 prevlen 屬性需要用 5 位元組的空間來儲存這個長度值；
encoding 屬性的空間大小跟資料是字元串還是整數，以及字元串的長度有關：
- 如果目前節點的資料是整數，則 encoding 會使用 1 位元組的空間進行編碼。
- 如果目前節點的資料是字元串，根據字元串的長度大小，encoding 會使用 1 位元組/2位元組/5位元組的空間進行編碼。
連鎖更新
壓縮清單除了查找複雜度高的問題，還有一個問題。
壓縮清單新增某個元素或修改某個元素時，如果空間不不夠，壓縮清單占用的記憶體空間就需要重新配置設定。而當新插入的元素較大時，可能會導緻後續元素的 prevlen 占用空間都發生變化，進而引起「連鎖更新」問題，導緻每個元素的空間都要重新配置設定，造成通路壓縮清單性能的下降。
前面提到，壓縮清單節點的 prevlen 屬性會根據前一個節點的長度進行不同的空間大小配置設定：
現在假設一個壓縮清單中有多個連續的、長度在 250～253 之間的節點，如下圖：
因為這些節點長度值小于 254 位元組，是以 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值。
這時，如果将一個長度大于等于 254 位元組的新節點加入到壓縮清單的表頭節點，即新節點将成為 e1 的前置節點，如下圖：
因為 e1 節點的 prevlen 屬性隻有 1 個位元組大小，無法儲存新節點的長度，此時就需要對壓縮清單的空間重配置設定操作，并将 e1 節點的 prevlen 屬性從原來的 1 位元組大小擴充為 5 位元組大小。
多米諾牌的效應就此開始。
e1 原本的長度在 250～253 之間，因為剛才的擴充空間，此時 e1 的長度就大于等于 254 了，是以原本 e2 儲存 e1 的 prevlen 屬性也必須從 1 位元組擴充至 5 位元組大小。
正如擴充 e1 引發了對 e2 擴充一樣，擴充 e2 也會引發對 e3 的擴充，而擴充 e3 又會引發對 e4 的擴充…. 一直持續到結尾。
這種在特殊情況下産生的連續多次空間擴充操作就叫做「連鎖更新」，就像多米諾牌的效應一樣，第一張牌倒下了，推動了第二張牌倒下；第二張牌倒下，又推動了第三張牌倒下….，
壓縮清單的缺陷
空間擴充操作也就是重新配置設定記憶體，是以連鎖更新一旦發生，就會導緻壓縮清單占用的記憶體空間要多次重新配置設定，這就會直接影響到壓縮清單的通路性能。
是以說，雖然壓縮清單緊湊型的記憶體布局能節省記憶體開銷，但是如果儲存的元素數量增加了，或是元素變大了，會導緻記憶體重新配置設定，最糟糕的是會有「連鎖更新」的問題。
是以，壓縮清單隻會用于儲存的節點數量不多的場景，隻要節點數量足夠小，即使發生連鎖更新，也是能接受的。
雖說如此，Redis 針對壓縮清單在設計上的不足，在後來的版本中，新增設計了兩種資料結構：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種資料結構的設計目标，就是盡可能地保持壓縮清單節省記憶體的優勢，同時解決壓縮清單的「連鎖更新」的問題。
哈希表
哈希表是一種儲存鍵值對（key-value）的資料結構。
哈希表中的每一個 key 都是獨一無二的，程式可以根據 key 查找到與之關聯的 value，或者通過 key 來更新 value，又或者根據 key 來删除整個 key-value等等。
在講壓縮清單的時候，提到過 Redis 的 Hash 對象的底層實作之一是壓縮清單（最新 Redis 代碼已将壓縮清單替換成 listpack）。Hash 對象的另外一個底層實作就是哈希表。
哈希表優點在于，它能以 O(1) 的複雜度快速查詢資料。怎麼做到的呢？将 key 通過 Hash 函數的計算，就能定位資料在表中的位置，因為哈希表實際上是數組，是以可以通過索引值快速查詢到資料。
但是存在的風險也是有，在哈希表大小固定的情況下，随着資料不斷增多，那麼哈希沖突的可能性也會越高。
解決哈希沖突的方式，有很多種。
Redis 采用了「鍊式哈希」來解決哈希沖突，在不擴容哈希表的前提下，将具有相同哈希值的資料串起來，形成連結起，以便這些資料在表中仍然可以被查詢到。
接下來，詳細說說哈希表。
哈希表結構設計
Redis 的哈希表結構如下：
typedef struct dictht {
//哈希表數組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值
unsigned long sizemask;
//該哈希表已有的節點數量
unsigned long used;
} dictht;
可以看到，哈希表是一個數組（dictEntry **table），數組的每個元素是一個指向「哈希表節點（dictEntry）」的指針。
哈希表節點的結構如下：
typedef struct dictEntry {
//鍵值對中的鍵
void *key;
//鍵值對中的值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//指向下一個哈希表節點，形成連結清單
struct dictEntry *next;
} dictEntry;
dictEntry 結構裡不僅包含指向鍵和值的指針，還包含了指向下一個哈希表節點的指針，這個指針可以将多個哈希值相同的鍵值對連結起來，以此來解決哈希沖突的問題，這就是鍊式哈希。
另外，這裡還跟你提一下，dictEntry 結構裡鍵值對中的值是一個「聯合體 v」定義的，是以，鍵值對中的值可以是一個指向實際值的指針，或者是一個無符号的 64 位整數或有符号的 64 位整數或double 類的值。這麼做的好處是可以節省記憶體空間，因為當「值」是整數或浮點數時，就可以将值的資料内嵌在 dictEntry 結構裡，無需再用一個指針指向實際的值，進而節省了記憶體空間。
哈希沖突
哈希表實際上是一個數組，數組裡多每一個元素就是一個哈希桶。
當一個鍵值對的鍵經過 Hash 函數計算後得到哈希值，再将(哈希值 % 哈希表大小)取模計算，得到的結果值就是該 key-value 對應的數組元素位置，也就是第幾個哈希桶。
什麼是哈希沖突呢？
舉個例子，有一個可以存放 8 個哈希桶的哈希表。key1 經過哈希函數計算後，再将「哈希值 % 8 」進行取模計算，結果值為 1，那麼就對應哈希桶 1，類似的，key9 和 key10 分别對應哈希桶 1 和桶 6。
此時，key1 和 key9 對應到了相同的哈希桶中，這就發生了哈希沖突。
是以，當有兩個以上數量的 kay 被配置設定到了哈希表中同一個哈希桶上時，此時稱這些 key 發生了沖突。
鍊式哈希
Redis 采用了「鍊式哈希」的方法來解決哈希沖突。
鍊式哈希是怎麼實作的？
實作的方式就是每個哈希表節點都有一個 next 指針，用于指向下一個哈希表節點，是以多個哈希表節點可以用 next 指針構成一個單項連結清單，被配置設定到同一個哈希桶上的多個節點可以用這個單項連結清單連接配接起來，這樣就解決了哈希沖突。
還是用前面的哈希沖突例子，key1 和 key9 經過哈希計算後，都落在同一個哈希桶，鍊式哈希的話，key1 就會通過 next 指針指向 key9，形成一個單向連結清單。
不過，鍊式哈希局限性也很明顯，随着連結清單長度的增加，在查詢這一位置上的資料的耗時就會增加，畢竟連結清單的查詢的時間複雜度是 O(n)。
要想解決這一問題，就需要進行 rehash，也就是對哈希表的大小進行擴充。
接下來，看看 Redis 是如何實作的 rehash 的。
rehash
哈希表結構設計的這一小節，我給大家介紹了 Redis 使用 dictht 結構體表示哈希表。不過，在實際使用哈希表時，Redis 定義一個 dict 結構體，這個結構體裡定義了兩個哈希表（ht[2]）。
typedef struct dict {
…
//兩個Hash表，交替使用，用于rehash操作
dictht ht[2];
…
} dict;
之是以定義了 2 個哈希表，是因為進行 rehash 的時候，需要用上 2 個哈希表了。
在正常服務請求階段，插入的資料，都會寫入到「哈希表 1」，此時的「哈希表 2 」 并沒有被配置設定空間。
随着資料逐漸增多，觸發了 rehash 操作，這個過程分為三步：
- 給「哈希表 2」 配置設定空間，一般會比「哈希表 1」 大 2 倍；
- 将「哈希表 1 」的資料遷移到「哈希表 2」 中；
- 遷移完成後，「哈希表 1 」的空間會被釋放，并把「哈希表 2」 設定為「哈希表 1」，然後在「哈希表 2」 新建立一個空白的哈希表，為下次 rehash 做準備。
為了友善你了解，我把 rehash 這三個過程畫在了下面這張圖：
這個過程看起來簡單，但是其實第二步很有問題，如果「哈希表 1 」的資料量非常大，那麼在遷移至「哈希表 2 」的時候，因為會涉及大量的資料拷貝，此時可能會對 Redis 造成阻塞，無法服務其他請求。
漸進式 rehash
為了避免 rehash 在資料遷移過程中，因拷貝資料的耗時，影響 Redis 性能的情況，是以 Redis 采用了漸進式 rehash，也就是将資料的遷移的工作不再是一次性遷移完成，而是分多次遷移。
漸進式 rehash 步驟如下：
- 給「哈希表 2」 配置設定空間；
- 在 rehash 進行期間，每次哈希表元素進行新增、删除、查找或者更新操作時，Redis 除了會執行對應的操作之外，還會順序将「哈希表 1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
- 随着處理用戶端發起的哈希表操作請求數量越多，最終在某個時間嗲呢，會把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，進而完成 rehash 操作。
這樣就巧妙地把一次性大量資料遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作。
在進行漸進式 rehash 的過程中，會有兩個哈希表，是以在漸進式 rehash 進行期間，哈希表元素的删除、查找、更新等操作都會在這兩個哈希表進行。
比如，查找一個 key 的值的話，先會在「哈希表 1」 裡面進行查找，如果沒找到，就會繼續到哈希表 2 裡面進行找到。
另外，在漸進式 rehash 進行期間，新增一個 key-value 時，會被儲存到「哈希表 2 」裡面，而「哈希表 1」 則不再進行任何添加操作，這樣保證了「哈希表 1 」的 key-value 數量隻會減少，随着 rehash 操作的完成，最終「哈希表 1 」就會變成空表。
rehash 觸發條件
介紹了 rehash 那麼多，還沒說什麼時情況下會觸發 rehash 操作呢？
rehash 的觸發條件跟負載因子（load factor）有關系。
負載因子可以通過下面這個公式計算：
觸發 rehash 操作的條件，主要有兩個：
- 當負載因子大于等于 1 ，并且 Redis 沒有在執行 bgsave 指令或者 bgrewiteaof 指令，也就是沒有執行 RDB 快照或沒有進行 AOF 重寫的時候，就會進行 rehash 操作。
- 當負載因子大于等于 5 時，此時說明哈希沖突非常嚴重了，不管有沒有有在執行 RDB 快照或 AOF 重寫，都會強制進行 rehash 操作。
整數集合
整數集合是 Set 對象的底層實作之一。當一個 Set 對象隻包含整數值元素，并且元素數量不時，就會使用整數集這個資料結構作為底層實作。
整數集合結構設計
整數集合本質上是一塊連續記憶體空間，它的結構定義如下：
typedef struct intset {
//編碼方式
uint32_t encoding;
//集合包含的元素數量
uint32_t length;
//儲存元素的數組
int8_t contents[];
} intset;
可以看到，儲存元素的容器是一個 contents 數組，雖然 contents 被聲明為 int8_t 類型的數組，但是實際上 contents 數組并不儲存任何 int8_t 類型的元素，contents 數組的真正類型取決于 intset 結構體裡的 encoding 屬性的值。比如：
- 如果 encoding 屬性值為 INTSET_ENC_INT16，那麼 contents 就是一個 int16_t 類型的數組，數組中每一個元素的類型都是 int16_t；
- 如果 encoding 屬性值為 INTSET_ENC_INT32，那麼 contents 就是一個 int32_t 類型的數組，數組中每一個元素的類型都是 int32_t；
- 如果 encoding 屬性值為 INTSET_ENC_INT64，那麼 contents 就是一個 int64_t 類型的數組，數組中每一個元素的類型都是 int64_t；
不同類型的 contents 數組，意味着數組的大小也會不同。
整數集合的更新操作
整數集合會有一個更新規則，就是當我們将一個新元素加入到整數集合裡面，如果新元素的類型（int32_t）比整數集合現有所有元素的類型（int16_t）都要長時，整數集合需要先進行更新，也就是按新元素的類型（int32_t）擴充 contents 數組的空間大小，然後才能将新元素加入到整數集合裡，當然更新的過程中，也要維持整數集合的有序性。
整數集合更新的過程不會重新配置設定一個新類型的數組，而是在原本的數組上擴充空間，然後在将每個元素按間隔類型大小分割，如果 encoding 屬性值為 INTSET_ENC_INT16，則每個元素的間隔就是 16 位。
舉個例子，假設有一個整數集合裡有 3 個類型為 int16_t 的元素。
現在，往這個整數集合中加入一個新元素 65535，這個新元素需要用 int32_t 類型來儲存，是以整數集合要進行更新操作，首先需要為 contents 數組擴容，在原本空間的大小之上再擴容多 80 位（4x32-3x16=80），這樣就能儲存下 4 個類型為 int32_t 的元素。
擴容完 contents 數組空間大小後，需要将之前的三個元素轉換為 int32_t 類型，并将轉換後的元素放置到正确的位上面，并且需要維持底層數組的有序性不變，整個轉換過程如下：
整數集合更新有什麼好處呢？
如果要讓一個數組同時儲存 int16_t、int32_t、int64_t 類型的元素，最簡單做法就是直接使用 int64_t 類型的數組。不過這樣的話，當如果元素都是 int16_t 類型的，就會造成記憶體浪費的情況。
整數集合更新就能避免這種情況，如果一直向整數集合添加 int16_t 類型的元素，那麼整數集合的底層實作就一直是用 int16_t 類型的數組，隻有在我們要将 int32_t 類型或 int64_t 類型的元素添加到集合時，才會對數組進行更新操作。
是以，整數集合更新的好處是節省記憶體資源。
整數集合支援降級操作嗎？
不支援降級操作，一旦對數組進行了更新，就會一直保持更新後的狀态。比如前面的更新操作的例子，如果删除了 65535 元素，整數集合的數組還是 int32_t 類型的，并不會是以降級為 int16_t 類型。
跳表
Redis 隻有在 Zset 對象的底層實作用到了跳表，跳表的優勢是能支援平均 O(logN) 複雜度的節點查找。
Zset 對象是唯一一個同時使用了兩個資料結構來實作的 Redis 對象，這兩個資料結構一個是跳表，一個是哈希表。這樣的好處是既能進行高效的範圍查詢，也能進行高效單點查詢。
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
Zset 對象能支援範圍查詢（如 ZRANGEBYSCORE 操作），這是因為它的資料結構設計采用了跳表，而又能以常數複雜度擷取元素權重（如 ZSCORE 操作），這是因為它同時采用了哈希表進行索引。
接下來，詳細的說下跳表。
跳表結構設計
連結清單在查找元素的時候，因為需要逐一查找，是以查詢效率非常低，時間複雜度是O(N)，于是就出現了跳表。跳表是在連結清單基礎上改進過來的，實作了一種「多層」的有序連結清單，這樣的好處是能快讀定位資料。
那跳表長什麼樣呢？我這裡舉個例子，下圖展示了一個層級為 3 的跳表。
圖中頭節點有 L0~L2 三個頭指針，分别指向了不同層級的節點，然後每個層級的節點都通過指針連接配接起來：
- L0 層級共有 5 個節點，分别是節點1、2、3、4、5；
- L1 層級共有 3 個節點，分别是節點 2、3、5；
- L2 層級隻有 1 個節點，也就是節點 3 。
如果我們要在連結清單中查找節點 4 這個元素，隻能從頭開始周遊連結清單，需要查找 4 次，而使用了跳表後，隻需要查找 2 次就能定位到節點 4，因為可以在頭節點直接從 L2 層級跳到節點 3，然後再往前周遊找到節點 4。
可以看到，這個查找過程就是在多個層級上跳來跳去，最後定位到元素。當資料量很大時，跳表的查找複雜度就是 O(logN)。
那跳表節點是怎麼實作多層級的呢？這就需要看「跳表節點」的資料結構了，如下：
typedef struct zskiplistNode {
//Zset 對象的元素值
sds ele;
//元素權重值
double score;
//後向指針
struct zskiplistNode *backward;
//節點的level數組，儲存每層上的前向指針和跨度
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
Zset 對象要同時儲存元素和元素的權重，對應到跳表節點結構裡就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節點都有一個後向指針，指向前一個節點，目的是為了友善從跳表的尾節點開始通路節點，這樣倒序查找時很友善。
跳表是一個帶有層級關系的連結清單，而且每一層級可以包含多個節點，每一個節點通過指針連接配接起來，實作這一特性就是靠跳表節點結構體中的zskiplistLevel 結構體類型的 level 數組。
level 數組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結構體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結構體裡定義了「指向下一個跳表節點的指針」和「跨度」，跨度時用來記錄兩個節點之間的距離。
比如，下面這張圖，展示了各個節點的跨度。
第一眼看到跨度的時候，以為是周遊操作有關，實際上并沒有任何關系，周遊操作隻需要用前向指針就可以完成了。
跨度實際上是為了計算這個節點在跳表中的排位。具體怎麼做的呢？因為跳表中的節點都是按序排列的，那麼計算某個節點排位的時候，從頭節點點到該結點的查詢路徑上，将沿途通路過的所有層的跨度累加起來，得到的結果就是目标節點在跳表中的排位。
舉個例子，查找圖中節點 3 在跳表中的排位，從頭節點開始查找節點 3，查找的過程隻經過了一個層（L3），并且層的跨度是 3，是以節點 3 在跳表中的排位是 3。
另外，圖中的頭節點其實也是 zskiplistNode 跳表節點，隻不過頭節點的後向指針、權重、元素值都會被用到，是以圖中省略了這部分。
問題來了，由誰定義哪個跳表節點是頭節點呢？這就介紹「跳表」結構體了，如下所示：
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
跳表結構裡包含了：
- 跳表的頭尾節點，便于在O(1)時間複雜度内通路跳表的頭節點和尾節點；
- 跳表的長度，便于在O(1)時間複雜度擷取跳表節點的數量；
- 跳表的最大層數，便于在O(1)時間複雜度擷取跳表中層高最大的那個節點的層數量；
跳表節點查詢過程
查找一個跳表節點的過程時，跳表會從頭節點的最高層開始，逐一周遊每一層。在周遊某一層的跳表節點時，會用跳表節點中的 SDS 類型的元素和元素的權重來進行判斷，共有兩個判斷條件：
- 如果目前節點的權重「小于」要查找的權重時，跳表就會通路該層上的下一個節點。
- 如果目前節點的權重「等于」要查找的權重時，并且目前節點的 SDS 類型資料「小于」要查找的資料時，跳表就會通路該層上的下一個節點。
如果上面兩個條件都不滿足，或者下一個節點為空時，跳表就會使用目前周遊到的節點的 level 數組裡的下一層指針，然後沿着下一層指針繼續查找，這就相當于跳到了下一層接着查找。
舉個例子，下圖有個 3 層級的跳表。
如果要查找「元素：abcd，權重：4」的節點，查找的過程是這樣的：
- 先從頭節點的最高層開始，L2 指向了「元素：abc，權重：3」節點，這個節點的權重比要查找節點的小，是以要通路該層上的下一個節點；
- 但是該層上的下一個節點是空節點，于是就會跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[1];
- 「元素：abc，權重：3」節點的 leve[1] 的下一個指針指向了「元素：abcde，權重：4」的節點，然後将其和要查找的節點比較。雖然「元素：abcde，權重：4」的節點的權重和要查找的權重相同，但是目前節點的 SDS 類型資料「大于」要查找的資料，是以會繼續跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[0]；
- 「元素：abc，權重：3」節點的 leve[0] 的下一個指針指向了「元素：abcd，權重：4」的節點，該節點正是要查找的節點，查詢結束。
跳表節點層數設定
跳表的相鄰兩層的節點數量的比例會影響跳表的查詢性能。
舉個例子，下圖的跳表，第二層的節點數量隻有 1 個，而第一層的節點數量有 6 個。
這時，如果想要查詢節點 6，那基本就跟連結清單的查詢複雜度一樣，就需要在第一層的節點中依次順序查找，複雜度就是 O(N) 了。是以，為了降低查詢複雜度，我們就需要維持相鄰層結點數間的關系。
跳表的相鄰兩層的節點數量最理想的比例是 2:1，查找複雜度可以降低到 O(logN)。
下圖的跳表就是，相鄰兩層的節點數量的比例是 2 : 1。
那怎樣才能維持相鄰兩層的節點數量的比例為 2 : 1 呢？
如果采用新增節點或者删除節點時，來調整跳表節點以維持比例的方法的話，會帶來額外的開銷。
Redis 則采用一種巧妙的方法是，跳表在建立節點的時候，随機生成每個節點的層數，并沒有嚴格維持相鄰兩層的節點數量比例為 2 : 1 的情況。
具體的做法是，跳表在建立節點時候，會生成範圍為[0-1]的一個随機數，如果這個随機數小于 0.25（相當于機率 25%），那麼層數就增加 1 層，然後繼續生成下一個随機數，直到随機數的結果大于 0.25 結束，最終确定該節點的層數。
這樣的做法，相當于每增加一層的機率不超過 25%，層數越高，機率越低，層高最大限制是 64。
quicklist
在 Redis 3.0 之前，List 對象的底層資料結構是雙向連結清單或者壓縮清單。然後在 Redis 3.2 的時候，List 對象的底層改由 quicklist 資料結構實作。
其實 quicklist 就是「雙向連結清單 + 壓縮清單」組合，因為一個 quicklist 就是一個連結清單，而連結清單中的每個元素又是一個壓縮清單。
在前面講壓縮清單的時候，我也提到了壓縮清單的不足，雖然壓縮清單是通過緊湊型的記憶體布局節省了記憶體開銷，但是因為它的結構設計，如果儲存的元素數量增加，或者元素變大了，壓縮清單會有「連鎖更新」的風險，一旦發生，會造成性能下降。
quicklist 解決辦法，通過控制每個連結清單節點中的壓縮清單的大小或者元素個數，來規避連鎖更新的問題。因為壓縮清單元素越少或越小，連鎖更新帶來的影響就越小，進而提供了更好的通路性能。
quicklist 結構設計
quicklist 的結構體跟連結清單的結構體類似，都包含了表頭和表尾，差別在于 quicklist 的節點是 quicklistNode。
typedef struct quicklist {
//quicklist的連結清單頭
quicklistNode *head; //quicklist的連結清單頭
//quicklist的連結清單頭
quicklistNode *tail;
//所有壓縮清單中的總元素個數
unsigned long count;
//quicklistNodes的個數
unsigned long len;
...
} quicklist;
接下來看看，quicklistNode 的結構定義：
typedef struct quicklistNode {
//前一個quicklistNode
struct quicklistNode *prev; //前一個quicklistNode
//下一個quicklistNode
struct quicklistNode *next; //後一個quicklistNode
//quicklistNode指向的壓縮清單
unsigned char *zl;
//壓縮清單的的位元組大小
unsigned int sz;
//壓縮清單的元素個數
unsigned int count : 16; //ziplist中的元素個數
....
} quicklistNode;
可以看到，quicklistNode 結構體裡包含了前一個節點和下一個節點指針，這樣每個 quicklistNode 形成了一個雙向連結清單。但是連結清單節點的元素不再是單純儲存元素值，而是儲存了一個壓縮清單，是以 quicklistNode 結構體裡有個指向壓縮清單的指針 *zl。
我畫了一張圖，友善你了解 quicklist 資料結構。
在向 quicklist 添加一個元素的時候，不會像普通的連結清單那樣，直接建立一個連結清單節點。而是會檢查插入位置的壓縮清單是否能容納該元素，如果能容納就直接儲存到 quicklistNode 結構裡的壓縮清單，如果不能容納，才會建立一個新的 quicklistNode 結構。
quicklist 會控制 quicklistNode 結構裡的壓縮清單的大小或者元素個數，來規避潛在的連鎖更新的風險，但是這并沒有完全解決連鎖更新的問題。
listpack
quicklist 雖然通過控制 quicklistNode 結構裡的壓縮清單的大小或者元素個數，來減少連鎖更新帶來的性能影響，但是并沒有完全解決連鎖更新的問題。
因為 quicklistNode 還是用了壓縮清單來儲存元素，壓縮清單連鎖更新的問題，來源于它的結構設計，是以要想徹底解決這個問題，需要設計一個新的資料結構。
于是，Redis 在 5.0 新設計一個資料結構叫 listpack，目的是替代壓縮清單，它最大特點是 listpack 中每個節點不再包含前一個節點的長度了，壓縮清單每個節點正因為需要儲存前一個節點的長度字段，就會有連鎖更新的隐患。
我看了 Redis 的 Github，在最新 6.2 發行版本中，Redis Hash 對象、Set 對象的底層資料結構的壓縮清單還未被替換成 listpack，而 Redis 的最新代碼（還未釋出版本）已經将所有用到壓縮清單底層資料結構的 Redis 對象替換成 listpack 資料結構來實作，估計不久将來，Redis 就會釋出一個将壓縮清單為 listpack 的發行版本。
listpack 結構設計
listpack 采用了壓縮清單的很多優秀的設計，比如還是用一塊連續的記憶體空間來緊湊地儲存資料，并且為了節省記憶體的開銷，listpack 節點會采用不同的編碼方式儲存不同大小的資料。
我們先看看 listpack 結構：
listpack 頭包含兩個屬性，分别記錄了 listpack 總位元組數和元素數量，然後 listpack 末尾也有個結尾辨別。圖中的 listpack entry 就是 listpack 的節點了。
每個 listpack 節點結構如下：
主要包含三個方面内容：
- encoding，定義該元素的編碼類型，會對不同長度的整數和字元串進行編碼；
- data，實際存放的資料；
- len，encoding+data的總長度；
可以看到，listpack 沒有壓縮清單中記錄前一個節點長度的字段了，listpack 隻記錄目前節點的長度，當我們向 listpack 加入一個新元素的時候，不會影響其他節點的長度字段的變化，進而避免了壓縮清單的連鎖更新問題。
參考資料：
- 《Redis設計與實作》
- 《Redis 源碼剖析與實戰》
總結
終于完工了，松一口氣。
好久沒寫那麼長的圖解技術文啦，這次潇潇灑灑寫了 1.5 萬字 + 畫了 40 多張圖，花費了不少時間，又是看書，又是看源碼。
希望這篇文章，能幫你破除 Redis 資料結構的迷霧！
我是小林，我們下次再見～
等等等，滑到底的朋友，給個「三連」在走呀！
關注公衆号：「小林coding」 ，回複「我要學習」即可免費獲得「伺服器 Linux C/C++ 」成長路程（書籍資料 + 思維導圖）