應用層：

String——字符串

Hash——字典

List——列表

Set——集合

Sorted Set——有序集合

中間層

redisobject

從Redis的使用者的角度來看屈雄，一個Redis節(jié)點包含多個database（非cluster模式下默認是16個撒踪，cluster模式下只能是1個）坯屿，而一個database維護了從key space到object space的映射關系。這個映射關系的key是string類型活合，而value可以是多種數(shù)據(jù)類型，比如：string, list, hash等。我們可以看到节值，key的類型固定是string锯梁，而value可能的類型是多個即碗。

而從Redis內部實現(xiàn)的角度來看，在前面第一篇文章中陌凳，我們已經(jīng)提到過剥懒，一個database內的這個映射關系是用一個dict來維護的。dict的key固定用一種數(shù)據(jù)結構來表達就夠了合敦，這就是動態(tài)字符串sds初橘。而value則比較復雜，為了在同一個dict內能夠存儲不同類型的value充岛，這就需要一個通用的數(shù)據(jù)結構保檐，這個通用的數(shù)據(jù)結構就是robj（全名是redisObject）。舉個例子：如果value是一個list崔梗，那么它的內部存儲結構是一個quicklist（quicklist的具體實現(xiàn)我們放在后面的文章討論）夜只；如果value是一個string，那么它的內部存儲結構一般情況下是一個sds蒜魄。當然實際情況更復雜一點扔亥，比如一個string類型的value场躯，如果它的值是一個數(shù)字，那么Redis內部還會把它轉成long型來存儲旅挤，從而減小內存使用踢关。而一個robj既能表示一個sds，也能表示一個quicklist粘茄，甚至還能表示一個long型签舞。

底層

dict-hash

dict是一個用于維護key和value映射關系的數(shù)據(jù)結構，與很多語言中的Map或dictionary類似柒瓣。Redis的一個database中所有key到value的映射儒搭，就是使用一個dict來維護的。不過嘹朗，這只是它在Redis中的一個用途而已师妙，它在Redis中被使用的地方還有很多。比如屹培，一個Redis hash結構默穴，當它的field較多時，便會采用dict來存儲褪秀。再比如蓄诽，Redis配合使用dict和skiplist來共同維護一個sorted set。這些細節(jié)我們后面再討論媒吗，在本文中仑氛，我們集中精力討論dict本身的實現(xiàn)。

sds-string

一個sds字符串的完整結構闸英，由在內存地址上前后相鄰的兩部分組成：

一個header锯岖。通常包含字符串的長度(len)、最大容量(alloc)和flags甫何。sdshdr5有所不同出吹。

一個字符數(shù)組。這個字符數(shù)組的長度等于最大容量+1辙喂。真正有效的字符串數(shù)據(jù)捶牢，其長度通常小于最大容量。在真正的字符串數(shù)據(jù)之后巍耗，是空余未用的字節(jié)（一般以字節(jié)0填充）秋麸，允許在不重新分配內存的前提下讓字符串數(shù)據(jù)向后做有限的擴展。在真正的字符串數(shù)據(jù)之后炬太，還有一個NULL結束符灸蟆，即ASCII碼為0的’\0’字符。這是為了和傳統(tǒng)C字符串兼容亲族。之所以字符數(shù)組的長度比最大容量多1個字節(jié)次乓，就是為了在字符串長度達到最大容量時仍然有1個字節(jié)存放NULL結束符吓歇。

ziplist

翻譯一下就是說：ziplist是一個經(jīng)過特殊編碼的雙向鏈表，它的設計目標就是為了提高存儲效率票腰。ziplist可以用于存儲字符串或整數(shù)，其中整數(shù)是按真正的二進制表示進行編碼的女气，而不是編碼成字符串序列杏慰。它能以O(1)的時間復雜度在表的兩端提供push和pop操作。

實際上炼鞠，ziplist充分體現(xiàn)了Redis對于存儲效率的追求缘滥。一個普通的雙向鏈表蘑志，鏈表中每一項都占用獨立的一塊內存风钻，各項之間用地址指針（或引用）連接起來。這種方式會帶來大量的內存碎片以舒，而且地址指針也會占用額外的內存霎肯。而ziplist卻是將表中每一項存放在前后連續(xù)的地址空間內擎颖，一個ziplist整體占用一大塊內存。它是一個表（list）观游，但其實不是一個鏈表（linked list）搂捧。

quicklist

它確實是一個雙向鏈表，而且是一個ziplist的雙向鏈表懂缕。

這是什么意思呢允跑？

我們知道，雙向鏈表是由多個節(jié)點（Node）組成的搪柑。這個描述的意思是：quicklist的每個節(jié)點都是一個ziplist聋丝。ziplist我們已經(jīng)在上一篇介紹過。

ziplist本身也是一個能維持數(shù)據(jù)項先后順序的列表（按插入位置）工碾，而且是一個內存緊縮的列表（各個數(shù)據(jù)項在內存上前后相鄰）弱睦。比如，一個包含3個節(jié)點的quicklist倚喂，如果每個節(jié)點的ziplist又包含4個數(shù)據(jù)項每篷，那么對外表現(xiàn)上，這個list就總共包含12個數(shù)據(jù)項端圈。

quicklist的結構為什么這樣設計呢焦读？總結起來，大概又是一個空間和時間的折中：

雙向鏈表便于在表的兩端進行push和pop操作舱权，但是它的內存開銷比較大矗晃。首先，它在每個節(jié)點上除了要保存數(shù)據(jù)之外宴倍，還要額外保存兩個指針张症；其次仓技，雙向鏈表的各個節(jié)點是單獨的內存塊，地址不連續(xù)俗他，節(jié)點多了容易產(chǎn)生內存碎片脖捻。

ziplist由于是一整塊連續(xù)內存，所以存儲效率很高兆衅。但是地沮，它不利于修改操作，每次數(shù)據(jù)變動都會引發(fā)一次內存的realloc羡亩。特別是當ziplist長度很長的時候摩疑，一次realloc可能會導致大批量的數(shù)據(jù)拷貝，進一步降低性能畏铆。

于是雷袋，結合了雙向鏈表和ziplist的優(yōu)點，quicklist就應運而生了辞居。

不過楷怒，這也帶來了一個新問題：到底一個quicklist節(jié)點包含多長的ziplist合適呢？比如速侈，同樣是存儲12個數(shù)據(jù)項率寡，既可以是一個quicklist包含3個節(jié)點，而每個節(jié)點的ziplist又包含4個數(shù)據(jù)項倚搬，也可以是一個quicklist包含6個節(jié)點冶共，而每個節(jié)點的ziplist又包含2個數(shù)據(jù)項。

skiplist

這種數(shù)據(jù)結構是由William Pugh發(fā)明的每界，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》捅僵。對細節(jié)感興趣的同學可以下載論文原文來閱讀。

skiplist眨层，顧名思義庙楚，首先它是一個list趴樱。實際上叁征，它是在有序鏈表的基礎上發(fā)展起來的捺疼。

我們先來看一個有序鏈表，如下圖（最左側的灰色節(jié)點表示一個空的頭結點）：

在這樣一個鏈表中呢袱，如果我們要查找某個數(shù)據(jù)羞福，那么需要從頭開始逐個進行比較坯临，直到找到包含數(shù)據(jù)的那個節(jié)點恋昼，或者找到第一個比給定數(shù)據(jù)大的節(jié)點為止（沒找到）液肌。也就是說嗦哆，時間復雜度為O(n)老速。同樣凸主，當我們要插入新數(shù)據(jù)的時候卿吐，也要經(jīng)歷同樣的查找過程，從而確定插入位置箭窜。

假如我們每相鄰兩個節(jié)點增加一個指針磺樱，讓指針指向下下個節(jié)點竹捉，如下圖：

這樣所有新增加的指針連成了一個新的鏈表活孩，但它包含的節(jié)點個數(shù)只有原來的一半（上圖中是7, 19, 26）⊙耍現(xiàn)在當我們想查找數(shù)據(jù)的時候起趾，可以先沿著這個新鏈表進行查找训裆。當碰到比待查數(shù)據(jù)大的節(jié)點時边琉，再回到原來的鏈表中進行查找。比如族扰，我們想查找23渔呵，查找的路徑是沿著下圖中標紅的指針所指向的方向進行的：

23首先和7比較，再和19比較爷辱，比它們都大，繼續(xù)向后比較巩检。

但23和26比較的時候兢哭，比26要小迟螺，因此回到下面的鏈表（原鏈表）矩父，與22比較排霉。

23比22要大，沿下面的指針繼續(xù)向后和26比較后裸。23比26小冒滩，說明待查數(shù)據(jù)23在原鏈表中不存在开睡，而且它的插入位置應該在22和26之間篇恒。

在這個查找過程中胁艰，由于新增加的指針蝗茁，我們不再需要與鏈表中每個節(jié)點逐個進行比較了哮翘。需要比較的節(jié)點數(shù)大概只有原來的一半饭寺。

利用同樣的方式艰匙，我們可以在上層新產(chǎn)生的鏈表上员凝，繼續(xù)為每相鄰的兩個節(jié)點增加一個指針健霹，從而產(chǎn)生第三層鏈表糖埋。如下圖：

在這個新的三層鏈表結構上，如果我們還是查找23祟敛，那么沿著最上層鏈表首先要比較的是19卒煞，發(fā)現(xiàn)23比19大叼架，接下來我們就知道只需要到19的后面去繼續(xù)查找乖订，從而一下子跳過了19前面的所有節(jié)點√鹞蓿可以想象岂丘，當鏈表足夠長的時候奥帘，這種多層鏈表的查找方式能讓我們跳過很多下層節(jié)點寨蹋，大大加快查找的速度已旧。

skiplist正是受這種多層鏈表的想法的啟發(fā)而設計出來的。實際上召娜，按照上面生成鏈表的方式运褪，上面每一層鏈表的節(jié)點個數(shù)，是下面一層的節(jié)點個數(shù)的一半萤晴，這樣查找過程就非常類似于一個二分查找吐句，使得查找的時間復雜度可以降低到O(log n)。但是店读，這種方法在插入數(shù)據(jù)的時候有很大的問題嗦枢。新插入一個節(jié)點之后，就會打亂上下相鄰兩層鏈表上節(jié)點個數(shù)嚴格的2:1的對應關系屯断。如果要維持這種對應關系文虏，就必須把新插入的節(jié)點后面的所有節(jié)點（也包括新插入的節(jié)點）重新進行調整侣诺，這會讓時間復雜度重新蛻化成O(n)丸相。刪除數(shù)據(jù)也有同樣的問題。

skiplist為了避免這一問題涕蜂，它不要求上下相鄰兩層鏈表之間的節(jié)點個數(shù)有嚴格的對應關系，而是為每個節(jié)點隨機出一個層數(shù)(level)印颤。比如，一個節(jié)點隨機出的層數(shù)是3，那么就把它鏈入到第1層到第3層這三層鏈表中顶吮。為了表達清楚，下圖展示了如何通過一步步的插入操作從而形成一個skiplist的過程：

從上面skiplist的創(chuàng)建和插入過程可以看出息罗，每一個節(jié)點的層數(shù)（level）是隨機出來的弊添，而且新插入一個節(jié)點不會影響其它節(jié)點的層數(shù)澈圈。因此，插入操作只需要修改插入節(jié)點前后的指針，而不需要對很多節(jié)點都進行調整。這就降低了插入操作的復雜度蜗顽。實際上崔挖，這是skiplist的一個很重要的特性，這讓它在插入性能上明顯優(yōu)于平衡樹的方案。這在后面我們還會提到逞频。

intset

encoding: 數(shù)據(jù)編碼歌亲，表示intset中的每個數(shù)據(jù)元素用幾個字節(jié)來存儲。它有三種可能的取值：INTSET_ENC_INT16表示每個元素用2個字節(jié)存儲扮休，INTSET_ENC_INT32表示每個元素用4個字節(jié)存儲，INTSET_ENC_INT64表示每個元素用8個字節(jié)存儲聘芜。因此瞎饲，intset中存儲的整數(shù)最多只能占用64bit嗅战。

length: 表示intset中的元素個數(shù)驮捍。encoding和length兩個字段構成了intset的頭部（header）珊泳。

contents: 是一個柔性數(shù)組（flexible array member），表示intset的header后面緊跟著數(shù)據(jù)元素录择。這個數(shù)組的總長度（即總字節(jié)數(shù)）等于encoding * length挨稿。柔性數(shù)組在Redis的很多數(shù)據(jù)結構的定義中都出現(xiàn)過（例如sds,quicklist,skiplist），用于表達一個偏移量京痢。contents需要單獨為其分配空間奶甘，這部分內存不包含在intset結構當中。

其中需要注意的是历造，intset可能會隨著數(shù)據(jù)的添加而改變它的數(shù)據(jù)編碼：

最開始甩十，新創(chuàng)建的intset使用占內存最小的INTSET_ENC_INT16（值為2）作為數(shù)據(jù)編碼。

每添加一個新元素吭产，則根據(jù)元素大小決定是否對數(shù)據(jù)編碼進行升級侣监。

下圖給出了一個添加數(shù)據(jù)的具體例子（點擊看大圖）。

在上圖中：

新創(chuàng)建的intset只有一個header臣淤，總共8個字節(jié)橄霉。其中encoding= 2,length= 0。

添加13, 5兩個元素之后邑蒋，因為它們是比較小的整數(shù)姓蜂，都能使用2個字節(jié)表示，所以encoding不變医吊，值還是2钱慢。

當添加32768的時候，它不再能用2個字節(jié)來表示了（2個字節(jié)能表達的數(shù)據(jù)范圍是-215~215-1卿堂，而32768等于215束莫，超出范圍了），因此encoding必須升級到INTSET_ENC_INT32（值為4）草描，即用4個字節(jié)表示一個元素览绿。

在添加每個元素的過程中，intset始終保持從小到大有序穗慕。

與ziplist類似饿敲，intset也是按小端（little endian）模式存儲的（參見維基百科詞條Endianness）。比如逛绵，在上圖中intset添加完所有數(shù)據(jù)之后怀各，表示encoding字段的4個字節(jié)應該解釋成0x00000004，而第5個數(shù)據(jù)應該解釋成0x000186A0 = 100000术浪。

intset與ziplist相比：

ziplist可以存儲任意二進制串瓢对，而intset只能存儲整數(shù)。

ziplist是無序的添吗，而intset是從小到大有序的。因此份名，在ziplist上查找只能遍歷碟联，而在intset上可以進行二分查找妓美，性能更高。

ziplist可以對每個數(shù)據(jù)項進行不同的變長編碼（每個數(shù)據(jù)項前面都有數(shù)據(jù)長度字段len）鲤孵，而intset只能整體使用一個統(tǒng)一的編碼（encoding）壶栋。