【說明】本文将介紹redis剩餘的4種對象結構以及5種資料結構。
2、清單對象
【前言】
清單對象的編碼可以是ziplist(壓縮清單)或者linkedlist(雙端連結清單)，當清單對象包含的元素比較少時會會使用壓縮清單，否則會使用雙端連結清單
具體政策是，當清單對象同時滿足以下兩個條件時，将使用壓縮清單編碼：
1、清單對象儲存的所有字元串元素的長度都小于64個位元組；
2、清單對象儲存的元素數量小于512個
如果上述兩個條件的任何一個不能被滿足，将使用雙端連結清單編碼
以上兩個條件的上限值是可以通過配置檔案中的list-max-ziplist-value、list-max-ziplist-entries來修改的
編碼轉換：
如果壓縮清單編碼的清單對象，不再滿足上述兩個條件時，将會被轉換為雙端清單編碼的格式
這種政策的優點是：
1.因為壓縮清單比雙端連結清單更節省記憶體，并且在元素數量較少時，在記憶體中以連續塊方式儲存的壓縮清單比起雙端連結清單可以更快的被載入到緩存中
2.随着清單對象包含的元素越來越多，使用壓縮清單來儲存元素的優勢逐漸消失，對象就會将底層實作從壓縮清單轉向功能更強、也更适合儲存大量元素的雙端連結清單上面
【壓縮清單--ziplist】
【結構】
壓縮清單(ziplist)是清單對象與哈希對象的底層資料結構
壓縮清單的節點可以儲存一個位元組數組或者一個整數值
對于清單對象而言，當一個清單鍵隻包含少量清單項，并且存儲的整數、字元串都是比較短小的，将使用壓縮清單
對于哈希對象而言，當一個哈希鍵隻包含少量鍵值對，并且鍵和值是小的整數或短的字元串時，将使用壓縮清單
【壓縮清單的結構】
壓縮清單的整體資料結構圖如下所示：
壓縮清單編碼的清單對象結構圖如下所示：
壓縮清單中各個屬性的具體含義如下：
zlbytes屬性：記錄壓縮清單占用的總的記憶體位元組數；在對壓縮清單進行記憶體重配置設定或計算壓縮清單末端位置(即zlend屬性所在位置)時需要用到該屬性
zltail屬性：記錄壓縮清單的最後一個清單節點的位置距離整個清單起始位址有多少位元組，通過該屬性，可以直接定位表尾節點的位址
zllen屬性：記錄壓縮清單的節點數量，當節點數量小于UNINT16_MAX(65535)時，該屬性會記錄節點數量的值，當節點數量大于65535時就不再存儲，需要周遊整個壓縮清單才能知道節點的總數量
entryX屬性：清單節點，用于存儲實際的數值，每個壓縮清單節點都由previous_entry_length、encoding、content三個部分組成
previous_entry_length屬性：記錄了前一個節點的長度
encoding屬性：實際要儲存值的資料類型及長度
content屬性：實際在節點中儲存的值，可以是一個位元組數組或一個整數
zlend屬性：是一個特殊值OxFF(十進制255)，用于标記壓縮清單的末端
包含三個節點的壓縮清單結構示意圖：
【清單節點中3個屬性的詳細說明】
1、previous_entry_length屬性：
該屬性記錄了壓縮清單中前一個節點的長度，機關是位元組，長度可以是1位元組或5位元組，具體政策為：
如果前一個節點的長度小于254位元組，previous_entry_length屬性将用1個位元組的長度
如果前一個節點的長度大于等于254位元組，previous_entry_length屬性将用5個位元組的長度，第1個位元組為固定的OxFE(十進制254)，之後的4個位元組被用來儲存前一個節點的長度
壓縮清單從表位向表頭周遊的原理：
向壓縮清單中存儲資料的時候，最先存儲的資料被放在清單尾部，新插入的資料會被放到舊資料的前面，讀取壓縮清單的順序是由表尾到表頭(讀取最舊的資料到最新的資料)
在讀取資料的時候，會先讀取zltail屬性，通過該屬性可以直接定位到壓縮清單的表尾節點，然後通過previous_entry_length屬性，依次找到上一個節點的資料，由後向前，可以依次讀取出所有的資料
2、encoding屬性
該屬性記錄了實際要儲存值的資料類型及長度
3、content屬性
該屬性記錄了儲存節點的值，節點值可以是一個位元組數組如”hello world”或者整數
【連鎖更新】
上文說過：
previous_entry_length屬性：記錄了前一個節點的長度（機關位元組）
如果前一個節點的長度大于等于254位元組，previous_entry_length屬性将用5個位元組的長度
如果碰巧發生這種情況：
如果每一個節點的值都<254且>250，那麼previous_entry_length屬性的值都為1，但現在新插入一個值，該值的長度>=254，那麼後面節點的previous_entry_length屬性的值都将變為5。
即牽一發而動全身，後面每個節點的大小都需要發生改變
除新增節點會導緻連鎖更新外，删除一個節點也有可能導緻連鎖更新，如下圖所示：
總結：
壓縮清單是一種為節約記憶體而開發的順序型資料結構
壓縮清單可以包含多個節點，每個節點可以儲存一個位元組數組或整數值，可以被用于清單對象和哈希對象
添加新節點到壓縮清單，或者從壓縮清單中删除節點，可能會引發連鎖更新操作，但這種幾率并不高
【雙端連結清單--linkedlist】
當一個清單鍵包含了數量比較多的元素，或者清單中包含的元素都是比較長的字元串時，redis會使用連結清單作為清單鍵的底層實作。
除了list清單對象、zset有序集合對象用到了連結清單之外，釋出與訂閱、慢查詢、螢幕等功能也用到了連結清單，redis伺服器本身還使用連結清單來儲存多個用戶端的狀态資訊，以及使用連結清單來建構用戶端輸出緩沖區(output buffer)。
【連結清單結構】
連結清單結構由list+listnode兩部分組成。
list結構：
head：表頭節點
tail：表尾節點
len：連結清單所包含的節點數量
dup：節點值複制函數，用于複制連結清單節點所儲存的值
free：節點值釋放函數，使用者釋放連結清單節點所儲存的值
match：節點值對比函數，用于對比連結清單節點所儲存的值和另一個輸入值是否相等
dup、free、match是用于實作多态連結清單所需的類型特定函數
連結清單節點(listNode)結構：
prev 前置節點
next 後置節點
value 節點的值
【連結清單結構的特點】
雙端：連結清單節點帶有prev和next指針，擷取某個節點的前置節點和後置節點的複雜度都是O(1)
無環：表頭節點的prev指針和表尾節點的next指針都指向NULL，對連結清單的通路以NULL為終點
有表頭指針和表尾指針：通過list結構的head指針和tail指針，程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)
有連結清單長度計數器：list結構的len屬性可以對連結清單節點進行計數，程式擷取連結清單節點數量的複雜度為O(1)
多态：連結清單節點使用value屬性儲存節點值，并且可以通過list結構的dup、free、match三個屬性為節點值設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值
linkedlist編碼的清單對象，在存儲上有以下特點：
linkedlist編碼的清單對象，每個雙端連結清單節點（node）都儲存了一個字元串對象
中的字元串，即字元串對象嵌套在清單結構中，示意圖如下所示：
上圖中tree字元串對象的完整結構圖如下所示：
3、哈希對象
哈希對象的編碼可以是ziplist(壓縮清單)或hashtable(字典)
當哈希對象可以同時滿足以下兩個條件時，哈希對象使用壓縮清單編碼：
哈希對象儲存的所有鍵值對的鍵和值的字元串長度都小于64位元組
哈希對象儲存的鍵值對數量小于512個
當其中一個條件不能滿足時，哈希對象使用hashtable(字典)編碼的格式
這兩個條件的上限值可以通過配置檔案中的hash-max-ziplist-value選項和hash-max-ziplist-entries選項來修改
編碼轉換：如果壓縮清單編碼的哈希對象，不再滿足上述兩個條件時，将被轉換為字典編碼的格式
壓縮清單的詳細結構上文已介紹過，這裡不再贅述
壓縮清單編碼的哈希對象，在存儲上有以下特點：
儲存了同一鍵值對的兩個節點總是緊挨在一起，儲存鍵的節點在前，儲存值的節點在後
先添加到哈希對象的鍵值對會被放在壓縮清單的表頭方向，而後來添加到哈希對象中的鍵值對會被放在壓縮清單的表尾方向
結構示意圖如下所示：
【字典】
【字典的特點】
字典是以key-value方式存儲資料的一種結構，字典中的每個鍵都是獨一無二的，程式可以在字典中根據鍵查找、更新、删除與之關聯的值，當字典中存儲的資料過多或過少，都會通過rehash重新配置設定字典的大小和結構。
【字典的用途】
1、redis的資料庫就是使用字典來作為底層實作的，對資料庫的增删改查是建構在對字典的操作之上的；
2、是哈希鍵的底層實作之一，當一個哈希鍵包含的鍵值對比較多，或者鍵值對中的元素都是比較長的字元串時，redis會使用字典作為哈希鍵的底層實作
3、是集合底層的實作之一
【字典的結構】
字典主要由3部分結構共同組成：
字典+哈希表+哈希節點
一個完整的字典結構如下圖所示：
其中dict是字典結構，dictht是哈希表的結構，dictEntry*是哈希節點的結構，最右邊是哈希節點儲存的鍵值對的值，k0、k1是鍵，v0、v1是對應的值
下面分别詳細介紹一下這三種結構：
【字典結構】
字典結構dict.h/dict有以下幾個參數：
具體說明如下：
ht屬性是一個包含兩個項的數組，數組中的每一個項都是一個dictht哈希表，一般情況下，字典隻是用ht[0]哈希表，ht[1]哈希表隻會在rehash時使用
rehashidx屬性，記錄了rehash的進度，如果沒有在rehash，則值為-1
type和dicttype屬性，保證了redis可以存儲不同類型的鍵值對
【哈希表結構】
一個空的哈希表(沒有任何鍵值對)整體結構圖如下所示：
哈希表由dict.h/dictht結構定義，裡面具體有table、size、used、sizemask幾個屬性：
table屬性是一個數組，數組中的每個元素都是一個指向dict.h/dictEntry(哈希表節點)結構的指針，每個dictEntry結構儲存着一個鍵值對
size屬性記錄了哈希表的大小，也即table數組的大小
used屬性記錄了哈希表目前已有節點(鍵值對)的數量
sizemask屬性的值總是等于size-1，這個屬性和哈希值一起決定一個鍵應該被放到table數組的哪個索引上面
【哈希表節點結構】
因為dictentry結構中并沒有屬性指向連結清單表尾的指針，是以為了速度考慮，程式總是将新節點添加到連結清單的表頭位置(複雜度O(1))，排在其它已有節點的前面
【rehash--重新散列】
為保持哈希表中資料配置設定的合理性，當哈希表儲存的鍵值對數量太多或者太少時，程式需要對哈希表的大小進行相應的擴充和收縮
對哈希表的擴充和收縮是通過執行rehash(重新散列)操作完成的，redis對字典的哈希表進行rehash的步驟如下：
1、為字典的ht[1]哈希表配置設定空間，配置設定政策為：
如果要執行的是擴充操作，那麼ht[1]的大小為第一個大于等于ht[0].used2的2的n次幂(示例：如果used=3，size=3，32=6，第一個大于等于6且是2的n次幂的值是8，是以ht[1]的size大小為8)
如果執行的是收縮操作，那麼ht[1]的大小為第一個大于等于ht[0].used的2的n次幂(示例：如果used=3，但size=10，ht[1]的size值将為4，used是哈希表中實際存儲的資料的節點數，size是哈希表大小即可以存儲多少個資料節點)
2、将儲存在ht[0]中的所有鍵值對rehash到ht[1]
3、釋放ht[0]，将ht[1]設定為ht[0]，并在ht[1]建立一個空白哈希表，為下一次rehash做準備
【哈希表的擴充與收縮】
當哈希表中的資料過于緊密或疏松時，會對哈希表進行擴充與收縮，具體政策如下：
負載因子=哈希表已儲存節點數量/哈希表大小
load_factor = ht[0].used/ht[0].size
當哈希表的負載因自小于0.1時，程式自動開始對哈希表執行收縮操作
當以下條件中的任意一個被滿足時，程式會自動開始對哈希表執行擴充操作：
1.伺服器目前沒有在執行BGSAVE或BGREWRITEAOF指令，并且哈希表的負載因子大于等于1
2.伺服器目前正在BGSAVE或BGREWRITEAOF指令，并且哈希表的負載因子大于等于5
當正在執行BGSAVE或BGREWRITEAOF指令時，redis會建立子程序，會用到寫時複制技術，需要占用部分記憶體，此時盡可能避免對哈希表進行擴充，避免消耗不必要的記憶體
【漸進式rehash】
為了避免rehash對伺服器性能造成影響，伺服器不是一次将ht[0]裡面所有的鍵值對全部rehash到ht[1]，而是分批次漸進式的rehash
在漸進式rehash期間，字典會同時使用ht[0]、ht[1]兩個哈希表，期間對字典的查、删、改都是在兩個哈希表中進行的。如果要在字典裡查找一個鍵，會先在ht[0]裡面查找，如果沒找到，會繼續到ht[1]裡進行查找。但是新增加的鍵值對一律會被儲存到ht[1]中，是以ht[0]裡的鍵值對隻減不增
字典編碼的哈希對象，在存儲上有以下特點：
字典中的每個鍵、值都是一個字元串對象
4、集合對象
集合對象可以用來存儲不重複的資料。
集合對象的編碼可以是intset(整數集合)或者hashtable(字典)
具體政策為：
當集合對象同時滿足以下兩個條件時，将使用intset編碼：
集合對象儲存的所有元素都是整數值
集合對象儲存的元素數量不超過512個
不能滿足這兩個條件的集合對象需要使用hashtable編碼
上述兩個條件可以通過配置檔案中的set-max-intset-entries選項來修改
【編碼轉換】當intset編碼的集合對象不再滿足上述兩個條件時，将會轉換為hashtable編碼的格式
【整數集合】
整數集合(intset)是用來存儲整數集合的結構，它可以儲存int16_t、int32_t或int64_t的整數，并且保證資料不會重複。
contents數組裡記錄了具體的資料，數組中的資料按值的大小從小到大有序地排列
length屬性記錄了資料的個數，即contents數組的長度
enconding屬性記錄了數組中資料的類型，可以為intset_enc_int16、intset_enc_int32、intset_enc_int64，對應的類型分别是int16_t、int32_t、int64_t
更新
當新添加的資料比整數集合現有的資料類型都要長時，需要先對整數集合進行更新，然後再添加新資料。
更新步驟：
根據新資料的類型，擴充整數集合底層數組的空間大小
将原有資料的類型均轉換為新類型
添加新資料
因為每次向整數集合添加新元素都可能引起更新，而每次更新都需要對底層數組中已有的所有元素進行類型轉換，是以向整數集合添加新元素的時間複雜度為O(N)。
整數集合不支援降級操作，一旦對數組進行了更新，編碼就會一直保持更新後對狀态。
5、有序集合
有序集合對編碼可以是ziplist或者skiplist。
具體政策規則是：
當有序集合對象可以同時滿足以下兩個條件時，将使用ziplist編碼：
有序集合儲存對元素數量小于128個
有序集合儲存的所有元素成員對長度都小于64位元組
不能滿足以上兩個條件的有序集合對象都使用skiplist編碼
以上兩個條件的上限值可以通過配置檔案中的zset-max-ziplist-entries和zset-max-ziplist-value選項來修改
【編碼的轉換】當ziplist編碼的有序集合不再符合上述兩個條件時，将被轉換為skiplist編碼的格式。
ziplist編碼的有序集合的存儲方式：
ziplist編碼以壓縮清單結構作為底層實作，每個集合元素使用兩個緊挨在一起對壓縮清單節點來儲存。第一個節點儲存元素的成員(member)，第二個元素儲存元素對分值(score)。壓縮清單内對元素按分值大小進行拍下，分值較小對元素放在靠近表頭對位置，結構示意圖如下所示：
壓縮清單結構之前已進行過詳細說明，這裡就不再贅述，下面将詳細說明下skiplist編碼。
Skiplist-字典+跳躍表
skiplist編碼的有序集合對象使用zset結構作為底層實作，一個zset結構同時包含一個字典和一個跳躍表，dict指針指向的是字典結構，zsl指針指向的是跳躍表結構，見下圖。
字典結構之前已有過詳細說明，這裡不再贅述，下面先說一下跳躍表結構：
【跳躍表】
如果一個有序集合包含的元素數量比較多，或者儲存的字元串長度較長，redis将使用跳躍表作為有序集合鍵的底層實作。
redis隻在兩個地方用到了跳躍表，一個是實作有序集合鍵，另一個是在叢集節點中用作内部資料結構。
【跳躍表結構】
跳躍表由zskiplist和zskiplistNode兩個結構組成，其中zskiplist用于儲存跳躍表資訊(比如表頭節點、表尾節點、長度)，而zskiplistNode則用于表示跳躍表節點。
上圖左側是zskiplist結構，其包含以下屬性：
Header：指向跳躍表的表頭節點
Tail：指向跳躍表的表尾節點
Level：記錄目前跳躍表内，層數最大的那個節點的層數(表頭節點的層數不計算在内)
Length：記錄跳躍表的長度，即目前節點的數量
上圖右側是四個zskiplistNode結構，該結構有以下屬性：
層(level)：L1、L2、L3等字樣表示各節點的層，連線上帶有數字箭頭的是前進指針，箭頭上的數字表示跨度。前進節點可以挨個周遊，也可以一次跳過多個節點
後退(backward)指針：節點中用BW字樣标記的是後退指針。後退節點每次隻能退至前一個節點。
分值(score)：各個節點中的1.0、2.0和3.0是節點儲存的分值，在跳躍表中，節點按各自所儲存的分值從小到大排列
成員對象(obj)：各個節點中的o1、o2和o3是節點所儲存的成員對象。
分值和成員
節點的分值(score屬性)是一個double類型的浮點數，跳躍表中的所有節點都按分值從小到大來排序
節點的成員對象(obj屬性)是一個指針，它指向一個字元串對象，而字元串對象則儲存着一個SDS值
在同一個跳躍表中，各個節點儲存的成員對象必須是唯一的，但是多個節點儲存的分值卻可以是相同的，分值相同的節點将按照成員對象在字典序中的大小來進行排序，成員對象較小的節點會排在前面(靠近表頭的位置)
【進一步說明】
zset結構中的zsl跳躍表按分值從小到大儲存了所有集合元素，每個跳躍表節點都儲存了一個集合元素：跳躍表節點的object屬性儲存了元素的成員，而跳躍表節點的score屬性則儲存了元素的分值。通過這個跳躍表，程式可以對有序集合進行範圍操作，如zrank、zrange等指令就是基于跳躍表api來實作的。
除此之外，zset結構中的dict字典為有序集合建立了一個從成員到分值的映射，字典中的每個鍵值對都儲存了一個集合元素：字典的鍵儲存了元素的成員，而字典的值則儲存了元素的分值。通過這個字典，程式可以用O(1)複雜度查找給定成員的分值，zscore指令就是根據這一特性實作的，而很多其它有序集合指令都在實作的内部用到了這一特性。
有序集合每個元素的成員都是一個字元串對象，而每個元素的分值都是一個double類型的浮點數。值得一提的是，雖然zset結構同時使用跳躍表和字典來儲存有序集合元素，但這兩種資料結構都會通過指針來共享相同元素的成員和分值，是以同時使用跳躍表和字典來儲存集合元素不會産生任何重複成員或分值，也不會是以浪費額外的記憶體。
【為什麼有序集合需要同時使用跳躍表和字典來實作？】
為了儲存兩種結構各自的優點，字典結構可以以O(1)複雜度查找成語的分值，但字典以無序但方式來儲存集合元素；而跳躍表結構用範圍查詢時複雜度隻要O(1).