壓縮列表

① Redis的五種數據結構及其底層實現原理

redis的字元串類型是由一種叫做簡單動態字元串(SDS)的數據類型來實現

SDC和C語言字元串的區別：
1：SDS保存了字元串的長度，而C語言不保存，只能遍歷找到第一個的結束符才能確定字元串的長度
2：修改SDS，會檢查空間是否足夠，不足會先擴展空間，防止緩沖區溢出，C字元串不會檢查
3：SDS的預分配空間機制，可以減少為字元串重新分配空間的次數
備註：重新分配空間方式，小於1M的數據 翻倍+1，例如：13K+13K+1，如果大於1M，每次多分配1M，例如：10M+1M+1,如果字元串變短，並不會立即縮短，而是採用惰性空間釋放，有專門的API可以釋放多餘空間

hash結構里其實是一個字典，有許多的鍵值對
redis的哈希表是一個dictht結構體：

哈希表節點的結構體如下：

hash演算法：
當要將一個新的鍵值對添加到字典裡面時， 程序需要先根據鍵值對的鍵計算出哈希值和索引值， 然後再根據索引值， 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。

hash沖突解決方式：鏈表法，後入的放到最前面
rehash：
鍵值數據量變動時，時為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內， 當哈希表保存的鍵值對數量太多或者太少時， 程序需要對哈希表的大小進行相應的擴展或者收縮。
如果是擴充，新數組的空間大小為 大於2*used的2的n次方，比如：used=5,則去大於10的第一個2的n次方，為16
如果是縮小，新數組的空間大小為第一個不大於used的2的n次方，比如：used=5,則新大小為4

redis的list列表是使用雙向鏈表來實現的
···
typedef struct listNode {
struct listNode * pre; //前置節點
struct listNode * next; //後置節點
void * value; //節點的值
}

typedef struct list {
listNode *head; //表頭節點
listNode tail; //表尾節點
unsigned long len; //鏈表所包含的節點數量
void ( p) (void ptr); //節點值賦值函數 這里有問題
void ( free) (void ptr); //節點值釋放函數
int ( match) (void *ptr, void *key) //節點值對比函數
}
···

1：有序集合的底層實現之一是跳錶， 除此之外跳錶它在 Redis 中沒有其他應用。
2：整數集合（intset）是集合鍵的底層實現之一： 當一個集合只包含整數值元素， 並且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合鍵的底層實現。
3：數據少是，使用ziplist(壓縮列表)，佔用連續內存，每項元素都是(數據+score)的方式連續存儲，按照score從小到大排序。ziplist為了節省內存，每個元素佔用的空間可以不同，對於大數據(long long),就多用一些位元組存儲，而對於小的數據(short)，就少用一些位元組來存儲。因此查找的時候需要按順序遍歷。ziplist省內存但是查找效率低。

無序集合可以用整數集合(intset)或者字典實現

Redis的5.0版本中，放出一個新的數據結構Stream。其實也是一個隊列，沒一個不同的key對應的是不同的隊列，沒個隊列的元素，也就是消息，都有一個msgid，並且需要保證msgid是嚴格遞增的。在Stream當中，消息是默認持久化的，即便是Redis重啟，也能夠讀取到信息。
Stream的多播，與其它隊列系統相似，對不同的消費者，也有消費者Group這樣的概念，不同的消費組，可以消費通一個消息，對於不同的消費組，都維護一個Idx下標，表示這一個消費群組費到了哪裡，每次進行消費，都會更新一下這個下標，往後面一位進行偏移。

跳躍表是一種有序數據結構，它通過在每個節點中維持多個指向其它節點的指針，從而大道快速訪問節點的目的，具有以下性質：
1：有很多層結構組成
2：每一層都是一個有序的鏈表，排列順序為由高到低，都至少包含兩個鏈表節點，分別是前面的head節點和後面的nil節點
3：最底層的鏈表包含了所有的元素
4：如果一個元素出現在某一層的鏈表中，那麼在該層之下的鏈表也全部都會出現
5：鏈表中的每個節點都包含兩個指針，一個指向同一層的下一個鏈表節點，另一個指向下一層的通一個鏈表節點

多個跳躍表節點構成一個跳躍表

1：搜索，從最高層的鏈表節點開始，如果比當前節點要大和比當前層的下一個節點要小，那麼則往下找，也及時和當前層的下一層的節點下一個節點
2：插入，首先確定插入的層數，有一種方法是拋一個硬幣，如果是正面就累加，直到遇到反面為止，最後記錄正面的次數作為插入的層數，當確定插入的層數K後，則需要將新元素插入從底層到K層
3：刪除，在各個層中找到包含指定值得節點，然後將節點從鏈表中刪除即可，如果刪除以後只剩下頭尾兩個節點，則刪除這一層。

整數集合是Redis用於保存整數值集合的抽象數據類型，它可以保存int16_t、int32_t、int64_t的整數值，並且保證集合中不會出現重復元素。

整數集合的每個元素都是contents數組的一個數據項，他們按照從小到大的順序排列，並且不包含任何重復項。
length屬性記錄了contents數組的大小。
需要注意的是雖然contents數組聲明為int8_t類型，但是實際上contents數組並不保存任何int8_t類型的值，其真正類型由encoding來決定。

壓縮列表(ziplist)是Redis為了節省內存而開發的，是由一系列特殊編碼的連續內存塊組成的順序型數據結構，一個壓縮列表可以包含任意多個節點(entry)，每個節點可以保存一個位元組數組或一個整數值。
壓縮列表的原理：壓縮列表並不是對數據利用某種演算法進行壓縮的，而是將數據按照一定規則編碼在一塊連續的內存區域，目的是節省內存。

壓縮列表的每個節點構成如下：