redis有五種基本數據結構：字符串、hash、set、zset、list。但是你知道構成這五種結構的底層數據結構是怎樣的嗎？ 今天我們來花費五分鐘的時間了解一下。 (目前redis版本為3.0.6)
動態字符串SDS
SDS是"simple dynamic string"的縮寫。 redis中所有場景中出現的字符串，基本都是由SDS來實現的
所有非數字的key。例如 setmsg"hello world" 中的key msg.字符串數據類型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"非字符串數據類型中的「字符串值」。例如 RPUSH fruits"apple""banana""cherry"中的"apple" "banana" "cherry"SDS長這樣：
free:還剩多少空間 len:字符串長度 buf:存放的字符數組
空間預分配
為減少修改字符串帶來的內存重分配次數，sds採用了「一次管夠」的策略：
若修改之後sds長度小於1MB,則多分配現有len長度的空間若修改之後sds長度大於等於1MB，則擴充除了滿足修改之後的長度外，額外多1MB空間
惰性空間釋放
為避免縮短字符串時候的內存重分配操作，sds在數據減少時，並不立刻釋放空間。
int
就是redis中存放的各種數字 包括一下這種，故意加引號「」的
雙向鍊表
長這樣：
分兩部分，一部分是「統籌部分」：橘黃色，一部分是「具體實施方「：藍色。
主體」統籌部分「：
head指向具體雙向鍊表的頭tail指向具體雙向鍊表的尾len雙向鍊表的長度具體"實施方"：一目了然的雙向鍊表結構，有前驅 pre有後繼 next
由 list和 listNode兩個數據結構構成。
ziplist
壓縮列表。 redis的列表鍵和哈希鍵的底層實現之一。此數據結構是為了節約內存而開發的。和各種語言的數組類似，它是由連續的內存塊組成的，這樣一來，由於內存是連續的，就減少了很多內存碎片和指針的內存佔用，進而節約了內存。
然後文中的 entry的結構是這樣的：
元素的遍歷
先找到列表尾部元素：
然後再根據ziplist節點元素中的 previous_entry_length屬性，來逐個遍歷:
連鎖更新
再次看看 entry元素的結構，有一個 previous_entry_length欄位，他的長度要麼都是1個字節，要麼都是5個字節：
前一節點的長度小於254位元組，則 previous_entry_length長度為1位元組前一節點的長度小於254位元組，則 previous_entry_length長度為5位元組假設現在存在一組壓縮列表，長度都在250位元組至253位元組之間，突然新增一新節點 new， 長度大於等於254位元組，會出現：
程序需要不斷的對壓縮列表進行空間重分配工作，直到結束。
除了增加操作，刪除操作也有可能帶來「連鎖更新」。 請看下圖，ziplist中所有entry節點的長度都在250位元組至253位元組之間，big節點長度大於254位元組，small節點小於254位元組。
哈希表
哈希表略微有點複雜。哈希表的製作方法一般有兩種，一種是： 開放尋址法，一種是 拉鏈法。redis的哈希表的製作使用的是 拉鏈法。
整體結構如下圖：
也是分為兩部分：左邊橘黃色部分和右邊藍色部分，同樣，也是」統籌「和」實施「的關係。 具體哈希表的實現，都是在藍色部分實現的。 先來看看藍色部分：
這也分為左右兩邊「統籌」和「實施」的兩部分。
右邊部分很容易理解：就是通常拉鍊表實現的哈希表的樣式；數組就是bucket，一般不同的key首先會定位到不同的bucket，若key重複，就用鍊表把衝突的key串起來。
新建key的過程：
假如重複了:
rehash
再來看看哈希表總體圖中左邊橘黃色的「統籌」部分，其中有兩個關鍵的屬性： ht和 rehashidx。 ht是一個數組，有且只有倆元素ht[0]和ht[1];其中，ht[0]存放的是redis中使用的哈希表，而ht[1]和rehashidx和哈希表的 rehash有關。
rehash指的是重新計算鍵的哈希值和索引值，然後將鍵值對重排的過程。
加載因子（load factor）=ht[0].used/ht[0].size。
擴容和收縮標準
擴容：
沒有執行BGSAVE和BGREWRITEAOF指令的情況下，哈希表的 加載因子大於等於1。正在執行BGSAVE和BGREWRITEAOF指令的情況下，哈希表的 加載因子大於等於5。收縮:
加載因子小於0.1時，程序自動開始對哈希表進行收縮操作。擴容和收縮的數量
擴容：
第一個大於等於 ht[0].used*2的 2^n(2的n次方冪)。收縮：
第一個大於等於 ht[0].used的 2^n(2的n次方冪)。(以下部分屬於細節分析，可以跳過直接看擴容步驟)
對於收縮，我當時陷入了疑慮：收縮標準是 加載因子小於0.1的時候，也就是說假如哈希表中有4個元素的話，哈希表的長度只要大於40，就會進行收縮，假如有一個長度大於40，但是存在的元素為4即( ht[0].used為4)的哈希表，進行收縮，那收縮後的值為多少？
我想了一下：按照前文所講的內容，應該是4。 但是，假如是4，存在和收縮後的長度相等，是不是又該擴容？ 翻開源碼看看：
收縮具體函數:
int dictResize(dict *d) { int minimal; //如果dict_can_resize被設置成0，表示不能進行rehash，或正在進行rehash，返回出錯標誌DICT_ERR if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; minimal = d->ht[0].used; //獲得已經有的節點數量作為最小限度minimal if (minimal < DICT_HT_INITIAL_SIZE)//但是minimal不能小於最低值DICT_HT_INITIAL_SIZE（4） minimal = DICT_HT_INITIAL_SIZE; return dictExpand(d, minimal); //用minimal調整字典d的大小} int dictExpand(dict *d, unsigned long size) { dictht n; unsigned long realsize = _dictNextPower(size); //獲得一個最接近2^n的realsize if (dictIsRehashing(d) || d->ht[0].used > size) //正在rehash或size不夠大返回出錯標誌 return DICT_ERR; if (realsize == d->ht[0].size) return DICT_ERR; //如果新的realsize和原本的size一樣則返回出錯標誌 /* Allocate the new hash table and initialize all pointers to NULL */ //初始化新的哈希表的成員 n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; /* Is this the first initialization? If so it's not really a rehashing * we just set the first hash table so that it can accept keys. */ if (d->ht[0].table == NULL) { //如果ht[0]哈希表為空，則將新的哈希表n設置為ht[0] d->ht[0] = n; return DICT_OK; } d->ht[1] = n; //如果ht[0]非空，則需要rehash d->rehashidx = 0; //設置rehash標誌位為0，開始漸進式rehash（incremental rehashing） return DICT_OK;} static unsigned long _dictNextPower(unsigned long size){ unsigned long i = DICT_HT_INITIAL_SIZE; //DICT_HT_INITIAL_SIZE 為 4 if (size >= LONG_MAX) return LONG_MAX + 1LU; while(1) { if (i >= size) return i; i *= 2; }}由代碼我們可以看到，假如收縮後長度為4，不僅不會收縮，甚至還會報錯。()
我們回過頭來再看看設定：題目可能成立嗎？ 哈希表的擴容都是2倍增長的，最小是4， 4 ===》 8 ====》 16 =====》 32 ======》 64 ====》 128
也就是說：不存在長度為 40多的情況，只能是64。但是如果是64的話，64 X 0.1（收縮界限）= 6.4 ，也就是說在減少到6的時候，哈希表就會收縮，會縮小到多少呢？是8。此時，再繼續減少到4，也不會再收縮了。所以，根本不存在一個長度大於40，但是存在的元素為4的哈希表的。
擴容步驟
收縮步驟
漸進式refresh
在"擴容步驟"和"收縮步驟" 兩幅動圖中每幅圖的第四步驟「將ht[0]中的數據利用哈希函數重新計算，rehash到ht[1]」，並不是一步完成的，而是分成N多步，循序漸進的完成的。 因為hash中有可能存放幾千萬甚至上億個key，畢竟Redis中每個hash中可以存 2^32-1 鍵值對（40多億），假如一次性將這些鍵值rehash的話，可能會導致伺服器在一段時間內停止服務，畢竟哈希函數就得計算一陣子呢((#^.^#))。
哈希表的refresh是分多次、漸進式進行的。
漸進式refresh和下圖中左邊橘黃色的「統籌」部分中的 rehashidx密切相關：
rehashidx 的數值就是現在rehash的元素位置rehashidx 等於 -1 的時候說明沒有在進行refresh
甚至在進行期間，每次對哈希表的增刪改查操作，除了正常執行之外，還會順帶將ht[0]哈希表相關鍵值對rehash到ht[1]。
以擴容步驟為例：
intset
整數集合是集合鍵的底層實現方式之一。
跳表
跳表這種數據結構長這樣：
redis中把跳表抽象成如下所示：
看這個圖，左邊「統籌」，右邊實現。 統籌部分有以下幾點說明：
header: 跳表表頭tail:跳表表尾level:層數最大的那個節點的層數length：跳表的長度實現部分有以下幾點說明：
表頭：是鍊表的哨兵節點，不記錄主體數據。是個雙向鍊表分值是有順序的o1、o2、o3是節點所保存的成員，是一個指針，可以指向一個SDS值。層級高度最高是32。沒每次創建一個新的節點的時候，程序都會隨機生成一個介於1和32之間的值作為level數組的大小，這個大小就是「高度」redis五種數據結構的實現
redis對象
redis中並沒有直接使用以上所說的各種數據結構來實現鍵值資料庫，而是基於一種對象，對象底層再間接的引用上文所說的具體的數據結構。
結構如下圖：
字符串
其中：embstr和raw都是由SDS動態字符串構成的。唯一區別是：raw是分配內存的時候，redisobject和 sds 各分配一塊內存，而embstr是redisobject和raw在一塊兒內存中。
列表
hash
set
zset