上一篇部落格我們介紹了 redis的五大資料類型詳細用法 ，但是在 Redis 中，這幾種資料類型底層是由什麼資料結構構造的呢？本篇部落格我們就來詳細介紹Redis中五大資料類型的底層實作。
1、示範資料類型的實作
上篇部落格我們在介紹 key 相關指令的時候，介紹了如下指令：
OBJECT ENCODING key 該指令是用來顯示那五大資料類型的底層資料結構。
比如對于 string 資料類型：
我們可以看到實作string資料類型的資料結構有 embstr 以及 int。
再比如 list 資料類型：
這裡我們就不做過多的示範了，那麼上次出現的 embstr 以及 int 還有 quicklist 是什麼資料結構呢？下面我們就來介紹Redis中幾種主要的資料結構。
2、簡單動态字元串
第一篇文章我們就說過 Redis 是用 C 語言寫的，但是對于Redis的字元串，卻不是 C 語言中的字元串（即以空字元’\0’結尾的字元數組），它是自己建構了一種名為 簡單動态字元串（simple dynamic string,SDS）的抽象類型，并将 SDS 作為 Redis的預設字元串表示。
SDS 定義：
struct sdshdr{
//記錄buf數組中已使用位元組的數量
//等于 SDS 儲存字元串的長度
int len;
//記錄 buf 數組中未使用位元組的數量
int free;
//位元組數組，用于儲存字元串
char buf[];
}
用SDS儲存字元串 “Redis”具體圖示如下：
圖檔來源：《Redis設計與實作》
我們看上面對于 SDS 資料類型的定義：
1、len 儲存了SDS儲存字元串的長度
2、buf[] 數組用來儲存字元串的每個元素
3、free j記錄了 buf 數組中未使用的位元組數量
上面的定義相對于 C 語言對于字元串的定義，多出了 len 屬性以及 free 屬性。為什麼不使用C語言字元串實作，而是使用 SDS呢？這樣實作有什麼好處？
①、常數複雜度擷取字元串長度
由于 len 屬性的存在，我們擷取 SDS 字元串的長度隻需要讀取 len 屬性，時間複雜度為 O(1)。而對于 C 語言，擷取字元串的長度通常是經過周遊計數來實作的，時間複雜度為 O(n)。通過 strlen key 指令可以擷取 key 的字元串長度。
②、杜絕緩沖區溢出
我們知道在 C 語言中使用 strcat 函數來進行兩個字元串的拼接，一旦沒有配置設定足夠長度的記憶體空間，就會造成緩沖區溢出。而對于 SDS 資料類型，在進行字元修改的時候，會首先根據記錄的 len 屬性檢查記憶體空間是否滿足需求，如果不滿足，會進行相應的空間擴充，然後在進行修改操作，是以不會出現緩沖區溢出。
③、減少修改字元串的記憶體重新配置設定次數
C語言由于不記錄字元串的長度，是以如果要修改字元串，必須要重新配置設定記憶體（先釋放再申請），因為如果沒有重新配置設定，字元串長度增大時會造成記憶體緩沖區溢出，字元串長度減小時會造成記憶體洩露。
而對于SDS，由于len屬性和free屬性的存在，對于修改字元串SDS實作了空間預配置設定和惰性空間釋放兩種政策：
1、空間預配置設定：對字元串進行空間擴充的時候，擴充的記憶體比實際需要的多，這樣可以減少連續執行字元串增長操作所需的記憶體重配置設定次數。
2、惰性空間釋放：對字元串進行縮短操作時，程式不立即使用記憶體重新配置設定來回收縮短後多餘的位元組，而是使用 free 屬性将這些位元組的數量記錄下來，等待後續使用。（當然SDS也提供了相應的API，當我們有需要時，也可以手動釋放這些未使用的空間。）
④、二進制安全
因為C字元串以空字元作為字元串結束的辨別，而對于一些二進制檔案（如圖檔等），内容可能包括空字元串，是以C字元串無法正确存取；而所有 SDS 的API 都是以處理二進制的方式來處理 buf 裡面的元素，并且 SDS 不是以空字元串來判斷是否結束，而是以 len 屬性表示的長度來判斷字元串是否結束。
⑤、相容部分 C 字元串函數
雖然 SDS 是二進制安全的，但是一樣遵從每個字元串都是以空字元串結尾的慣例，這樣可以重用 C 語言庫<string.h> 中的一部分函數。
⑥、總結
一般來說，SDS 除了儲存資料庫中的字元串值以外，SDS 還可以作為緩沖區（buffer）：包括 AOF 子產品中的AOF緩沖區以及用戶端狀态中的輸入緩沖區。後面在介紹Redis的持久化時會進行介紹。
3、連結清單
連結清單是一種常用的資料結構，C 語言内部是沒有内置這種資料結構的實作，是以Redis自己建構了連結清單的實作。關于連結清單的詳細介紹可以參考我的
這篇部落格。
連結清單定義：
typedef struct listNode{
//前置節點
struct listNode *prev;
//後置節點
struct listNode *next;
//節點的值
void *value;
}listNode 通過多個 listNode 結構就可以組成連結清單，這是一個雙端連結清單，Redis還提供了操作連結清單的資料結構：
typedef struct list{
//表頭節點
listNode *head;
//表尾節點
listNode *tail;
//連結清單所包含的節點數量
unsigned long len;
//節點值複制函數
void (*free) (void *ptr);
//節點值釋放函數
void (*free) (void *ptr);
//節點值對比函數
int (*match) (void *ptr,void *key);
}list;
Redis連結清單特性：
①、雙端：連結清單具有前置節點和後置節點的引用，擷取這兩個節點時間複雜度都為O(1)。
②、無環：表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL,對連結清單的通路都是以 NULL 結束。
③、帶連結清單長度計數器：通過 len 屬性擷取連結清單長度的時間複雜度為 O(1)。
④、多态：連結清單節點使用 void* 指針來儲存節點值，可以儲存各種不同類型的值。
4、字典
字典又稱為符号表或者關聯數組、或映射（map），是一種用于儲存鍵值對的抽象資料結構。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進行查找或修改。C 語言中沒有内置這種資料結構的實作，是以字典依然是 Redis自己建構的。
Redis 的字典使用哈希表作為底層實作，關于哈希表的詳細講解可以參考我
哈希表結構定義：
typedef struct dictht{
//哈希表數組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值
//總是等于 size-1
unsigned long sizemask;
//該哈希表已有節點的數量
unsigned long used;
}dictht
哈希表是由數組 table 組成，table 中每個元素都是指向 dict.h/dictEntry 結構，dictEntry 結構定義如下：
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一個哈希表節點，形成連結清單
struct dictEntry *next;
}dictEntry
key 用來儲存鍵，val 屬性用來儲存值，值可以是一個指針，也可以是uint64_t整數，也可以是int64_t整數。
注意這裡還有一個指向下一個哈希表節點的指針，我們知道哈希表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放位址法和鍊位址法。這裡采用的便是鍊位址法，通過next這個指針可以将多個哈希值相同的鍵值對連接配接在一起，用來解決哈希沖突。
①、雜湊演算法：Redis計算哈希值和索引值方法如下：
#1、使用字典設定的哈希函數，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
#2、使用哈希表的sizemask屬性和第一步得到的哈希值，計算索引值
index = hash & dict->ht[x].sizemask;
②、解決哈希沖突：這個問題上面我們介紹了，方法是鍊位址法。通過字典裡面的 *next 指針指向下一個具有相同索引值的哈希表節點。
③、擴容和收縮：當哈希表儲存的鍵值對太多或者太少時，就要通過 rerehash(重新散列）來對哈希表進行相應的擴充或者收縮。具體步驟：
1、如果執行擴充操作，會基于原哈希表建立一個大小等于 ht[0].used*2n 的哈希表（也就是每次擴充都是根據原哈希表已使用的空間擴大一倍建立另一個哈希表）。相反如果執行的是收縮操作，每次收縮是根據已使用空間縮小一倍建立一個新的哈希表。
2、重新利用上面的雜湊演算法，計算索引值，然後将鍵值對放到新的哈希表位置上。
3、所有鍵值對都遷徙完畢後，釋放原哈希表的記憶體空間。
④、觸發擴容的條件：
1、伺服器目前沒有執行 BGSAVE 指令或者 BGREWRITEAOF 指令，并且負載因子大于等于1。
2、伺服器目前正在執行 BGSAVE 指令或者 BGREWRITEAOF 指令，并且負載因子大于等于5。
ps：負載因子 = 哈希表已儲存節點數量 / 哈希表大小。
⑤、漸近式 rehash
什麼叫漸進式 rehash？也就是說擴容和收縮操作不是一次性、集中式完成的，而是分多次、漸進式完成的。如果儲存在Redis中的鍵值對隻有幾個幾十個，那麼 rehash 操作可以瞬間完成，但是如果鍵值對有幾百萬，幾千萬甚至幾億，那麼要一次性的進行 rehash，勢必會造成Redis一段時間内不能進行别的操作。是以Redis采用漸進式 rehash,這樣在進行漸進式rehash期間，字典的删除查找更新等操作可能會在兩個哈希表上進行，第一個哈希表沒有找到，就會去第二個哈希表上進行查找。但是進行 增加操作，一定是在新的哈希表上進行的。
5、跳躍表
關于跳躍表的趣味介紹：
http://blog.jobbole.com/111731/跳躍表（skiplist）是一種有序資料結構，它通過在每個節點中維持多個指向其它節點的指針，進而達到快速通路節點的目的。具有如下性質：
1、由很多層結構組成；
2、每一層都是一個有序的連結清單，排列順序為由高層到底層，都至少包含兩個連結清單節點，分别是前面的head節點和後面的nil節點；
3、最底層的連結清單包含了所有的元素；
4、如果一個元素出現在某一層的連結清單中，那麼在該層之下的連結清單也全都會出現（上一層的元素是目前層的元素的子集）；
5、連結清單中的每個節點都包含兩個指針，一個指向同一層的下一個連結清單節點，另一個指向下一層的同一個連結清單節點；
Redis中跳躍表節點定義如下：
typedef struct zskiplistNode {
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//後退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
} zskiplistNode
多個跳躍表節點構成一個跳躍表：
typedef struct zskiplist{
//表頭節點和表尾節點
structz skiplistNode *header, *tail;
//表中節點的數量
unsigned long length;
//表中層數最大的節點的層數
int level;
}zskiplist;
①、搜尋：從最高層的連結清單節點開始，如果比目前節點要大和比目前層的下一個節點要小，那麼則往下找，也就是和目前層的下一層的節點的下一個節點進行比較，以此類推，一直找到最底層的最後一個節點，如果找到則傳回，反之則傳回空。
②、插入：首先确定插入的層數，有一種方法是假設抛一枚硬币，如果是正面就累加，直到遇見反面為止，最後記錄正面的次數作為插入的層數。當确定插入的層數k後，則需要将新元素插入到從底層到k層。
③、删除：在各個層中找到包含指定值的節點，然後将節點從連結清單中删除即可，如果删除以後隻剩下頭尾兩個節點，則删除這一層。
6、整數集合
整數集合（intset）是Redis用于儲存整數值的集合抽象資料類型，它可以儲存類型為int16_t、int32_t 或者int64_t 的整數值，并且保證集合中不會出現重複元素。
定義如下：
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素數量
uint32_t length;
//儲存元素的數組
int8_t contents[];
}intset;
整數集合的每個元素都是 contents 數組的一個資料項，它們按照從小到大的順序排列，并且不包含任何重複項。
length 屬性記錄了 contents 數組的大小。
需要注意的是雖然 contents 數組聲明為 int8_t 類型，但是實際上contents 數組并不儲存任何 int8_t 類型的值，其真正類型有 encoding 來決定。
①、更新
當我們新增的元素類型比原集合元素類型的長度要大時，需要對整數集合進行更新，才能将新元素放入整數集合中。具體步驟：
1、根據新元素類型，擴充整數集合底層數組的大小，并為新元素配置設定空間。
2、将底層數組現有的所有元素都轉成與新元素相同類型的元素，并将轉換後的元素放到正确的位置，放置過程中，維持整個元素順序都是有序的。
3、将新元素添加到整數集合中（保證有序）。
更新能極大地節省記憶體。
②、降級
整數集合不支援降級操作，一旦對數組進行了更新，編碼就會一直保持更新後的狀态。
7、壓縮清單
壓縮清單（ziplist）是Redis為了節省記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮清單可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值。
壓縮清單的原理：壓縮清單并不是對資料利用某種算法進行壓縮，而是将資料按照一定規則編碼在一塊連續的記憶體區域，目的是節省記憶體。
壓縮清單的每個節點構成如下：
①、previous_entry_ength：記錄壓縮清單前一個位元組的長度。previous_entry_ength的長度可能是1個位元組或者是5個位元組，如果上一個節點的長度小于254，則該節點隻需要一個位元組就可以表示前一個節點的長度了，如果前一個節點的長度大于等于254，則previous length的第一個位元組為254，後面用四個位元組表示目前節點前一個節點的長度。利用此原理即目前節點位置減去上一個節點的長度即得到上一個節點的起始位置，壓縮清單可以從尾部向頭部周遊。這麼做很有效地減少了記憶體的浪費。
②、encoding：節點的encoding儲存的是節點的content的内容類型以及長度，encoding類型一共有兩種，一種位元組數組一種是整數，encoding區域長度為1位元組、2位元組或者5位元組長。
③、content：content區域用于儲存節點的内容，節點内容類型和長度由encoding決定。
8、總結
大多數情況下，Redis使用簡單字元串SDS作為字元串的表示，相對于C語言字元串，SDS具有常數複雜度擷取字元串長度，杜絕了緩存區的溢出，減少了修改字元串長度時所需的記憶體重配置設定次數，以及二進制安全能存儲各種類型的檔案，并且還相容部分C函數。
通過為連結清單設定不同類型的特定函數，Redis連結清單可以儲存各種不同類型的值，除了用作清單鍵，還在釋出與訂閱、慢查詢、螢幕等方面發揮作用（後面會介紹）。
Redis的字典底層使用哈希表實作，每個字典通常有兩個哈希表，一個平時使用，另一個用于rehash時使用，使用鍊位址法解決哈希沖突。
跳躍表通常是有序集合的底層實作之一，表中的節點按照分值大小進行排序。
整數集合是集合鍵的底層實作之一，底層由數組構成，更新特性能盡可能的節省記憶體。
壓縮清單是Redis為節省記憶體而開發的順序型資料結構，通常作為清單鍵和哈希鍵的底層實作之一。
以上介紹的簡單字元串、連結清單、字典、跳躍表、整數集合、壓縮清單等資料結構就是Redis底層的一些資料結構，用來實作上一篇部落格介紹的Redis五大資料類型，那麼每種資料類型是由哪些資料結構實作的呢？下一篇部落格進行介紹。
參考文檔：《Redis設計與實作》
作者：
YSOcean出處：
http://www.cnblogs.com/ysocean/本文版權歸作者所有，歡迎轉載，但未經作者同意不能轉載，否則保留追究法律責任的權利。