Redis支持五種數(shù)據(jù)類型：string（字符串），hash（哈希），list（列表）悬秉，set（集合）及zset(sorted set：有序集合)。
這些數(shù)據(jù)類型的底層實(shí)現(xiàn)如下圖所示冰蘑。
一和泌、字符串
在Redis里面，C字符串只會作為字符串字面量用在一些無須對字符串值進(jìn)行修改的地方祠肥。當(dāng)Redis需要的不僅僅是一個(gè)字符串字面量允跑，而是一個(gè)可以被修改的字符串值時(shí)，Redis就會使用SDS來表示字符串值。
SDS的定義：
struct sdshdr{
??? int len; //已使用的字節(jié)數(shù)聋丝；
??? int free; //未使用的字節(jié)數(shù)索烹；
??? char buf[]; //字節(jié)數(shù)組，用來保存字符串
}
因?yàn)镃字符串并不記錄自身的長度信息弱睦，所以獲取長度的時(shí)間復(fù)雜度的時(shí)間復(fù)雜度為O(N)百姓，而SDS在len屬性里記錄了SDS本身的長度，所以獲取長度的時(shí)間復(fù)雜度為O(1)况木。通過使用sds使得redis獲取字符串長度的時(shí)間復(fù)雜度從O(N)降為O(1)垒拢，確保了獲取字符串長度的工作不會成為redis的性能瓶頸。
另外火惊，C字符串在修改時(shí)可能會導(dǎo)致緩沖區(qū)溢出求类，而SDS進(jìn)行修改時(shí)，API會先檢查SDS的空間是否滿足所需的要求屹耐，如果不滿足的話API會自動(dòng)將SDS的空間擴(kuò)展至執(zhí)行修改需要的大小尸疆。杜絕了C字符串可能出現(xiàn)的緩沖區(qū)溢出問題。
C字符串每次進(jìn)行變更（增加或者縮短）時(shí)都要進(jìn)行一次空間重分配惶岭，對redis而言寿弱，頻繁的內(nèi)存分配不符合redis對性能的要求，所以redis通過空間預(yù)付配和空間惰性釋的策略來提高性能按灶。所謂的空間預(yù)分配是指每次需要對SDS進(jìn)行空間擴(kuò)展的時(shí)候症革，程序不僅會為SDS分配其所必需的空間，還會分配額外的未使用空間鸯旁。所謂的惰性釋放是指當(dāng)SDS需要縮短操作時(shí)噪矛，程序并不立即使用內(nèi)存重分配來回收多出來的內(nèi)存，而是使用free屬性記錄多出來的字符以備未來使用铺罢。
二艇挨、列表
redis的底層實(shí)現(xiàn)是ziplist或雙向列表。
List類型的key創(chuàng)建時(shí)使用zip list結(jié)構(gòu)存儲畏铆，robj對象的encoding字段設(shè)置為REDIS_ENCODING_ZIPLIST雷袋。zip list實(shí)現(xiàn)細(xì)節(jié)可參考[3]吉殃。概況來講辞居，zip list通過一個(gè)連續(xù)的內(nèi)存塊實(shí)現(xiàn)list結(jié)構(gòu)，其中的每個(gè)entry節(jié)點(diǎn)頭部保存前后節(jié)點(diǎn)長度信息蛋勺，實(shí)現(xiàn)雙向鏈表功能瓦灶。這個(gè)頭部可根據(jù)前后entry長度進(jìn)行內(nèi)存壓縮，而如果直接使用指針的話則至少需要兩個(gè)指針抱完，對64位系統(tǒng)來說將占用16個(gè)字節(jié)贼陶，使用zip list時(shí)最好情況下只需要兩個(gè)字節(jié)，這在具有大量list類型的key-value對且各個(gè)value較小的應(yīng)用來說，可以節(jié)省大量內(nèi)存碉怔。
當(dāng)list的elem數(shù)小于配置值: hash-max-ziplist-entries 或者elem_value字符串的長度小于 hash-max-ziplist-value, 可以編碼成 REDIS_ENCODING_ZIPLIST 類型存儲,以節(jié)約內(nèi)存烘贴；但由于在zip list添加和刪除元素會涉及到數(shù)據(jù)移動(dòng)，因此當(dāng)list內(nèi)容較多時(shí)撮胧，轉(zhuǎn)而使用雙向鏈表桨踪。
2.1 壓縮列表
zlbytes: 整個(gè)列表所占的字節(jié)數(shù)
zltail: 尾節(jié)點(diǎn)距離起始地址有多少字節(jié)，通過該屬性可以直接訪問到列表結(jié)尾芹啥。
zllen: 節(jié)點(diǎn)數(shù)
zlend: 0XFF锻离，用于標(biāo)記末端
每個(gè)節(jié)點(diǎn)有3部分組成
previous_entry_length: 前一個(gè)節(jié)點(diǎn)的長度，當(dāng)前一節(jié)點(diǎn)長度小于254時(shí)其長度為1字節(jié)墓怀，當(dāng)前一節(jié)點(diǎn)長度大于等于254時(shí)其長度為5字節(jié)汽纠。因此在極端情況下插入大節(jié)點(diǎn)或刪除小節(jié)點(diǎn)可能引發(fā)連鎖更新。通過該屬性可以實(shí)現(xiàn)列表節(jié)點(diǎn)的倒序訪問傀履，達(dá)到類似鏈表的性能虱朵。
encoding: 編碼方式，用于標(biāo)識節(jié)點(diǎn)存的內(nèi)容是數(shù)字還是字節(jié)數(shù)組啤呼。
content: 保存的內(nèi)容卧秘。
2.2 雙向鏈表
struct list{
??? listNode* head;
??? listNode* tail;
??? unsigned long len;? //鏈表節(jié)點(diǎn)數(shù)量
}
三、哈希對象
哈希對象的底層實(shí)現(xiàn)是壓縮列表或字典官扣。
3.1 字典
typedef struct dictht{
?????//哈希表數(shù)組
?????dictEntry **table;
?????//哈希表大小
?????unsigned longsize;
?????//哈希表大小掩碼翅敌，用于計(jì)算索引值
?????//總是等于 size-1
?????unsigned longsizemask;
?????//該哈希表已有節(jié)點(diǎn)的數(shù)量
?????unsigned longused;
}dictht
typedefstructdictEntry{
?????//鍵
?????void*key;
?????//值
?????union{
??????????void*val;
??????????uint64_tu64;
??????????int64_ts64;
?????}v;
?????//指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
?????structdictEntry *next;
}dictEntry
key 用來保存鍵惕蹄，val 屬性用來保存值蚯涮，值可以是一個(gè)指針，也可以是uint64_t整數(shù)卖陵，也可以是int64_t整數(shù)遭顶。
注意這里還有一個(gè)指向下一個(gè)哈希表節(jié)點(diǎn)的指針，我們知道哈希表最大的問題是存在哈希沖突泪蔫，如何解決哈希沖突棒旗，有開放地址法和鏈地址法。這里采用的便是鏈地址法撩荣，通過next這個(gè)指針可以將多個(gè)哈希值相同的鍵值對連接在一起铣揉，用來解決哈希沖突。
①餐曹、哈希算法：Redis計(jì)算哈希值和索引值方法如下：
#1逛拱、使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
#2台猴、使用哈希表的sizemask屬性和第一步得到的哈希值朽合，計(jì)算索引值
index = hash & dict->ht[x].sizemask;
②俱两、解決哈希沖突：這個(gè)問題上面我們介紹了，方法是鏈地址法曹步。通過字典里面的 *next 指針指向下一個(gè)具有相同索引值的哈希表節(jié)點(diǎn)宪彩。因?yàn)閐ictEntry節(jié)點(diǎn)組成的鏈表沒有指向鏈表結(jié)尾的指針，所以為了速度考慮總是將新節(jié)點(diǎn)添加到鏈表的表頭位置讲婚。
③毯焕、擴(kuò)容和收縮：當(dāng)哈希表保存的鍵值對太多或者太少時(shí)，就要通過 rerehash(重新散列）來對哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮磺樱。具體步驟：
1纳猫、如果執(zhí)行擴(kuò)展操作，會基于原哈希表創(chuàng)建一個(gè)大小等于 ht[0].used*2n 的哈希表（也就是每次擴(kuò)展都是根據(jù)原哈希表已使用的空間擴(kuò)大一倍創(chuàng)建另一個(gè)哈希表）竹捉。相反如果執(zhí)行的是收縮操作芜辕，每次收縮是根據(jù)已使用空間縮小一倍創(chuàng)建一個(gè)新的哈希表。
2块差、重新利用上面的哈希算法侵续，計(jì)算索引值，然后將鍵值對放到新的哈希表位置上憨闰。
3状蜗、所有鍵值對都遷徙完畢后，釋放原哈希表的內(nèi)存空間鹉动。
④轧坎、觸發(fā)擴(kuò)容的條件：
1、服務(wù)器目前沒有執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令泽示，并且負(fù)載因子大于等于1缸血。
2、服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令械筛，并且負(fù)載因子大于等于5捎泻。
ps：負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小。
⑤埋哟、漸近式 rehash
從0開始笆豁，在每次對字典的增加、刪除赤赊、查找和更新操作后闯狱，對某一hash值的所有鍵值對rehash到另一新的哈希表上直至所有鍵值對都完成操作。也就是說擴(kuò)容和收縮操作不是一次性砍鸠、集中式完成的扩氢，而是分多次耕驰、漸進(jìn)式完成的爷辱。如果保存在Redis中的鍵值對只有幾個(gè)幾十個(gè)，那么rehash 操作可以瞬間完成，但是如果鍵值對有幾百萬饭弓，幾千萬甚至幾億双饥，那么要一次性的進(jìn)行rehash，勢必會造成Redis一段時(shí)間內(nèi)不能進(jìn)行別的操作弟断。所以Redis采用漸進(jìn)式rehash咏花，這樣在進(jìn)行漸進(jìn)式rehash期間，字典的刪除查找更新等操作可能會在兩個(gè)哈希表上進(jìn)行阀趴，第一個(gè)哈希表沒有找到昏翰，就會去第二個(gè)哈希表上進(jìn)行查找。但是進(jìn)行增加操作刘急，一定是在新的哈希表上進(jìn)行的棚菊。
redis自身的底層數(shù)據(jù)結(jié)構(gòu)就是一個(gè)字典。
四叔汁、集合
set的底層實(shí)現(xiàn)是intset和table统求。
4.1 整數(shù)集合
typedef struct intset{
?????//編碼方式
?????uint32_t encoding;
?????//集合包含的元素?cái)?shù)量
?????uint32_t length;
?????//保存元素的數(shù)組
?????int8_t contents[];
}intset;
整數(shù)集合的每個(gè)元素都是 contents 數(shù)組的一個(gè)數(shù)據(jù)項(xiàng)，它們按照從小到大的順序排列据块，并且不包含任何重復(fù)項(xiàng)码邻。
length 屬性記錄了 contents 數(shù)組的大小。
需要注意的是雖然 contents 數(shù)組聲明為 int8_t 類型另假，但是實(shí)際上contents 數(shù)組并不保存任何 int8_t 類型的值像屋，其真正類型有 encoding 來決定。
①边篮、升級
當(dāng)我們新增的元素類型比原集合元素類型的長度要大時(shí)开睡，需要對整數(shù)集合進(jìn)行升級，才能將新元素放入整數(shù)集合中苟耻。具體步驟：
1篇恒、根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組的大小凶杖，并為新元素分配空間胁艰。
2、將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)成與新元素相同類型的元素智蝠，并將轉(zhuǎn)換后的元素放到正確的位置腾么，放置過程中，維持整個(gè)元素順序都是有序的杈湾。
3解虱、將新元素添加到整數(shù)集合中（保證有序）。
升級能極大地節(jié)省內(nèi)存漆撞。
②殴泰、降級
整數(shù)集合不支持降級操作于宙，一旦對數(shù)組進(jìn)行了升級，編碼就會一直保持升級后的狀態(tài)悍汛。
五捞魁、有序集合
有序集合的底層實(shí)現(xiàn)是壓縮列表或跳躍表。
5.1 跳躍表
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)离咐，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其它節(jié)點(diǎn)的指針谱俭，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。具有如下性質(zhì)：
1宵蛀、由很多層結(jié)構(gòu)組成昆著；
2、每一層都是一個(gè)有序的鏈表术陶，排列順序?yàn)橛筛邔拥降讓有ǎ贾辽侔瑑蓚€(gè)鏈表節(jié)點(diǎn)，分別是前面的head節(jié)點(diǎn)和后面的nil節(jié)點(diǎn)瞳别；
3征候、最底層的鏈表包含了所有的元素；
4祟敛、如果一個(gè)元素出現(xiàn)在某一層的鏈表中疤坝，那么在該層之下的鏈表也全都會出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）；
5馆铁、鏈表中的每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針跑揉，一個(gè)指向同一層的下一個(gè)鏈表節(jié)點(diǎn)，另一個(gè)指向下一層的同一個(gè)鏈表節(jié)點(diǎn)埠巨；
±①、搜索：從最高層的鏈表節(jié)點(diǎn)開始辣垒，如果比當(dāng)前節(jié)點(diǎn)要大和比當(dāng)前層的下一個(gè)節(jié)點(diǎn)要小望侈，那么則往下找，也就是和當(dāng)前層的下一層的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)進(jìn)行比較勋桶，以此類推脱衙，一直找到最底層的最后一個(gè)節(jié)點(diǎn)，如果找到則返回例驹，反之則返回空捐韩。
②鹃锈、插入：首先確定插入的層數(shù)荤胁，有一種方法是假設(shè)拋一枚硬幣，如果是正面就累加屎债，直到遇見反面為止仅政，最后記錄正面的次數(shù)作為插入的層數(shù)垢油。當(dāng)確定插入的層數(shù)k后，則需要將新元素插入到從底層到k層已旧。
③召娜、刪除：在各個(gè)層中找到包含指定值的節(jié)點(diǎn)运褪，然后將節(jié)點(diǎn)從鏈表中刪除即可，如果刪除以后只剩下頭尾兩個(gè)節(jié)點(diǎn)玖瘸，則刪除這一層秸讹。
??? 跳躍表支持時(shí)間復(fù)雜度平均O(logN)的查找，效率可以和平衡樹相媲美雅倒，因此很多程序使用跳躍表來代替平衡樹璃诀。
