Redis的幾種數(shù)據(jù)結(jié)構(gòu)：
1.SDS(動(dòng)態(tài)字符串)
SDS存儲(chǔ)String類型的數(shù)據(jù)，底層是一個(gè)char[]，同時(shí)會(huì)維護(hù)字符串的長度，和申請的內(nèi)存大小，動(dòng)態(tài)擴(kuò)容如下機(jī)制：
? ? 1. 如果擴(kuò)容后的新字符串小于1M，則申請新的內(nèi)存空間為擴(kuò)展后的字符串長度的兩倍+1；
? ? 2.如果新字符串大于1M，則申請的新空間為擴(kuò)展后字符串長度 + 1M +1。
2.IntSet
? InstSet底層是一個(gè)整數(shù)數(shù)組，同時(shí)會(huì)維護(hù)數(shù)組的編碼方式（類似short、int、long）和元素個(gè)數(shù)。同時(shí)數(shù)組中的整數(shù)是唯一的，升序的。如果新添加的數(shù)字超過了編碼方式的范圍，則會(huì)進(jìn)行擴(kuò)容，擴(kuò)容機(jī)制如下：
? ? 1.將編碼方式升級；
? ? 2.倒序一次將數(shù)組中的元素拷貝到擴(kuò)容后的正確位置;
? ? 3.將添加的元素放入數(shù)組末尾;
如果長度超了，則將數(shù)組復(fù)制到一個(gè)更大的數(shù)組里面。
3.Dict
Dict由三個(gè)部分組成，分別是：
字典：維護(hù)字典的類型， 兩個(gè)哈希表， reHash的進(jìn)度， reHash是否暫停；
哈希表：維護(hù)指向哈希節(jié)點(diǎn)數(shù)組的指針、哈希表大小、哈希表大小的掩碼、哈希節(jié)點(diǎn)的個(gè)數(shù)；
哈希節(jié)點(diǎn)：維護(hù)一個(gè)鍵值對和指向下一個(gè)節(jié)點(diǎn)的指針；
Ditc中的HashTable就是數(shù)組結(jié)合單向鏈表的實(shí)現(xiàn)，當(dāng)集合中元素較多時(shí)，會(huì)導(dǎo)致哈希沖突的增多，鏈表過長，查詢效率降低，所以Dict每次新增鍵值對時(shí)都會(huì)檢測負(fù)載因子，如果負(fù)載因子過大或時(shí)會(huì)進(jìn)行哈希表的擴(kuò)容，同時(shí)如果負(fù)載因子很小的話，會(huì)進(jìn)行哈希表的收縮。哈希表的擴(kuò)容和收縮機(jī)制如下：
1. 計(jì)算新的哈希表的大小，按照新的哈希表大小申請內(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的過程中，新增操作直接寫入新哈希表中，其他操作均需要查詢兩張表尋找數(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)的長度（用于遍歷）、節(jié)點(diǎn)編碼信息（數(shù)據(jù)類型：字符串還是整數(shù)，和數(shù)據(jù)長度）,節(jié)點(diǎn)數(shù)據(jù)。
5.QuickList
ZipList雖然節(jié)省內(nèi)存，但是申請內(nèi)存必須是連續(xù)的，如果內(nèi)存占用過多，申請內(nèi)存的效率會(huì)很低。為了解決這個(gè)問題，可以創(chuàng)建多個(gè)ZipList來分片儲(chǔ)存數(shù)據(jù)，然后使用QuickList來管理拆分后的數(shù)據(jù)。QuickListu是一個(gè)雙端鏈表，每一個(gè)節(jié)點(diǎn)都是一個(gè)ZipList。為了避免每個(gè)ZipList的長度過大，可以配置每一個(gè)ZipList的最大長度用來控制ZipList的大小。除了控制ZipList的大小，QuickList還可以對節(jié)點(diǎn)的ZipList做壓縮，因?yàn)殒湵矶际鞘孜苍L問較多，所以首尾不壓縮，中間的節(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)的跨度不同，層級越高，跨度越大。增刪改查效率與紅黑樹基本一致，但是實(shí)現(xiàn)簡單。
7.RedisObject ： Redis基類
Redis中的任意數(shù)據(jù)類型的鍵和值都會(huì)被封裝為一個(gè)RedisObject，源碼如下
Redis五種數(shù)據(jù)類型：
1.String：其基本編碼方式是RAW，基于簡單動(dòng)態(tài)字符串(SDS)實(shí)現(xiàn)，儲(chǔ)存上限為512Mb。
如果儲(chǔ)存的SDS長度小于44字節(jié)，則會(huì)采用EMBSTR編碼，此時(shí)object head與SDS是一段連續(xù)空間，申請內(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ù)量不超過配置值，會(huì)采用IntSet編碼，以節(jié)省內(nèi)存。
4.ZSet：是一個(gè)SortedSet，其中每一個(gè)元素都需要指定一個(gè)score值和member值。一般由SkipList組合Dict實(shí)現(xiàn)。如果元素?cái)?shù)量不多時(shí)，會(huì)采用ZipList來實(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)。
