1壓縮清單
壓縮清單是清單鍵和哈希鍵的底層實作，當一個清單鍵隻包含少量清單項，并且每個清單項要麼是小整數值，要麼就是長度比較短的字元串，那麼redis就會使用壓縮清單來實作。
1.1 壓縮清單的構成
壓縮清單是redis為了節約記憶體而開發的，是由一系列的特殊編碼的連續記憶體塊組成的順序型資料結構。一個壓縮清單可以包含任意多個節點，每個節點可以儲存一個位元組數組或一個整數值。
| 屬性 | 類型 | 長度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4位元組 | 記錄整個壓縮清單占用的記憶體位元組數 |
| zltail | uint32_t | 4位元組 | 記錄壓縮清單表尾節點距離壓縮清單的起始位址有多少位元組 |
| zllen | uint16_t | 2位元組 | 記錄了壓縮清單包含的節點數量：當屬性值小于uint16_max時，這個屬性值就是壓縮清單包含的節點，等于則需要周遊 |
| entryx | 清單節點 | 不定 | 壓縮清單包含的各個節點 |
| zlend | uint8_t | 1位元組 | 特殊值0xFF，用于标記壓縮清單的末端 |
1.2 壓縮清單節點的構成
每個壓縮清單節點可以儲存一個位元組數組或者一個整數值，其中，位元組數組可以是以下三種長度。
- 長度小于等于63位元組的位元組數組
- 長度小于等于16383 位元組的位元組數組
- 長度小于等于 4294967295位元組的位元組數組
整數值則可以是以下六種長度之一
- 4 位長，0-12 之間的無符号整數
- 1 位元組長的有符号整數
- 3 位元組長的有符号整數
- int16_t 類型整數
- int32_t 類型整數
- int64_t 類型整數
每個壓縮清單節點都由 previous_entry_length,encoding,content三個部分組成
1.2.1 previous_entry_length
節點的previous_entry_length屬性是以位元組為機關，記錄了壓縮清單中前一個節點的長度。previous_entry_length 長度可以是1位元組或者5位元組。
- 如果前一節點的長度小于254節點，那麼previous_entry_length 屬性的長度為1位元組
- 如果前一節點長度大于大等于254節點，那麼previous_entry_length屬性則為5位元組
因為previous_entry_length 屬性記錄了前一個節點的長度，是以指針可以通過指針運算，根據目前節點的起始位址來計算出前一個節點的起始位址
1.2.2 encoding
節點的encoding屬性記錄了節點的content屬性所儲存的資料類型以及長度。
- 一位元組，兩位元組或者五位元組長，值的最高位為00,01,或者10的是位元組數組編碼這種編碼表示節點的content屬性儲存着位元組數組，數組的長度由編碼除去最高兩位之後的其他位記錄。
- 一位元組長，值的最高位以11開頭的整數編碼：這種編碼表示節點的content屬性儲存着整數值，整數值的類型和長度由其他位記錄
1.2.3 content
節點的content屬性負責儲存節點的值，節點值可以是一個位元組數組或者整數，值的類型由encoding屬性決定。
1.3 連鎖更新
- 由于previous_entry_length 的屬性記錄了前一個節點的長度： 前一節點長度小于254節點，則其屬性需要用 1 位元組長的空間來儲存這個長度值
-
如果前一節點長度大于等于254節點，則需要5位元組來儲存
當在一個壓縮清單中，有多個連續的，長度介于250位元組到253位元組之間的節點，當新加的前一節點，導緻後一節點的previous_entry_length 更新增加，導緻總位元組大小增加，引起連鎖更新會導緻後面的節點也更新。
除了添加新節點會導緻連鎖更新外，删除節點也可能會引發連鎖更新。
由于連鎖更新在最壞的情況下需要對壓縮清單執行N次 空間重配置設定操作，而每次空間重配置設定最壞的複雜度為o（N），是以連鎖更新的最壞複雜度為o（N2）
要注意的是
- 首先，壓縮清單裡要恰好有多個連續的，長度介于250位元組至253位元組之間的更新才有可能被引發
- 其此出現連鎖更新，隻要被更新的節點數量不多，就不會對性能造成影響
1.4 重點
- 壓縮清單是一種節約記憶體而開發的順序型資料結構
- 壓縮清單被用作清單鍵和哈希鍵的底層實作
- 壓縮清單可以包含多個節點，每個節點都可以儲存
一個位元組數組或者整數值
- 添加新節點到壓縮清單，或者從壓縮清單中删除節點，可能會引發連鎖更新操作，但這種操作出現的幾率不高