Redis的幾種數(shù)據(jù)結(jié)構(gòu)：

1.SDS(動(dòng)態(tài)字符串)

SDS存儲(chǔ)String類(lèi)型的數(shù)據(jù)末荐，底層是一個(gè)char[]明肮，同時(shí)會(huì)維護(hù)字符串的長(zhǎng)度，和申請(qǐng)的內(nèi)存大小君编，動(dòng)態(tài)擴(kuò)容如下機(jī)制：

? ? 1. 如果擴(kuò)容后的新字符串小于1M鹏秋，則申請(qǐng)新的內(nèi)存空間為擴(kuò)展后的字符串長(zhǎng)度的兩倍+1尊蚁；

? ? 2.如果新字符串大于1M，則申請(qǐng)的新空間為擴(kuò)展后字符串長(zhǎng)度 + 1M +1拼岳。

2.IntSet

? InstSet底層是一個(gè)整數(shù)數(shù)組枝誊，同時(shí)會(huì)維護(hù)數(shù)組的編碼方式（類(lèi)似short况芒、int惜纸、long）和元素個(gè)數(shù)。同時(shí)數(shù)組中的整數(shù)是唯一的绝骚，升序的耐版。如果新添加的數(shù)字超過(guò)了編碼方式的范圍，則會(huì)進(jìn)行擴(kuò)容压汪，擴(kuò)容機(jī)制如下：

? ? 1.將編碼方式升級(jí)粪牲；

? ? 2.倒序一次將數(shù)組中的元素拷貝到擴(kuò)容后的正確位置;

? ? 3.將添加的元素放入數(shù)組末尾;

如果長(zhǎng)度超了，則將數(shù)組復(fù)制到一個(gè)更大的數(shù)組里面止剖。

3.Dict

Dict由三個(gè)部分組成腺阳，分別是：

字典：維護(hù)字典的類(lèi)型， 兩個(gè)哈希表穿香， reHash的進(jìn)度亭引， reHash是否暫停；

哈希表：維護(hù)指向哈希節(jié)點(diǎn)數(shù)組的指針皮获、哈希表大小焙蚓、哈希表大小的掩碼、哈希節(jié)點(diǎn)的個(gè)數(shù)；

哈希節(jié)點(diǎn)：維護(hù)一個(gè)鍵值對(duì)和指向下一個(gè)節(jié)點(diǎn)的指針购公；

Ditc中的HashTable就是數(shù)組結(jié)合單向鏈表的實(shí)現(xiàn)萌京，當(dāng)集合中元素較多時(shí)，會(huì)導(dǎo)致哈希沖突的增多宏浩，鏈表過(guò)長(zhǎng)知残，查詢效率降低，所以Dict每次新增鍵值對(duì)時(shí)都會(huì)檢測(cè)負(fù)載因子绘闷，如果負(fù)載因子過(guò)大或時(shí)會(huì)進(jìn)行哈希表的擴(kuò)容橡庞，同時(shí)如果負(fù)載因子很小的話，會(huì)進(jìn)行哈希表的收縮印蔗。哈希表的擴(kuò)容和收縮機(jī)制如下：

1. 計(jì)算新的哈希表的大小扒最，按照新的哈希表大小申請(qǐng)內(nèi)存空間，用于創(chuàng)建哈希表华嘹，并賦值給字典中的兩個(gè)哈希表中的空哈希表吧趣。

2. 將字典中的reHash進(jìn)度和reHash是否暫停字段更新。

3.將數(shù)據(jù)漸進(jìn)式的遷移至新的哈希表中耙厚，每次執(zhí)行新增强挫、查詢、修改薛躬、刪除操作時(shí)俯渤，都將reHash的進(jìn)度上的數(shù)據(jù)遷移至新哈希表中，然后將reHash進(jìn)度++型宝，直到所有數(shù)據(jù)遷移完畢八匠。在reHash的過(guò)程中，新增操作直接寫(xiě)入新哈希表中趴酣，其他操作均需要查詢兩張表尋找數(shù)據(jù)梨树。

4.會(huì)將新的哈希表重新賦值給舊的空哈希表，然后釋放新哈希表的內(nèi)存空間岖寞。

4.ZipList

ZipList是一個(gè)特殊的雙端列表抡四，由一系列特殊編碼的連續(xù)內(nèi)存塊組成，可以在任意一端進(jìn)行壓入/彈出操作仗谆。其內(nèi)部維護(hù)ziplist的總字節(jié)數(shù)指巡、尾偏移量、節(jié)點(diǎn)數(shù)量（最大65535個(gè)）隶垮、各節(jié)點(diǎn)藻雪、尾標(biāo)識(shí)（0fff）。其中岁疼，每一個(gè)節(jié)點(diǎn)中包含前一個(gè)節(jié)點(diǎn)的長(zhǎng)度（用于遍歷）阔涉、節(jié)點(diǎn)編碼信息（數(shù)據(jù)類(lèi)型：字符串還是整數(shù)缆娃，和數(shù)據(jù)長(zhǎng)度）,節(jié)點(diǎn)數(shù)據(jù)。

5.QuickList

ZipList雖然節(jié)省內(nèi)存瑰排，但是申請(qǐng)內(nèi)存必須是連續(xù)的贯要，如果內(nèi)存占用過(guò)多，申請(qǐng)內(nèi)存的效率會(huì)很低椭住。為了解決這個(gè)問(wèn)題崇渗，可以創(chuàng)建多個(gè)ZipList來(lái)分片儲(chǔ)存數(shù)據(jù)，然后使用QuickList來(lái)管理拆分后的數(shù)據(jù)京郑。QuickListu是一個(gè)雙端鏈表宅广，每一個(gè)節(jié)點(diǎn)都是一個(gè)ZipList。為了避免每個(gè)ZipList的長(zhǎng)度過(guò)大些举，可以配置每一個(gè)ZipList的最大長(zhǎng)度用來(lái)控制ZipList的大小跟狱。除了控制ZipList的大小，QuickList還可以對(duì)節(jié)點(diǎn)的ZipList做壓縮户魏，因?yàn)殒湵矶际鞘孜苍L問(wèn)較多驶臊，所以首尾不壓縮，中間的節(jié)點(diǎn)壓縮叼丑，進(jìn)一步節(jié)省了內(nèi)存关翎。

6.SkipList

SkipList是一個(gè)的雙向鏈表，每個(gè)節(jié)點(diǎn)都包含了score和數(shù)據(jù)鸠信，節(jié)點(diǎn)按照score值排序纵寝，score一樣則按照數(shù)據(jù)值字典排序，每個(gè)節(jié)點(diǎn)都可以包含多層指針星立，層數(shù)是1到32之間的隨機(jī)數(shù)爽茴，不同層指針到下一個(gè)節(jié)點(diǎn)的跨度不同，層級(jí)越高贞铣，跨度越大闹啦。增刪改查效率與紅黑樹(shù)基本一致沮明，但是實(shí)現(xiàn)簡(jiǎn)單辕坝。

7.RedisObject ： Redis基類(lèi)

Redis中的任意數(shù)據(jù)類(lèi)型的鍵和值都會(huì)被封裝為一個(gè)RedisObject，源碼如下

Redis五種數(shù)據(jù)類(lèi)型：

1.String：其基本編碼方式是RAW荐健，基于簡(jiǎn)單動(dòng)態(tài)字符串(SDS)實(shí)現(xiàn)酱畅，儲(chǔ)存上限為512Mb。

如果儲(chǔ)存的SDS長(zhǎng)度小于44字節(jié)江场，則會(huì)采用EMBSTR編碼纺酸，此時(shí)object head與SDS是一段連續(xù)空間，申請(qǐng)內(nèi)存時(shí)只需要調(diào)用一次內(nèi)存分配函數(shù)址否，效率更高餐蔬。如果儲(chǔ)存的字符串是整數(shù)值碎紊，并且大小在LONG_MAX范圍內(nèi)，則會(huì)采用INT編碼樊诺，直接將數(shù)據(jù)保存在RedisObject的ptr指針位置（剛好8字節(jié)）仗考。

2.List：使用QuickList實(shí)現(xiàn)。

3.Set：其集合中元素都是唯一的词爬，可以判斷元素是否存在秃嗜。一般使用HT編碼，由Dict實(shí)現(xiàn)顿膨，key儲(chǔ)存數(shù)據(jù)锅锨，value為null。當(dāng)儲(chǔ)存的數(shù)據(jù)都是整數(shù)時(shí)恋沃，且數(shù)量不超過(guò)配置值必搞，會(huì)采用IntSet編碼，以節(jié)省內(nèi)存囊咏。

4.ZSet：是一個(gè)SortedSet顾画，其中每一個(gè)元素都需要指定一個(gè)score值和member值。一般由SkipList組合Dict實(shí)現(xiàn)匆笤。如果元素?cái)?shù)量不多時(shí)研侣，會(huì)采用ZipList來(lái)實(shí)現(xiàn)。

5.Hash：默認(rèn)由ZipList實(shí)現(xiàn)炮捧，相鄰的兩個(gè)節(jié)點(diǎn)前一個(gè)儲(chǔ)存field庶诡，后一個(gè)儲(chǔ)存value。如果數(shù)據(jù)量較大時(shí)咆课，Hash結(jié)果會(huì)轉(zhuǎn)為HT編碼末誓，使用Dict實(shí)現(xiàn)。