1. Redis數(shù)據(jù)結(jié)構(gòu)-動(dòng)態(tài)字符串

Redis中保存的Key是字符串，value是字符串或者字符串的集合。可見字符串是Redis中最常用的一種數(shù)據(jù)結(jié)構(gòu)。

Redis沒有直接使用C語言中的字符串，因?yàn)镃語言字符串存在很多問題：

• 獲取字符串長(zhǎng)度的需要通過運(yùn)算
• 非二進(jìn)制安全
• 不可修改Redis構(gòu)建了一種新的字符串結(jié)構(gòu)，稱為簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String），簡(jiǎn)稱SDS。例如，我們執(zhí)行命令：

圖片

那么Redis將在底層創(chuàng)建兩個(gè)SDS，其中一個(gè)是包含“name”的SDS，另一個(gè)是包含“虎哥”的SDS。

Redis是C語言實(shí)現(xiàn)的，其中SDS是一個(gè)結(jié)構(gòu)體，源碼如下：

圖片

例如，一個(gè)包含字符串“name”的sds結(jié)構(gòu)如下：

圖片

SDS之所以叫做動(dòng)態(tài)字符串，是因?yàn)樗邆鋭?dòng)態(tài)擴(kuò)容的能力，例如一個(gè)內(nèi)容為“hi”的SDS：

圖片

假如我們要給SDS追加一段字符串“,Amy”，這里首先會(huì)申請(qǐng)新內(nèi)存空間：

• 如果新字符串小于1M，則新空間為擴(kuò)展后字符串長(zhǎng)度的兩倍+1；
• 如果新字符串大于1M，則新空間為擴(kuò)展后字符串長(zhǎng)度+1M+1。稱為內(nèi)存預(yù)分配。

圖片

2. Redis數(shù)據(jù)結(jié)構(gòu)-intset

IntSet是Redis中set集合的一種實(shí)現(xiàn)方式，基于整數(shù)數(shù)組來實(shí)現(xiàn)，并且具備長(zhǎng)度可變、有序等特征。結(jié)構(gòu)如下：

圖片

其中的encoding包含三種模式，表示存儲(chǔ)的整數(shù)大小不同：

圖片

為了方便查找，Redis會(huì)將intset中所有的整數(shù)按照升序依次保存在contents數(shù)組中，結(jié)構(gòu)如圖：

圖片

現(xiàn)在，數(shù)組中每個(gè)數(shù)字都在int16_t的范圍內(nèi)，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節(jié)大小為：encoding：4字節(jié) length：4字節(jié) contents：2字節(jié) * 3  = 6字節(jié)

圖片

我們向該其中添加一個(gè)數(shù)字：50000，這個(gè)數(shù)字超出了int16_t的范圍，intset會(huì)自動(dòng)升級(jí)編碼方式到合適的大小。以當(dāng)前案例來說流程如下：

• 升級(jí)編碼為INTSET_ENC_INT32, 每個(gè)整數(shù)占4字節(jié)，并按照新的編碼方式及元素個(gè)數(shù)擴(kuò)容數(shù)組
• 倒序依次將數(shù)組中的元素拷貝到擴(kuò)容后的正確位置
• 將待添加的元素放入數(shù)組末尾
• 最后，將inset的encoding屬性改為INTSET_ENC_INT32，將length屬性改為4

圖片

源碼如下：

圖片

圖片

小總結(jié)：

Intset可以看做是特殊的整數(shù)數(shù)組，具備一些特點(diǎn)：

• Redis會(huì)確保Intset中的元素唯一、有序
• 具備類型升級(jí)機(jī)制，可以節(jié)省內(nèi)存空間
• 底層采用二分查找方式來查詢

1.3. Redis數(shù)據(jù)結(jié)構(gòu)-Dict

我們知道Redis是一個(gè)鍵值型（Key-Value Pair）的數(shù)據(jù)庫，我們可以根據(jù)鍵實(shí)現(xiàn)快速的增刪改查。而鍵與值的映射關(guān)系正是通過Dict來實(shí)現(xiàn)的

Dict由三部分組成:

• 哈希表（DictHashTable）
• 哈希節(jié)點(diǎn)（DictEntry）
• 字典（Dict）

圖片

當(dāng)我們向Dict添加鍵值對(duì)時(shí)，Redis首先根據(jù)key計(jì)算出hash值（h），然后利用 h & sizemask來計(jì)算元素應(yīng)該存儲(chǔ)到數(shù)組中的哪個(gè)索引位置。我們存儲(chǔ)k1=v1，假設(shè)k1的哈希值h =1，則1&3 =1，因此k1=v1要存儲(chǔ)到數(shù)組角標(biāo)1位置。

圖片

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節(jié)點(diǎn)（DictEntry）、字典（Dict）

圖片

圖片

Dict的擴(kuò)容

Dict中的HashTable就是數(shù)組結(jié)合單向鏈表的實(shí)現(xiàn)，當(dāng)集合中元素較多時(shí)，必然導(dǎo)致哈希沖突增多，鏈表過長(zhǎng)，則查詢效率會(huì)大大降低。Dict在每次新增鍵值對(duì)時(shí)都會(huì)檢查負(fù)載因子（LoadFactor = used/size） ，滿足以下兩種情況時(shí)會(huì)觸發(fā)哈希表擴(kuò)容：

• 哈希表的 LoadFactor >= 1，并且服務(wù)器沒有執(zhí)行 BGSAVE 或者 BGREWRITEAOF 等后臺(tái)進(jìn)程；
• 哈希表的 LoadFactor > 5 ；

圖片

Dict的rehash

不管是擴(kuò)容還是收縮，必定會(huì)創(chuàng)建新的哈希表，導(dǎo)致哈希表的size和sizemask變化，而key的查詢與sizemask有關(guān)。因此必須對(duì)哈希表中的每一個(gè)key重新計(jì)算索引，插入新的哈希表，這個(gè)過程稱為rehash。過程是這樣的：

• 計(jì)算新hash表的realeSize，值取決于當(dāng)前要做的是擴(kuò)容還是收縮：

• 如果是擴(kuò)容，則新size為第一個(gè)大于等于dict.ht[0].used + 1的2^n
• 如果是收縮，則新size為第一個(gè)大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申請(qǐng)內(nèi)存空間，創(chuàng)建dictht，并賦值給dict.ht[1]
• 設(shè)置dict.rehashidx = 0，標(biāo)示開始rehash
• 將dict.ht[0]中的每一個(gè)dictEntry都rehash到dict.ht[1]
• 將dict.ht[1]賦值給dict.ht[0]，給dict.ht[1]初始化為空哈希表，釋放原來的dict.ht[0]的內(nèi)存
• 將rehashidx賦值為-1，代表rehash結(jié)束
• 在rehash過程中，新增操作，則直接寫入ht[1]，查詢、修改和刪除則會(huì)在dict.ht[0]和dict.ht[1]依次查找并執(zhí)行。這樣可以確保ht[0]的數(shù)據(jù)只減不增，隨著rehash最終為空

整個(gè)過程可以描述成：

圖片

小總結(jié)：

Dict的結(jié)構(gòu)：

• 類似java的HashTable，底層是數(shù)組加鏈表來解決哈希沖突
• Dict包含兩個(gè)哈希表，ht[0]平常用，ht[1]用來rehash

Dict的伸縮：

• 當(dāng)LoadFactor大于5或者LoadFactor大于1并且沒有子進(jìn)程任務(wù)時(shí)，Dict擴(kuò)容
• 當(dāng)LoadFactor小于0.1時(shí)，Dict收縮
• 擴(kuò)容大小為第一個(gè)大于等于used + 1的2^n
• 收縮大小為第一個(gè)大于等于used 的2^n
• Dict采用漸進(jìn)式rehash，每次訪問Dict時(shí)執(zhí)行一次rehash
• rehash時(shí)ht[0]只減不增，新增操作只在ht[1]執(zhí)行，其它操作在兩個(gè)哈希表

4. Redis數(shù)據(jù)結(jié)構(gòu)-ZipList

ZipList 是一種特殊的“雙端鏈表” ，由一系列特殊編碼的連續(xù)內(nèi)存塊組成。可以在任意一端進(jìn)行壓入/彈出操作, 并且該操作的時(shí)間復(fù)雜度為 O(1)。

圖片

圖片

ZipListEntry

ZipList 中的Entry并不像普通鏈表那樣記錄前后節(jié)點(diǎn)的指針，因?yàn)橛涗泝蓚€(gè)指針要占用16個(gè)字節(jié)，浪費(fèi)內(nèi)存。而是采用了下面的結(jié)構(gòu)：

圖片

• previous_entry_length：前一節(jié)點(diǎn)的長(zhǎng)度，占1個(gè)或5個(gè)字節(jié)。

• 如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，則采用1個(gè)字節(jié)來保存這個(gè)長(zhǎng)度值
• 如果前一節(jié)點(diǎn)的長(zhǎng)度大于254字節(jié)，則采用5個(gè)字節(jié)來保存這個(gè)長(zhǎng)度值，第一個(gè)字節(jié)為0xfe，后四個(gè)字節(jié)才是真實(shí)長(zhǎng)度數(shù)據(jù)

• encoding：編碼屬性，記錄content的數(shù)據(jù)類型（字符串還是整數(shù)）以及長(zhǎng)度，占用1個(gè)、2個(gè)或5個(gè)字節(jié)
• contents：負(fù)責(zé)保存節(jié)點(diǎn)的數(shù)據(jù)，可以是字符串或整數(shù)

ZipList中所有存儲(chǔ)長(zhǎng)度的數(shù)值均采用小端字節(jié)序，即低位字節(jié)在前，高位字節(jié)在后。例如：數(shù)值0x1234，采用小端字節(jié)序后實(shí)際存儲(chǔ)值為：0x3412

Encoding編碼

ZipListEntry中的encoding編碼分為字符串和整數(shù)兩種：字符串：如果encoding是以“00”、“01”或者“10”開頭，則證明content是字符串

例如，我們要保存字符串：“ab”和 “bc”

圖片

ZipListEntry中的encoding編碼分為字符串和整數(shù)兩種：

• 整數(shù)：如果encoding是以“11”開始，則證明content是整數(shù)，且encoding固定只占用1個(gè)字節(jié)

圖片

圖片

5. Redis數(shù)據(jù)結(jié)構(gòu)-ZipList的連鎖更新問題

ZipList的每個(gè)Entry都包含previous_entry_length來記錄上一個(gè)節(jié)點(diǎn)的大小，長(zhǎng)度是1個(gè)或5個(gè)字節(jié)：如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，則采用1個(gè)字節(jié)來保存這個(gè)長(zhǎng)度值 如果前一節(jié)點(diǎn)的長(zhǎng)度大于等于254字節(jié)，則采用5個(gè)字節(jié)來保存這個(gè)長(zhǎng)度值，第一個(gè)字節(jié)為0xfe，后四個(gè)字節(jié)才是真實(shí)長(zhǎng)度數(shù)據(jù) 現(xiàn)在，假設(shè)我們有N個(gè)連續(xù)的、長(zhǎng)度為250~253字節(jié)之間的entry，因此entry的previous_entry_length屬性用1個(gè)字節(jié)即可表示，如圖所示：

圖片

ZipList這種特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導(dǎo)致連鎖更新的發(fā)生。

小總結(jié)：

ZipList特性：

• 壓縮列表的可以看做一種連續(xù)內(nèi)存空間的"雙向鏈表"
• 列表的節(jié)點(diǎn)之間不是通過指針連接，而是記錄上一節(jié)點(diǎn)和本節(jié)點(diǎn)長(zhǎng)度來尋址，內(nèi)存占用較低
• 如果列表數(shù)據(jù)過多，導(dǎo)致鏈表過長(zhǎng)，可能影響查詢性能
• 增或刪較大數(shù)據(jù)時(shí)有可能發(fā)生連續(xù)更新問題

6. Redis數(shù)據(jù)結(jié)構(gòu)-QuickList

問題1：ZipList雖然節(jié)省內(nèi)存，但申請(qǐng)內(nèi)存必須是連續(xù)空間，如果內(nèi)存占用較多，申請(qǐng)內(nèi)存效率很低。怎么辦？

答：為了緩解這個(gè)問題，我們必須限制ZipList的長(zhǎng)度和entry大小。

問題2：但是我們要存儲(chǔ)大量數(shù)據(jù)，超出了ZipList最佳的上限該怎么辦？

答：我們可以創(chuàng)建多個(gè)ZipList來分片存儲(chǔ)數(shù)據(jù)。

問題3：數(shù)據(jù)拆分后比較分散，不方便管理和查找，這多個(gè)ZipList如何建立聯(lián)系？

答：Redis在3.2版本引入了新的數(shù)據(jù)結(jié)構(gòu)QuickList，它是一個(gè)雙端鏈表，只不過鏈表中的每個(gè)節(jié)點(diǎn)都是一個(gè)ZipList。

圖片

為了避免QuickList中的每個(gè)ZipList中entry過多，Redis提供了一個(gè)配置項(xiàng)：list-max-ziplist-size來限制。如果值為正，則代表ZipList的允許的entry個(gè)數(shù)的最大值 如果值為負(fù)，則代表ZipList的最大內(nèi)存大小，分5種情況：

• -1：每個(gè)ZipList的內(nèi)存占用不能超過4kb
• -2：每個(gè)ZipList的內(nèi)存占用不能超過8kb
• -3：每個(gè)ZipList的內(nèi)存占用不能超過16kb
• -4：每個(gè)ZipList的內(nèi)存占用不能超過32kb
• -5：每個(gè)ZipList的內(nèi)存占用不能超過64kb

其默認(rèn)值為 -2：

圖片

以下是QuickList的和QuickListNode的結(jié)構(gòu)源碼：

圖片

我們接下來用一段流程圖來描述當(dāng)前的這個(gè)結(jié)構(gòu)

圖片

總結(jié)：

QuickList的特點(diǎn)：

• 是一個(gè)節(jié)點(diǎn)為ZipList的雙端鏈表
• 節(jié)點(diǎn)采用ZipList，解決了傳統(tǒng)鏈表的內(nèi)存占用問題
• 控制了ZipList大小，解決連續(xù)內(nèi)存空間申請(qǐng)效率問題
• 中間節(jié)點(diǎn)可以壓縮，進(jìn)一步節(jié)省了內(nèi)存

7. Redis數(shù)據(jù)結(jié)構(gòu)-SkipList

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：

• 元素按照升序排列存儲(chǔ)
• 節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

圖片

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：元素按照升序排列存儲(chǔ) 節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

圖片

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：元素按照升序排列存儲(chǔ) 節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

圖片

小總結(jié)：

SkipList的特點(diǎn)：

• 跳躍表是一個(gè)雙向鏈表，每個(gè)節(jié)點(diǎn)都包含score和ele值
• 節(jié)點(diǎn)按照score值排序，score值一樣則按照ele字典排序
• 每個(gè)節(jié)點(diǎn)都可以包含多層指針，層數(shù)是1到32之間的隨機(jī)數(shù)
• 不同層指針到下一個(gè)節(jié)點(diǎn)的跨度不同，層級(jí)越高，跨度越大
• 增刪改查效率與紅黑樹基本一致，實(shí)現(xiàn)卻更簡(jiǎn)單

8. Redis數(shù)據(jù)結(jié)構(gòu)-RedisObject

Redis中的任意數(shù)據(jù)類型的鍵和值都會(huì)被封裝為一個(gè)RedisObject，也叫做Redis對(duì)象，源碼如下：

1、什么是redisObject：從Redis的使用者的角度來看，?個(gè)Redis節(jié)點(diǎn)包含多個(gè)database（非cluster模式下默認(rèn)是16個(gè)，cluster模式下只能是1個(gè)），而一個(gè)database維護(hù)了從key space到object space的映射關(guān)系。這個(gè)映射關(guān)系的key是string類型，?value可以是多種數(shù)據(jù)類型，比如：string, list, hash、set、sorted set等。我們可以看到，key的類型固定是string，而value可能的類型是多個(gè)。?從Redis內(nèi)部實(shí)現(xiàn)的?度來看，database內(nèi)的這個(gè)映射關(guān)系是用?個(gè)dict來維護(hù)的。dict的key固定用?種數(shù)據(jù)結(jié)構(gòu)來表達(dá)就夠了，這就是動(dòng)態(tài)字符串sds。而value則比較復(fù)雜，為了在同?個(gè)dict內(nèi)能夠存儲(chǔ)不同類型的value，這就需要?個(gè)通?的數(shù)據(jù)結(jié)構(gòu)，這個(gè)通用的數(shù)據(jù)結(jié)構(gòu)就是robj，全名是redisObject。

圖片

Redis的編碼方式

Redis中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類型不同，選擇不同的編碼方式，共包含11種不同類型：

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

Redis中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類型不同，選擇不同的編碼方式。每種數(shù)據(jù)類型的使用的編碼方式如下：

9. Redis數(shù)據(jù)結(jié)構(gòu)-String

String是Redis中最常見的數(shù)據(jù)存儲(chǔ)類型：

其基本編碼方式是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ù)，效率更高。

• 底層實(shí)現(xiàn)?式：動(dòng)態(tài)字符串sds 或者 long

String的內(nèi)部存儲(chǔ)結(jié)構(gòu)?般是sds（Simple Dynamic String，可以動(dòng)態(tài)擴(kuò)展內(nèi)存），但是如果?個(gè)String類型的value的值是數(shù)字，那么Redis內(nèi)部會(huì)把它轉(zhuǎn)成long類型來存儲(chǔ)，從?減少內(nèi)存的使用。

圖片

如果存儲(chǔ)的字符串是整數(shù)值，并且大小在LONG_MAX范圍內(nèi)，則會(huì)采用INT編碼：直接將數(shù)據(jù)保存在RedisObject的ptr指針位置（剛好8字節(jié)），不再需要SDS了

圖片

圖片

圖片

確切地說，String在Redis中是??個(gè)robj來表示

用來表示String的robj可能編碼成3種內(nèi)部表?：

• OBJ_ENCODING_RAW
• OBJ_ENCODING_EMBSTR
• OBJ_ENCODING_INT

其中前兩種編碼使?的是sds來存儲(chǔ)，最后?種OBJ_ENCODING_INT編碼直接把string存成了long型。在對(duì)string進(jìn)行incr, decr等操作的時(shí)候，如果它內(nèi)部是OBJ_ENCODING_INT編碼，那么可以直接行加減操作；如果它內(nèi)部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼，那么Redis會(huì)先試圖把sds存儲(chǔ)的字符串轉(zhuǎn)成long型，如果能轉(zhuǎn)成功，再進(jìn)行加減操作。對(duì)?個(gè)內(nèi)部表示成long型的string執(zhí)行append, setbit, getrange這些命令，針對(duì)的仍然是string的值（即?進(jìn)制表示的字符串），而不是針對(duì)內(nèi)部表?的long型進(jìn)?操作。比如字符串”32”，如果按照字符數(shù)組來解釋，它包含兩個(gè)字符，它們的ASCII碼分別是0x33和0x32。當(dāng)我們執(zhí)行命令setbit key 7 0的時(shí)候，相當(dāng)于把字符0x33變成了0x32，這樣字符串的值就變成了”22”。?如果將字符串”32”按照內(nèi)部的64位long型來解釋，那么它是0x0000000000000020，在這個(gè)基礎(chǔ)上執(zhí)?setbit位操作，結(jié)果就完全不對(duì)了。因此，在這些命令的實(shí)現(xiàn)中，會(huì)把long型先轉(zhuǎn)成字符串再進(jìn)行相應(yīng)的操作。

10. Redis數(shù)據(jù)結(jié)構(gòu)-List

Redis的List類型可以從首、尾操作列表中的元素：

圖片

哪一個(gè)數(shù)據(jù)結(jié)構(gòu)能滿足上述特征？

• LinkedList ：普通鏈表，可以從雙端訪問，內(nèi)存占用較高，內(nèi)存碎片較多
• ZipList ：壓縮列表，可以從雙端訪問，內(nèi)存占用低，存儲(chǔ)上限低
• QuickList：LinkedList + ZipList，可以從雙端訪問，內(nèi)存占用較低，包含多個(gè)ZipList，存儲(chǔ)上限高

Redis的List結(jié)構(gòu)類似一個(gè)雙端鏈表，可以從首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList來實(shí)現(xiàn)List，當(dāng)元素?cái)?shù)量小于512并且元素大小小于64字節(jié)時(shí)采用ZipList編碼，超過則采用LinkedList編碼。

在3.2版本之后，Redis統(tǒng)一采用QuickList來實(shí)現(xiàn)List：

圖片

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

Set是Redis中的單列集合，滿足下列特點(diǎn)：

• 不保證有序性
• 保證元素唯一
• 求交集、并集、差集

圖片

可以看出，Set對(duì)查詢?cè)氐男室蠓浅８?/p>

思考一下，什么樣的數(shù)據(jù)結(jié)構(gòu)可以滿足？

HashTable，也就是Redis中的Dict，不過Dict是雙列集合（可以存鍵、值對(duì)）

Set是Redis中的集合，不一定確保元素有序，可以滿足元素唯一、查詢效率要求極高。為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來存儲(chǔ)元素，value統(tǒng)一為null。當(dāng)存儲(chǔ)的所有數(shù)據(jù)都是整數(shù)，并且元素?cái)?shù)量不超過set-max-intset-entries時(shí)，Set會(huì)采用IntSet編碼，以節(jié)省內(nèi)存

圖片

結(jié)構(gòu)如下：

圖片

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

ZSet也就是SortedSet，其中每一個(gè)元素都需要指定一個(gè)score值和member值：

• 可以根據(jù)score值排序后
• member必須唯一
• 可以根據(jù)member查詢分?jǐn)?shù)

圖片

因此，zset底層數(shù)據(jù)結(jié)構(gòu)必須滿足鍵值存儲(chǔ)、鍵必須唯一、可排序這幾個(gè)需求。之前學(xué)習(xí)的哪種編碼結(jié)構(gòu)可以滿足？

• SkipList：可以排序，并且可以同時(shí)存儲(chǔ)score和ele值（member）
• HT（Dict）：可以鍵值存儲(chǔ)，并且可以根據(jù)key找value

圖片

圖片

當(dāng)元素?cái)?shù)量不多時(shí)，HT和SkipList的優(yōu)勢(shì)不明顯，而且更耗內(nèi)存。因此zset還會(huì)采用ZipList結(jié)構(gòu)來節(jié)省內(nèi)存，不過需要同時(shí)滿足兩個(gè)條件：

• 元素?cái)?shù)量小于zset_max_ziplist_entries，默認(rèn)值128
• 每個(gè)元素都小于zset_max_ziplist_value字節(jié)，默認(rèn)值64

ziplist本身沒有排序功能，而且沒有鍵值對(duì)的概念，因此需要有zset通過編碼實(shí)現(xiàn)：

• ZipList是連續(xù)內(nèi)存，因此score和element是緊挨在一起的兩個(gè)entry， element在前，score在后
• score越小越接近隊(duì)首，score越大越接近隊(duì)尾，按照score值升序排列

圖片

圖片

10.3. Redis數(shù)據(jù)結(jié)構(gòu)-Hash

Hash結(jié)構(gòu)與Redis中的Zset非常類似：

• 都是鍵值存儲(chǔ)
• 都需求根據(jù)鍵獲取值
• 鍵必須唯一

區(qū)別如下：

• zset的鍵是member，值是score；hash的鍵和值都是任意值
• zset要根據(jù)score排序；hash則無需排序

（1）底層實(shí)現(xiàn)方式：壓縮列表ziplist 或者 字典dict 當(dāng)Hash中數(shù)據(jù)項(xiàng)比較少的情況下，Hash底層才?壓縮列表ziplist進(jìn)?存儲(chǔ)數(shù)據(jù)，隨著數(shù)據(jù)的增加，底層的ziplist就可能會(huì)轉(zhuǎn)成dict，具體配置如下：

• hash-max-ziplist-entries 512
• hash-max-ziplist-value 64

當(dāng)滿足上面兩個(gè)條件其中之?的時(shí)候，Redis就使?dict字典來實(shí)現(xiàn)hash。Redis的hash之所以這樣設(shè)計(jì)，是因?yàn)楫?dāng)ziplist變得很?的時(shí)候，它有如下幾個(gè)缺點(diǎn)：

• 每次插?或修改引發(fā)的realloc操作會(huì)有更?的概率造成內(nèi)存拷貝，從而降低性能。
• ?旦發(fā)生內(nèi)存拷貝，內(nèi)存拷貝的成本也相應(yīng)增加，因?yàn)橐截惛?的?塊數(shù)據(jù)。
• 當(dāng)ziplist數(shù)據(jù)項(xiàng)過多的時(shí)候，在它上?查找指定的數(shù)據(jù)項(xiàng)就會(huì)性能變得很低，因?yàn)閦iplist上的查找需要進(jìn)行遍歷。

總之，ziplist本來就設(shè)計(jì)為各個(gè)數(shù)據(jù)項(xiàng)挨在?起組成連續(xù)的內(nèi)存空間，這種結(jié)構(gòu)并不擅長(zhǎng)做修改操作。?旦數(shù)據(jù)發(fā)?改動(dòng)，就會(huì)引發(fā)內(nèi)存realloc，可能導(dǎo)致內(nèi)存拷貝。

hash結(jié)構(gòu)如下：

圖片

zset集合如下：

圖片

因此，Hash底層采用的編碼與Zset也基本一致，只需要把排序有關(guān)的SkipList去掉即可：

Hash結(jié)構(gòu)默認(rèn)采用ZipList編碼，用以節(jié)省內(nèi)存。ZipList中相鄰的兩個(gè)entry 分別保存field和value

當(dāng)數(shù)據(jù)量較大時(shí)，Hash結(jié)構(gòu)會(huì)轉(zhuǎn)為HT編碼，也就是Dict，觸發(fā)條件有兩個(gè)：

• ZipList中的元素?cái)?shù)量超過了hash-max-ziplist-entries（默認(rèn)512）
• ZipList中的任意entry大小超過了hash-max-ziplist-value（默認(rèn)64字節(jié)）

圖片