面試題】Redis常用資料類型，以及底層實作

字元串（string），隊列（list），哈希（hash），集合（sets），有序集合（sorted sets）。

Redis中的字元串都是由動态字元串(simple dynamic string SDS)實作的

所有非數字的key。例如<code>set msg "hello world"</code> 中的key msg.

字元串資料類型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"

非字元串資料類型中的“字元串值”。例如<code>RPUSH fruits "apple" "banana" "cherry"</code>中的"apple" "banana" "cherry"。

SDS資料結構定義：

Redis 3.2之前的SDS這樣設計的有點：

1）有單獨的統計變量len和free（稱為頭部）。可以很友善地得到字元串長度。

2）内容存放在柔性數組buf中，SDS對上層暴露的指針不是指向結構體SDS的指針，而是直接指向柔性數組buf的指針。上層可像讀取C字元串一樣讀取SDS的内容，相容C語言處理字元串的各種函數。

3）由于有長度統計變量len的存在，讀寫字元串時不依賴“\0”終止符，保證了二進制安全。

list的底層資料結構時連結清單。Redis 3.2之前的版本（包含3.2）使用的時ziplist或者linkedlist，Redis 3.2之後版本使用的quicklist。

ziplist

壓縮清單是為了節約記憶體而開發的，是存儲在連續記憶體塊上的順序資料結構。一個壓縮清單可以包含任意多的 entry 節點，每個節點包含一個位元組數組或整數。redis 中并沒有顯式定義 ziplist 的資料結構，僅僅提供了一個描述結構 zlentry 用于操作資料。

各字段含義如下：

1、zlbytes：壓縮清單的位元組長度，占4個位元組，是以壓縮清單最長(2^32)-1位元組；

2、zltail：壓縮清單尾元素相對于壓縮清單起始位址的偏移量，占4個位元組；

3、zllen：壓縮清單的元素數目，占兩個位元組；那麼當壓縮清單的元素數目超過(2^16)-1怎麼處理呢？此時通過zllen字段無法獲得壓縮清單的元素數目，必須周遊整個壓縮清單才能擷取到元素數目；

4、entryX：壓縮清單存儲的若幹個元素，可以為位元組數組或者整數；entry的編碼結構後面詳述；

5、zlend：壓縮清單的結尾，占一個位元組，恒為0xFF。

該資料結構具有以下特征：

結構緊湊：一整塊連續記憶體，沒有多餘的記憶體碎片，更新會導緻記憶體 realloc 與記憶體複制，平均時間複雜度為 O(N)

逆向周遊：從表尾開始向表頭進行周遊

連鎖更新：對前一條資料的更新，可能導緻後一條資料的 prev_entry_length 與 encoding 所需長度變化，産生連鎖反應，更新操作最壞時間為 O(N2)

quicklist

在較早版本的 redis 中，list 有兩種底層實作：

當清單對象中元素的長度比較小或者數量比較少的時候，采用壓縮清單 ziplist 來存儲

當清單對象中元素的長度比較大或者數量比較多的時候，則會轉而使用雙向清單 linkedlist 來存儲

兩者各有優缺點：

ziplist 的優點是記憶體緊湊，通路效率高，缺點是更新效率低，并且資料量較大時，可能導緻大量的記憶體複制

linkedlist 的優點是節點修改的效率高，但是需要額外的記憶體開銷，并且節點較多時，會産生大量的記憶體碎片.

為了結合兩者的優點，在 redis 3.2 之後，list 的底層實作變為快速清單 quicklist。

快速清單是 linkedlist 與 ziplist 的結合: quicklist 包含多個記憶體不連續的節點，但每個節點本身就是一個 ziplist。

該資料結構有以下特征：

無縫切換：結合了 linkedlist 與 ziplist 的優點，無需在兩種結構之間進行切換

中間壓縮：作為隊列使用的場景下，list 中間的資料被通路的頻率比較低，可以選擇進行壓縮以減少記憶體占用。

hash 類型是 Redis 常用資料類型之一，其底層存儲結構有兩種實作方式。

當存儲的資料量較少的時，hash 采用 ziplist 作為底層存儲結構，此時要求符合以下兩個條件：

哈希對象儲存的所有鍵值對（鍵和值）的字元串長度總和小于 64 個位元組。

哈希對象儲存的鍵值對數量要小于 512 個。

當無法滿足上述條件時，hash 就會采用 dict（字典結構）來存儲資料，資料結構如下：

資料結構有以下特征：

雜湊演算法：使用 murmurhash2 作為哈希函數，時間複雜度為O(1)

沖突解決：使用鍊位址法解決沖突，新增元素會被放到表頭，時間複雜度為O(1)

Redis set 采用了兩種方式相結合的底層存儲結構，分别是 intset（整型數組）與 hash table（哈希表），當 set 存儲的資料滿足以下要求時，使用 intset 結構：

集合内儲存的所有成員都是整數值；

集合内儲存的成員數量不超過 512 個。

當不滿足上述要求時，則使用 hash table 結構。

intset 的結構體定義如下:

encoding：用來指定編碼格式，共有三種，分别是 INTSET_ENC_INT16、INSET_ENC_INT32 和 INSET_ENC_INT64，它們對應不同的數值範圍。Redis 為了盡可能地節省記憶體，它會根據插入資料的大小來選擇不同的編碼格式。

length：集合内成員的數量，記錄 contents 數組中共有多少個成員。

contents：存儲成員的數組，數組中的成員從小到大依次排列，且不允許重複。

有序整型集合，具有緊湊的存儲空間，添加操作的時間複雜度為O(N)

有序集合（zset）同樣使用了兩種不同的存儲結構，分别是 zipList（壓縮清單）和 skipList（跳躍清單），當 zset 滿足以下條件時使用壓縮清單：

成員的數量小于128 個；

每個 member （成員）的字元串長度都小于 64 個位元組。

當有序結合不滿足使用壓縮清單的條件時，就會使用 skipList 結構來存儲資料。

跳躍清單（skipList）又稱“跳表”是一種基于連結清單實作的随機化資料結構，其插入、删除、查找的時間複雜度均為 O(logN)。從名字可以看出“跳躍清單”，并不同于一般的普通連結清單，它的結構較為複雜，本節隻對它做淺顯的介紹，如有興趣可自行研究。

在 Redis 中一個 skipList 節點最高可以達到 64 層，一個“跳表”中最多可以存儲 2^64 個元素，每個節點都是一個 skiplistNode（跳表節點）。skipList 的結構體定義如下：

header：指向 skiplist 的頭節點指針，通過它可以直接找到跳表的頭節點，時間複雜度為 O(1)；

tail：指向 skiplist 的尾節點指針，通過它可以直接找到跳表的尾節點，時間複雜度為 O(1)；

length：記錄 skiplist 的長度，也就跳表中有多少個元素，但不包括頭節點；

level：記錄目前跳表内所有節點中的最大層數（level）；

跳躍清單的每一層都是一個有序的連結清單，連結清單中每個節點都包含兩個指針，一個指向同一層的下了一個節點，另一個指向下一層的同一個節點。最低層的連結清單将包含 zset 中的所有元素。如果說一個元素出現在了某一層，那麼低于該層的所有層都将包含這個元素，也就說高層是底層的子集。

查找：平均查找時間為O(logN)，最壞查找時間為O(N)，并且支援範圍查找

機率：每次建立節點的時候，程式根據幂次定律随機生成一個 1 至 32 之間的随機數，用于決定層高

排位：在查找節點的過程中，沿途通路過所有的跨度 span 累計起來，得到目标節點在表中的排位

好學若饑，謙卑若愚