這篇文章延續(xù)精簡的風(fēng)格，爭(zhēng)取能讓大家8min內(nèi)讀完并有所收獲。

概述

一周前的文章精簡的介紹了Redis核心原理及Redis是如何工作的，這一章回歸到Redis的本質(zhì)上來（存儲(chǔ)）。Redis之所以如此受歡迎，一方面是性能強(qiáng)勁，另一方面就是支持多種常見的數(shù)據(jù)結(jié)構(gòu)，甚至能完成一定的數(shù)據(jù)運(yùn)算工作，靈活性大大提升。

Redis的常用四大數(shù)據(jù)結(jié)構(gòu)類型，將一一介紹

1）String

2）List

3）Hash

4）Set

Redis數(shù)據(jù)結(jié)構(gòu)

在文章Redis核心原理中介紹了，Redis字典的KV都是由redisObject組成的，每種Redis數(shù)據(jù)類型都是由不同的編碼方式和真實(shí)的底層數(shù)據(jù)類型（ptr）實(shí)現(xiàn)，本文先介紹底層數(shù)據(jù)實(shí)現(xiàn)

SDS

Redis string底層實(shí)現(xiàn)

struct sdshdr {????

????// 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量

????// 等于 SDS 所保存字符串的長度????

????int len;????

????// 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量????

????int free;????

????// 字節(jié)數(shù)組，用于保存字符串????

????char buf[];

};

1）獲取字符串長度的復(fù)雜度是O(1)

2）執(zhí)行append操作時(shí)，如果空間不足則自動(dòng)分配新空間，不會(huì)導(dǎo)致buf溢出

3）當(dāng)字符串長度小于1MB時(shí)，將分配與len相同大小的未使用空間（如圖所示），目的是在空間占用和空間重分配之間取得平衡

LINKEDLIST

Redis鏈表實(shí)現(xiàn)

1）list是雙向鏈表，RPUSH LPUSH由此實(shí)現(xiàn)

2）獲取鏈表長度為O(1)

HASH TABLE

Redis 哈希表實(shí)現(xiàn)

1）獲取hash表size/used的復(fù)雜度為O(1)

2）有兩張hash表組成，如果沒有rehash狀態(tài)下，rehashidx為-1，且其中的一張表是空的。當(dāng)rehash時(shí)，為了不影響redis的性能，同時(shí)使用兩張表漸進(jìn)式的完成rehash：設(shè)置rehashidx為0，當(dāng)查詢或修改key時(shí)把KV轉(zhuǎn)移到新表上去，直至舊表為空，設(shè)置rehashidx為-1，完成遷移

3）為什么hash table的長度是2的N次冪？因?yàn)閎ucket = hashcode & (len-1)，當(dāng)len為2的N次冪時(shí)len-1=1111。。? 因此原有的對(duì)象只有少部分會(huì)被重新分配到新的bucket中去，因?yàn)?len-1) -> （2*len-1）時(shí)只有最高位的0變成了1，會(huì)減少遷移的工作量，提高效率

INT SET

Redis的整數(shù)集合

1）獲取set length的復(fù)雜度為O(1)

2）encoding表明取值范圍及內(nèi)存占用，因此Redis并不適合將少量過大的數(shù)和大量小數(shù)值存在一起，會(huì)造成空間浪費(fèi)

ZIPLIST

Redis的壓縮表

1）ziplist是鏈表和哈希表的底層實(shí)現(xiàn)之一

2）ziplist采用更緊湊的編碼，減少內(nèi)存使用

以下是Redis的數(shù)據(jù)結(jié)構(gòu)全貌

String

Redis字符串對(duì)象

List

ziplist實(shí)現(xiàn)的List

linked list實(shí)現(xiàn)的List

1）當(dāng)列表中的object數(shù)量小于512個(gè)時(shí)，redis使用ziplist這種占用空間更小的結(jié)構(gòu)

Hash

ziplist實(shí)現(xiàn)的哈希對(duì)象

ziplist實(shí)現(xiàn)的哈希對(duì)象

hashtable實(shí)現(xiàn)的哈希對(duì)象

1）當(dāng)哈希表中的object數(shù)量小于512個(gè)時(shí)，Redis使用ziplist這種占用空間更小的結(jié)構(gòu)。雖然復(fù)雜度為O(N)，但由于object數(shù)量少，不會(huì)對(duì)CPU造成影響

Set

intset只包含數(shù)值類型的set

其它set

1）當(dāng)一個(gè)set中全是數(shù)字時(shí)，采用intset為底層，占用空間小，因?yàn)楸M量不要把少數(shù)string和大量int存儲(chǔ)在一個(gè)set里

總結(jié)

1）使用哈希表、列表及集合時(shí)，盡量不要使用big data及添加過多的數(shù)據(jù)，因?yàn)檫@樣會(huì)導(dǎo)致存儲(chǔ)結(jié)構(gòu)從ziplist變?yōu)閔ash table、linkedlist等空間占用更大的數(shù)據(jù)結(jié)構(gòu)

2）如無必要的情況下，一個(gè)集合中不要將string和int混合存儲(chǔ)，這會(huì)導(dǎo)致內(nèi)存占用變大

3）String不要過長，小于39字符時(shí)，使用embstr編碼格式，占用更少內(nèi)存

4）set可以用來做數(shù)據(jù)運(yùn)算，如交、并等大量數(shù)據(jù)的運(yùn)算

參考文檔

Redis設(shè)計(jì)與實(shí)現(xiàn)

Redis原理及應(yīng)用