1. 演示數(shù)據(jù)類型的實現(xiàn)
????????上篇博客我們在介紹 key 相關(guān)命令的時候王凑，介紹了如下命令：
```
OBJECT ENCODING? ? key
```
????????該命令是用來顯示那五大數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)簇搅。
????????比如對于 string 數(shù)據(jù)類型：
(1).string
????????在使用string存儲字符串的時候返回的是"embstr",存儲數(shù)字的時候返回的就是“int”片吊。
(2).hash
????????在使用hash的時候無論是存儲字符串還是數(shù)字返回的都是"ziplist"日戈。
(3).list
????????使用list存儲字符串還是數(shù)字返回的都是“quicklist”贡必。
(4).set
????????set存儲純數(shù)字的時候返回的是"intset",存儲包含字符串的時候返回的是"hashtable"登馒。
(5).zset
????????使用zset存儲數(shù)字或者字符串都是返回的"ziplist"式曲。
2.簡單動態(tài)字符串
????????Redis 是用 C 語言寫的，但是對于Redis的字符串发笔，卻不是 C 語言中的字符串（即以空字符’\0’結(jié)尾的字符數(shù)組）盟萨，它是自己構(gòu)建了一種名為 簡單動態(tài)字符串（simple dynamic string,SDS）的抽象類型，并將 SDS 作為 Redis的默認(rèn)字符串表示了讨。
SDS 定義：
```
struct?sdshdr{
?????//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
?????//等于 SDS 保存字符串的長度
?????int?len;
?????//記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
?????int?free;
?????//字節(jié)數(shù)組捻激，用于保存字符串
?????char?buf[];
}
```
用SDS保存字符串 “Redis”具體圖示如下：
圖片來源：《Redis設(shè)計與實現(xiàn)》
? 我們看上面對于 SDS 數(shù)據(jù)類型的定義：
1制轰、len 保存了SDS保存字符串的長度
2、buf[] 數(shù)組用來保存字符串的每個元素
3胞谭、free j記錄了 buf 數(shù)組中未使用的字節(jié)數(shù)量
上面的定義相對于 C 語言對于字符串的定義垃杖，多出了 len 屬性以及 free 屬性。為什么不使用C語言字符串實現(xiàn)丈屹，而是使用 SDS呢调俘？這樣實現(xiàn)有什么好處？
①旺垒、常數(shù)復(fù)雜度獲取字符串長度
由于 len 屬性的存在彩库，我們獲取 SDS 字符串的長度只需要讀取 len 屬性，時間復(fù)雜度為 O(1)先蒋。而對于 C 語言骇钦，獲取字符串的長度通常是經(jīng)過遍歷計數(shù)來實現(xiàn)的，時間復(fù)雜度為 O(n)竞漾。通過 strlen key 命令可以獲取 key 的字符串長度眯搭。
②、杜絕緩沖區(qū)溢出
我們知道在 C 語言中使用 strcat? 函數(shù)來進行兩個字符串的拼接业岁，一旦沒有分配足夠長度的內(nèi)存空間鳞仙，就會造成緩沖區(qū)溢出。而對于 SDS 數(shù)據(jù)類型笔时，在進行字符修改的時候繁扎，會首先根據(jù)記錄的 len 屬性檢查內(nèi)存空間是否滿足需求，如果不滿足糊闽，會進行相應(yīng)的空間擴展，然后在進行修改操作爹梁，所以不會出現(xiàn)緩沖區(qū)溢出右犹。
③、減少修改字符串的內(nèi)存重新分配次數(shù)
C語言由于不記錄字符串的長度姚垃，所以如果要修改字符串念链，必須要重新分配內(nèi)存（先釋放再申請），因為如果沒有重新分配积糯，字符串長度增大時會造成內(nèi)存緩沖區(qū)溢出掂墓，字符串長度減小時會造成內(nèi)存泄露。
而對于SDS看成，由于len屬性和free屬性的存在君编，對于修改字符串SDS實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種策略：
1、空間預(yù)分配：對字符串進行空間擴展的時候川慌，擴展的內(nèi)存比實際需要的多吃嘿，這樣可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)祠乃。
2、惰性空間釋放：對字符串進行縮短操作時兑燥，程序不立即使用內(nèi)存重新分配來回收縮短后多余的字節(jié)亮瓷，而是使用 free 屬性將這些字節(jié)的數(shù)量記錄下來，等待后續(xù)使用降瞳。（當(dāng)然SDS也提供了相應(yīng)的API嘱支，當(dāng)我們有需要時，也可以手動釋放這些未使用的空間挣饥。）
④除师、二進制安全
因為C字符串以空字符作為字符串結(jié)束的標(biāo)識，而對于一些二進制文件（如圖片等）亮靴，內(nèi)容可能包括空字符串馍盟，因此C字符串無法正確存取茧吊；而所有 SDS 的API 都是以處理二進制的方式來處理 buf 里面的元素贞岭，并且 SDS 不是以空字符串來判斷是否結(jié)束，而是以 len 屬性表示的長度來判斷字符串是否結(jié)束搓侄。
⑤瞄桨、兼容部分 C 字符串函數(shù)
雖然 SDS 是二進制安全的，但是一樣遵從每個字符串都是以空字符串結(jié)尾的慣例讶踪，這樣可以重用 C 語言庫<string.h> 中的一部分函數(shù)芯侥。
⑥、總結(jié)
一般來說乳讥，SDS 除了保存數(shù)據(jù)庫中的字符串值以外柱查，SDS 還可以作為緩沖區(qū)（buffer）：包括 AOF 模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的輸入緩沖區(qū)。后面在介紹Redis的持久化時會進行介紹云石。
3.鏈表
????????鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)唉工，C 語言內(nèi)部是沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，所以Redis自己構(gòu)建了鏈表的實現(xiàn)汹忠。關(guān)于鏈表的詳細(xì)介紹可以參考網(wǎng)上的資料淋硝。
鏈表定義：
```
typedef?struct?listNode{
???????//前置節(jié)點
???????struct?listNode *prev;
???????//后置節(jié)點
???????struct?listNode *next;
???????//節(jié)點的值
???????void?*value;??
}listNode
```
????????通過多個 listNode 結(jié)構(gòu)就可以組成鏈表，這是一個雙端鏈表宽菜，Redis還提供了操作鏈表的數(shù)據(jù)結(jié)構(gòu)：
```
typedef?struct?list{
?????//表頭節(jié)點
?????listNode *head;
?????//表尾節(jié)點
?????listNode *tail;
?????//鏈表所包含的節(jié)點數(shù)量
?????unsigned?long?len;
?????//節(jié)點值復(fù)制函數(shù)
?????void?(*free) (void?*ptr);
?????//節(jié)點值釋放函數(shù)
?????void?(*free) (void?*ptr);
?????//節(jié)點值對比函數(shù)
?????int?(*match) (void?*ptr,void?*key);
}list;
```
Redis鏈表特性：
∫ド拧①、雙端：鏈表具有前置節(jié)點和后置節(jié)點的引用铅乡，獲取這兩個節(jié)點時間復(fù)雜度都為O(1)继谚。
②阵幸、無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結(jié)束犬庇。
∩纭③、帶鏈表長度計數(shù)器：通過 len 屬性獲取鏈表長度的時間復(fù)雜度為 O(1)臭挽。
∥娼蟆④、多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值欢峰，可以保存各種不同類型的值葬荷。
4.字典
????????字典又稱為符號表或者關(guān)聯(lián)數(shù)組、或映射（map）纽帖，是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)宠漩。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進行查找或修改懊直。C 語言中沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)扒吁，所以字典依然是 Redis自己構(gòu)建的。
????????Redis 的字典使用哈希表作為底層實現(xiàn)室囊，關(guān)于哈希表的詳細(xì)講解可以參考我這篇博客雕崩。
哈希表結(jié)構(gòu)定義：
```
typedef?struct?dictht{
?????//哈希表數(shù)組
?????dictEntry **table;
?????//哈希表大小
?????unsigned?long?size;
?????//哈希表大小掩碼，用于計算索引值
?????//總是等于 size-1
?????unsigned?long?sizemask;
?????//該哈希表已有節(jié)點的數(shù)量
?????unsigned?long?used;
}dictht
```
哈希表是由數(shù)組 table 組成融撞，table 中每個元素都是指向 dict.h/dictEntry 結(jié)構(gòu)盼铁，dictEntry 結(jié)構(gòu)定義如下：
```
typedef?struct?dictEntry{
?????//鍵
?????void?*key;
?????//值
?????union{
??????????void?*val;
??????????uint64_tu64;
??????????int64_ts64;
?????}v;
?????//指向下一個哈希表節(jié)點，形成鏈表
?????struct?dictEntry *next;
}dictEntry
```
key 用來保存鍵尝偎，val 屬性用來保存值饶火，值可以是一個指針，也可以是uint64_t整數(shù)致扯，也可以是int64_t整數(shù)肤寝。
注意這里還有一個指向下一個哈希表節(jié)點的指針，我們知道哈希表最大的問題是存在哈希沖突抖僵，如何解決哈希沖突醒陆，有開放地址法和鏈地址法。這里采用的便是鏈地址法裆针，通過next這個指針可以將多個哈希值相同的鍵值對連接在一起，用來解決哈希沖突寺晌。
①世吨、哈希算法：Redis計算哈希值和索引值方法如下：
```
#1、使用字典設(shè)置的哈希函數(shù)呻征，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
#2耘婚、使用哈希表的sizemask屬性和第一步得到的哈希值，計算索引值
index = hash & dict->ht[x].sizemask;
```
②陆赋、解決哈希沖突：這個問題上面我們介紹了沐祷，方法是鏈地址法嚷闭。通過字典里面的 *next 指針指向下一個具有相同索引值的哈希表節(jié)點。
③赖临、擴容和收縮：當(dāng)哈希表保存的鍵值對太多或者太少時胞锰，就要通過 rerehash(重新散列）來對哈希表進行相應(yīng)的擴展或者收縮。具體步驟：
1兢榨、如果執(zhí)行擴展操作嗅榕，會基于原哈希表創(chuàng)建一個大小等于 ht[0].used*2n 的哈希表（也就是每次擴展都是根據(jù)原哈希表已使用的空間擴大一倍創(chuàng)建另一個哈希表）。相反如果執(zhí)行的是收縮操作吵聪，每次收縮是根據(jù)已使用空間縮小一倍創(chuàng)建一個新的哈希表凌那。
2、重新利用上面的哈希算法吟逝，計算索引值帽蝶，然后將鍵值對放到新的哈希表位置上。
3块攒、所有鍵值對都遷徙完畢后励稳，釋放原哈希表的內(nèi)存空間。
④局蚀、觸發(fā)擴容的條件：
1麦锯、服務(wù)器目前沒有執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于1琅绅。
2扶欣、服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于5千扶。
ps：負(fù)載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小料祠。
⑤、漸近式 rehash
什么叫漸進式 rehash澎羞？也就是說擴容和收縮操作不是一次性髓绽、集中式完成的，而是分多次妆绞、漸進式完成的顺呕。如果保存在Redis中的鍵值對只有幾個幾十個，那么 rehash 操作可以瞬間完成括饶，但是如果鍵值對有幾百萬株茶，幾千萬甚至幾億，那么要一次性的進行 rehash图焰，勢必會造成Redis一段時間內(nèi)不能進行別的操作启盛。所以Redis采用漸進式 rehash,這樣在進行漸進式rehash期間，字典的刪除查找更新等操作可能會在兩個哈希表上進行，第一個哈希表沒有找到僵闯，就會去第二個哈希表上進行查找卧抗。但是進行 增加操作，一定是在新的哈希表上進行的鳖粟。
5.跳躍表
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)社裆，它通過在每個節(jié)點中維持多個指向其它節(jié)點的指針，從而達到快速訪問節(jié)點的目的牺弹。具有如下性質(zhì)：
1浦马、由很多層結(jié)構(gòu)組成；
2张漂、每一層都是一個有序的鏈表晶默，排列順序為由高層到底層，都至少包含兩個鏈表節(jié)點航攒，分別是前面的head節(jié)點和后面的nil節(jié)點磺陡；
3、最底層的鏈表包含了所有的元素漠畜；
4币他、如果一個元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）憔狞；
5蝴悉、鏈表中的每個節(jié)點都包含兩個指針，一個指向同一層的下一個鏈表節(jié)點瘾敢，另一個指向下一層的同一個鏈表節(jié)點拍冠；
Redis中跳躍表節(jié)點定義如下：
```
typedef?struct?zskiplistNode {
?????//層
?????struct?zskiplistLevel{
???????????//前進指針
???????????struct?zskiplistNode *forward;
???????????//跨度
???????????unsigned?int?span;
?????}level[];
?????//后退指針
?????struct?zskiplistNode *backward;
?????//分值
?????double?score;
?????//成員對象
?????robj *obj;
} zskiplistNode
```
多個跳躍表節(jié)點構(gòu)成一個跳躍表：
```
typedef?struct?zskiplist{
?????//表頭節(jié)點和表尾節(jié)點
?????structz skiplistNode *header, *tail;
?????//表中節(jié)點的數(shù)量
?????unsigned?long?length;
?????//表中層數(shù)最大的節(jié)點的層數(shù)
?????int?level;
}zskiplist;
```
①簇抵、搜索：從最高層的鏈表節(jié)點開始庆杜，如果比當(dāng)前節(jié)點要大和比當(dāng)前層的下一個節(jié)點要小，那么則往下找碟摆，也就是和當(dāng)前層的下一層的節(jié)點的下一個節(jié)點進行比較晃财，以此類推，一直找到最底層的最后一個節(jié)點典蜕，如果找到則返回断盛，反之則返回空。
∮涮颉②钢猛、插入：首先確定插入的層數(shù)，有一種方法是假設(shè)拋一枚硬幣屑宠，如果是正面就累加，直到遇見反面為止仇让，最后記錄正面的次數(shù)作為插入的層數(shù)典奉。當(dāng)確定插入的層數(shù)k后躺翻，則需要將新元素插入到從底層到k層。
∥谰痢③公你、刪除：在各個層中找到包含指定值的節(jié)點，然后將節(jié)點從鏈表中刪除即可假瞬，如果刪除以后只剩下頭尾兩個節(jié)點陕靠，則刪除這一層。
6.整數(shù)集合
????????整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)類型脱茉，它可以保存類型為int16_t剪芥、int32_t 或者int64_t 的整數(shù)值，并且保證集合中不會出現(xiàn)重復(fù)元素琴许。
定義如下：
```
typedef?struct?intset{
?????//編碼方式
?????uint32_t encoding;
?????//集合包含的元素數(shù)量
?????uint32_t length;
?????//保存元素的數(shù)組
?????int8_t contents[];
}intset;
```
????????整數(shù)集合的每個元素都是 contents 數(shù)組的一個數(shù)據(jù)項税肪，它們按照從小到大的順序排列，并且不包含任何重復(fù)項榜田。
length 屬性記錄了 contents 數(shù)組的大小益兄。
需要注意的是雖然 contents 數(shù)組聲明為 int8_t 類型，但是實際上contents 數(shù)組并不保存任何 int8_t 類型的值箭券，其真正類型有 encoding 來決定净捅。
①、升級
當(dāng)我們新增的元素類型比原集合元素類型的長度要大時辩块，需要對整數(shù)集合進行升級蛔六，才能將新元素放入整數(shù)集合中。具體步驟：
1庆捺、根據(jù)新元素類型古今，擴展整數(shù)集合底層數(shù)組的大小，并為新元素分配空間滔以。
2捉腥、將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)成與新元素相同類型的元素，并將轉(zhuǎn)換后的元素放到正確的位置你画，放置過程中抵碟，維持整個元素順序都是有序的。
3坏匪、將新元素添加到整數(shù)集合中（保證有序）拟逮。
升級能極大地節(jié)省內(nèi)存。
②适滓、降級
整數(shù)集合不支持降級操作敦迄，一旦對數(shù)組進行了升級，編碼就會一直保持升級后的狀態(tài)。
7罚屋、壓縮列表
????????壓縮列表（ziplist）是Redis為了節(jié)省內(nèi)存而開發(fā)的苦囱，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，一個壓縮列表可以包含任意多個節(jié)點（entry）脾猛，每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值撕彤。
? ??????壓縮列表的原理：壓縮列表并不是對數(shù)據(jù)利用某種算法進行壓縮，而是將數(shù)據(jù)按照一定規(guī)則編碼在一塊連續(xù)的內(nèi)存區(qū)域猛拴，目的是節(jié)省內(nèi)存羹铅。
壓縮列表的每個節(jié)點構(gòu)成如下：
①愉昆、previous_entry_ength：記錄壓縮列表前一個字節(jié)的長度职员。previous_entry_ength的長度可能是1個字節(jié)或者是5個字節(jié)，如果上一個節(jié)點的長度小于254撼唾，則該節(jié)點只需要一個字節(jié)就可以表示前一個節(jié)點的長度了廉邑，如果前一個節(jié)點的長度大于等于254，則previous length的第一個字節(jié)為254倒谷，后面用四個字節(jié)表示當(dāng)前節(jié)點前一個節(jié)點的長度蛛蒙。利用此原理即當(dāng)前節(jié)點位置減去上一個節(jié)點的長度即得到上一個節(jié)點的起始位置，壓縮列表可以從尾部向頭部遍歷渤愁。這么做很有效地減少了內(nèi)存的浪費牵祟。
②抖格、encoding：節(jié)點的encoding保存的是節(jié)點的content的內(nèi)容類型以及長度诺苹，encoding類型一共有兩種，一種字節(jié)數(shù)組一種是整數(shù)雹拄，encoding區(qū)域長度為1字節(jié)收奔、2字節(jié)或者5字節(jié)長。
∽揖痢③坪哄、content：content區(qū)域用于保存節(jié)點的內(nèi)容，節(jié)點內(nèi)容類型和長度由encoding決定势篡。
8翩肌、總結(jié)
大多數(shù)情況下，Redis使用簡單字符串SDS作為字符串的表示禁悠，相對于C語言字符串念祭，SDS具有常數(shù)復(fù)雜度獲取字符串長度，杜絕了緩存區(qū)的溢出碍侦，減少了修改字符串長度時所需的內(nèi)存重分配次數(shù)粱坤，以及二進制安全能存儲各種類型的文件隶糕，并且還兼容部分C函數(shù)。
通過為鏈表設(shè)置不同類型的特定函數(shù)站玄，Redis鏈表可以保存各種不同類型的值若厚，除了用作列表鍵，還在發(fā)布與訂閱蜒什、慢查詢、監(jiān)視器等方面發(fā)揮作用（后面會介紹）疤估。
Redis的字典底層使用哈希表實現(xiàn)灾常，每個字典通常有兩個哈希表，一個平時使用铃拇，另一個用于rehash時使用钞瀑，使用鏈地址法解決哈希沖突。
跳躍表通常是有序集合的底層實現(xiàn)之一慷荔，表中的節(jié)點按照分值大小進行排序雕什。
整數(shù)集合是集合鍵的底層實現(xiàn)之一，底層由數(shù)組構(gòu)成显晶，升級特性能盡可能的節(jié)省內(nèi)存贷岸。
壓縮列表是Redis為節(jié)省內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)，通常作為列表鍵和哈希鍵的底層實現(xiàn)之一磷雇。
以上介紹的簡單字符串偿警、鏈表、字典唯笙、跳躍表螟蒸、整數(shù)集合、壓縮列表等數(shù)據(jù)結(jié)構(gòu)就是Redis底層的一些數(shù)據(jù)結(jié)構(gòu)崩掘，用來實現(xiàn)上一篇博客介紹的Redis五大數(shù)據(jù)類型七嫌，那么每種數(shù)據(jù)類型是由哪些數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的呢？下一篇博客進行介紹苞慢。
參考文檔：《Redis設(shè)計與實現(xiàn)》
