1、概述

　　　　相信使用過Redis 的各位同學(xué)都很清楚，Redis 是一個(gè)基于鍵值對（key-value）的分布式存儲(chǔ)系統(tǒng)，與Memcached類似，卻優(yōu)于Memcached的一個(gè)高性能的key-value數(shù)據(jù)庫。

　　　　在《Redis設(shè)計(jì)與實(shí)現(xiàn)》這樣描述：

　　　　Redis 數(shù)據(jù)庫里面的每個(gè)鍵值對（key-value） 都是由對象（object）組成的：

　　　　　　數(shù)據(jù)庫鍵總是一個(gè)字符串對象（string object）;

　　　　　　數(shù)據(jù)庫的值則可以是字符串對象、列表對象（list）、哈希對象（hash）、集合對象（set）、有序集合（sort set）對象這五種對象中的其中一種。

　　　　我們?yōu)槭裁磿?huì)說Redis 優(yōu)于Memcached 呢，因?yàn)镽edis 的出現(xiàn)，豐富了memcached 中key-value的存儲(chǔ)不足，在部分場合可以對關(guān)系數(shù)據(jù)庫起到很好的補(bǔ)充作用，而且這些數(shù)據(jù)類型都支持push/pop、add/remove及取交集并集和差集及更豐富的操作，而且這些操作都是原子性的。　　

　　　　我們今天探討的并不是Redis 中value 的數(shù)據(jù)類型，而是他們的具體實(shí)現(xiàn)——底層數(shù)據(jù)類型。

　　　　Redis 底層數(shù)據(jù)結(jié)構(gòu)有一下數(shù)據(jù)類型：

1. 　簡單動(dòng)態(tài)字符串

2.    鏈表

3.    字典

4.    跳躍表

5.    整數(shù)集合

6.    壓縮列表

7.    對象

　　　　我們接下來會(huì)一步一步的探討這些數(shù)據(jù)結(jié)構(gòu)有什么特點(diǎn)，已經(jīng)他們是如何構(gòu)成我們所使用的value 數(shù)據(jù)類型。

2、簡單動(dòng)態(tài)字符串（simple dynamic string）SDS

2.1 概述

　　　Redis 是一個(gè)開源的使用ANSI C語言編寫的key-value 數(shù)據(jù)庫，我們可能會(huì)較為主觀的認(rèn)為 Redis 中的字符串就是采用了C語言中的傳統(tǒng)字符串表示，但其實(shí)不然，Redis 沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一種名為簡單動(dòng)態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis 的默認(rèn)字符串表示：

redis>SET msg "hello world"
OK

　　　設(shè)置一個(gè)key= msg，value = hello world 的新鍵值對，他們底層是數(shù)據(jù)結(jié)構(gòu)將會(huì)是：

　　　　　鍵（key）是一個(gè)字符串對象，對象的底層實(shí)現(xiàn)是一個(gè)保存著字符串“msg” 的SDS；

　　　　　值（value）也是一個(gè)字符串對象，對象的底層實(shí)現(xiàn)是一個(gè)保存著字符串“hello world” 的SDS

　　　從上述例子，我們可以很直觀的看到我們在平常使用redis 的時(shí)候，創(chuàng)建的字符串到底是一個(gè)什么樣子的數(shù)據(jù)類型。除了用來保存字符串以外，SDS還被用作緩沖區(qū)（buffer）AOF模塊中的AOF緩沖區(qū)。

2.2  SDS 的定義

　　Redis 中定義動(dòng)態(tài)字符串的結(jié)構(gòu)：

/*  
 * 保存字符串對象的結(jié)構(gòu)  
 */  
struct sdshdr {  
      
    // buf 中已占用空間的長度  
    int len;  
  
    // buf 中剩余可用空間的長度  
    int free;  
  
    // 數(shù)據(jù)空間  
    char buf[];  
};  

　　　1、len 變量，用于記錄buf 中已經(jīng)使用的空間長度（這里指出Redis 的長度為5）

　　　2、free 變量，用于記錄buf 中還空余的空間（初次分配空間，一般沒有空余，在對字符串修改的時(shí)候，會(huì)有剩余空間出現(xiàn)）

　　   3、buf 字符數(shù)組，用于記錄我們的字符串（記錄Redis）

2.3  SDS 與 C 字符串的區(qū)別

　　　　傳統(tǒng)的C 字符串 使用長度為N 1 的字符串?dāng)?shù)組來表示長度為N 的字符串，這樣做在獲取字符串長度，字符串?dāng)U展等操作的時(shí)候效率低下。C 語言使用這種簡單的字符串表示方式，并不能滿足Redis 對字符串在安全性、效率以及功能方面的要求

2.3.1 獲取字符串長度（SDS O（1）/C 字符串 O(n)）

 　　　　傳統(tǒng)的C 字符串 使用長度為N 1 的字符串?dāng)?shù)組來表示長度為N 的字符串，所以為了獲取一個(gè)長度為C字符串的長度，必須遍歷整個(gè)字符串。

　　　　 和C 字符串不同，SDS 的數(shù)據(jù)結(jié)構(gòu)中，有專門用于保存字符串長度的變量，我們可以通過獲取len 屬性的值，直接知道字符串長度。

2.3.2 杜絕緩沖區(qū)溢出

　　　　C 字符串 不記錄字符串長度，除了獲取的時(shí)候復(fù)雜度高以外，還容易導(dǎo)致緩沖區(qū)溢出。

 　　　　假設(shè)程序中有兩個(gè)在內(nèi)存中緊鄰著的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 則保存了字符串“MongoDb”：

　　　　 如果我們現(xiàn)在將s1 的內(nèi)容修改為redis cluster，但是又忘了重新為s1 分配足夠的空間，這時(shí)候就會(huì)出現(xiàn)以下問題：

　　　　  我們可以看到，原本s2 中的內(nèi)容已經(jīng)被S1的內(nèi)容給占領(lǐng)了，s2 現(xiàn)在為 cluster，而不是“Mongodb”。

　　　　 Redis 中SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：

　　　　 當(dāng)我們需要對一個(gè)SDS 進(jìn)行修改的時(shí)候，redis 會(huì)在執(zhí)行拼接操作之前，預(yù)先檢查給定SDS 空間是否足夠，如果不夠，會(huì)先拓展SDS 的空間，然后再執(zhí)行拼接操作

2.3.3 減少修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)　　　

　　C語言字符串在進(jìn)行字符串的擴(kuò)充和收縮的時(shí)候，都會(huì)面臨著內(nèi)存空間的重新分配問題。

　　　1. 字符串拼接會(huì)產(chǎn)生字符串的內(nèi)存空間的擴(kuò)充，在拼接的過程中，原來的字符串的大小很可能小于拼接后的字符串的大小，那么這樣的話，就會(huì)導(dǎo)致一旦忘記申請分配空間，就會(huì)導(dǎo)致內(nèi)存的溢出。

　　　2. 字符串在進(jìn)行收縮的時(shí)候，內(nèi)存空間會(huì)相應(yīng)的收縮，而如果在進(jìn)行字符串的切割的時(shí)候，沒有對內(nèi)存的空間進(jìn)行一個(gè)重新分配，那么這部分多出來的空間就成為了內(nèi)存泄露。

　　舉個(gè)例子：我們需要對下面的SDS進(jìn)行拓展，則需要進(jìn)行空間的拓展，這時(shí)候redis 會(huì)將SDS的長度修改為13字節(jié)，并且將未使用空間同樣修改為1字節(jié) 

　　　因?yàn)樵谏弦淮涡薷淖址臅r(shí)候已經(jīng)拓展了空間，再次進(jìn)行修改字符串的時(shí)候會(huì)發(fā)現(xiàn)空間足夠使用，因此無須進(jìn)行空間拓展

　　通過這種預(yù)分配策略，SDS將連續(xù)增長N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次

2.3.4 惰性空間釋放

　　　　我們在觀察SDS 的結(jié)構(gòu)的時(shí)候可以看到里面的free 屬性，是用于記錄空余空間的。我們除了在拓展字符串的時(shí)候會(huì)使用到free 來進(jìn)行記錄空余空間以外，在對字符串進(jìn)行收縮的時(shí)候，我們也可以使用free 屬性來進(jìn)行記錄剩余空間，這樣做的好處就是避免下次對字符串進(jìn)行再次修改的時(shí)候，需要對字符串的空間進(jìn)行拓展。

　　　　然而，我們并不是說不能釋放SDS 中空余的空間，SDS 提供了相應(yīng)的API，讓我們可以在有需要的時(shí)候，自行釋放SDS 的空余空間。

　　　　通過惰性空間釋放，SDS 避免了縮短字符串時(shí)所需的內(nèi)存重分配操作，并未將來可能有的增長操作提供了優(yōu)化

2.3.5 二進(jìn)制安全

　　　　C 字符串中的字符必須符合某種編碼，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存想圖片，音頻，視頻，壓縮文件這樣的二進(jìn)制數(shù)據(jù)。

　　　　但是在Redis中，不是靠空字符來判斷字符串的結(jié)束的，而是通過len這個(gè)屬性。那么，即便是中間出現(xiàn)了空字符對于SDS來說，讀取該字符仍然是可以的。

　　　　例如：

2.3.6 兼容部分C字符串函數(shù)

 　　　　雖然SDS 的API 都是二進(jìn)制安全的，但他們一樣遵循C字符串以空字符串結(jié)尾的慣例。

2.3.7 總結(jié)

3、鏈表

3.1 概述

　　鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問方式，并且可以通過增刪節(jié)點(diǎn)來靈活地調(diào)整鏈表的長度。

　　鏈表在Redis 中的應(yīng)用非常廣泛，比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。當(dāng)一個(gè)列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長的字符串時(shí)，Redis 就會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)?！?/p>

3.2 鏈表的數(shù)據(jù)結(jié)構(gòu)

　　　每個(gè)鏈表節(jié)點(diǎn)使用一個(gè) listNode結(jié)構(gòu)表示（adlist.h/listNode）：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

　　　多個(gè)鏈表節(jié)點(diǎn)組成的雙端鏈表：

 　　　　我們可以通過直接操作list 來操作鏈表會(huì)更加方便：

typedef struct list{
    //表頭節(jié)點(diǎn)
    listNode  * head;
    //表尾節(jié)點(diǎn)
    listNode  * tail;
    //鏈表長度
    unsigned long len;
    //節(jié)點(diǎn)值復(fù)制函數(shù)
    void *(*dup) (void *ptr);
    //節(jié)點(diǎn)值釋放函數(shù)
    void (*free) (void *ptr);
    //節(jié)點(diǎn)值對比函數(shù)
    int (*match)(void *ptr, void *key);
}

 　　　　list 組成的結(jié)構(gòu)圖：

3.3 鏈表的特性

• 雙端：鏈表節(jié)點(diǎn)帶有prev 和next 指針，獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的時(shí)間復(fù)雜度都是O（N）

• 無環(huán)：表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的next 都指向NULL，對立案表的訪問時(shí)以NULL為截止

• 表頭和表尾：因?yàn)殒湵韼в衕ead指針和tail 指針，程序獲取鏈表頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)

• 長度計(jì)數(shù)器：鏈表中存有記錄鏈表長度的屬性 len

• 多態(tài)：鏈表節(jié)點(diǎn)使用 void* 指針來保存節(jié)點(diǎn)值，并且可以通過list 結(jié)構(gòu)的dup 、 free、 match三個(gè)屬性為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)。

4、字典

4.1 概述

 　　　字典，又稱為符號(hào)表（symbol table）、關(guān)聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)?！?/p>

　　　 在字典中，一個(gè)鍵（key）可以和一個(gè)值（value）進(jìn)行關(guān)聯(lián)，字典中的每個(gè)鍵都是獨(dú)一無二的。在C語言中，并沒有這種數(shù)據(jù)結(jié)構(gòu)，但是Redis 中構(gòu)建了自己的字典實(shí)現(xiàn)。

　　　 舉個(gè)簡單的例子：

redis > SET msg "hello world"
OK

　　　 創(chuàng)建這樣的鍵值對（“msg”，“hello world”）在數(shù)據(jù)庫中就是以字典的形式存儲(chǔ)

4.2 字典的定義

　　　4.2.1 哈希表

　　　Redis 字典所使用的哈希表由 dict.h/dictht 結(jié)構(gòu)定義：

typedef struct dictht {
   //哈希表數(shù)組
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩碼，用于計(jì)算索引值
   unsigned long sizemask;
   //該哈希表已有節(jié)點(diǎn)的數(shù)量
   unsigned long used;
}

　　　我們可以看到，在結(jié)構(gòu)中存有指向dictEntry 數(shù)組的指針，而我們用來存儲(chǔ)數(shù)據(jù)的空間既是dictEntry

         4.2.2 哈希表節(jié)點(diǎn)（ dictEntry ）

　　　dictEntry 結(jié)構(gòu)定義：

typeof struct dictEntry{
   //鍵
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;

}

　　　在數(shù)據(jù)結(jié)構(gòu)中，我們清楚key 是唯一的，但是我們存入里面的key 并不是直接的字符串，而是一個(gè)hash 值，通過hash 算法，將字符串轉(zhuǎn)換成對應(yīng)的hash 值，然后在dictEntry 中找到對應(yīng)的位置。

        這時(shí)候我們會(huì)發(fā)現(xiàn)一個(gè)問題，如果出現(xiàn)hash 值相同的情況怎么辦？Redis 采用了鏈地址法：

　　　當(dāng)k1 和k0 的hash 值相同時(shí)，將k1中的next 指向k0 想成一個(gè)鏈表。

　　　4.2.3 字典

typedef struct dict {
    // 類型特定函數(shù)
    dictType *type;
    // 私有數(shù)據(jù)
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

　　　　type 屬性 和privdata 屬性是針對不同類型的鍵值對，為創(chuàng)建多態(tài)字典而設(shè)置的。

　　　　ht 屬性是一個(gè)包含兩個(gè)項(xiàng)（兩個(gè)哈希表）的數(shù)組

　　　　普通狀態(tài)下的字典：

4.3 解決哈希沖突

 　　在上述分析哈希節(jié)點(diǎn)的時(shí)候我們有講到：在插入一條新的數(shù)據(jù)時(shí)，會(huì)進(jìn)行哈希值的計(jì)算，如果出現(xiàn)了hash值相同的情況，Redis 中采用了連地址法（separate chaining）來解決鍵沖突。每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next 指針，多個(gè)哈希表節(jié)點(diǎn)可以使用next 構(gòu)成一個(gè)單向鏈表，被分配到同一個(gè)索引上的多個(gè)節(jié)點(diǎn)可以使用這個(gè)單向鏈表連接起來解決hash值沖突的問題。

　　舉個(gè)例子：

　　現(xiàn)在哈希表中有以下的數(shù)據(jù)：k0 和k1

　　  我們現(xiàn)在要插入k2，通過hash 算法計(jì)算到k2 的hash 值為2，即我們需要將k2 插入到dictEntry[2]中：

　　   在插入后我們可以看到，dictEntry指向了k2，k2的next 指向了k1，從而完成了一次插入操作（這里選擇表頭插入是因?yàn)楣１砉?jié)點(diǎn)中沒有記錄鏈表尾節(jié)點(diǎn)位置）

4.4 Rehash

　　隨著對哈希表的不斷操作，哈希表保存的鍵值對會(huì)逐漸的發(fā)生改變，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍之內(nèi)，我們需要對哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者壓縮，這時(shí)候，我們可以通過 rehash（重新散列）操作來完成。

　　4.4.1 目前的哈希表狀態(tài)：

　　　　我們可以看到，哈希表中的每個(gè)節(jié)點(diǎn)都已經(jīng)使用到了，這時(shí)候我們需要對哈希表進(jìn)行拓展。

　　4.4.2 為哈希表分配空間

　　　　哈希表空間分配規(guī)則：

　　　　　　如果執(zhí)行的是拓展操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0] 的2的n次冪

　　　　　　如果執(zhí)行的是收縮操作，那么ht[1] 的大小為第一個(gè)大于等于ht[0] 的2的n次冪

　　　　因此這里我們?yōu)閔t[1] 分配 空間為8，

　　4.4.3 數(shù)據(jù)轉(zhuǎn)移

　　　　將ht[0]中的數(shù)據(jù)轉(zhuǎn)移到ht[1]中，在轉(zhuǎn)移的過程中，需要對哈希表節(jié)點(diǎn)的數(shù)據(jù)重新進(jìn)行哈希值計(jì)算

　　　　數(shù)據(jù)轉(zhuǎn)移后的結(jié)果：

 　　4.4.4 釋放ht[0]

　　　　將ht[0]釋放，然后將ht[1]設(shè)置成ht[0]，最后為ht[1]分配一個(gè)空白哈希表：

　　4.4.5 漸進(jìn)式 rehash

　　　　上面我們說到，在進(jìn)行拓展或者壓縮的時(shí)候，可以直接將所有的鍵值對rehash 到ht[1]中，這是因?yàn)閿?shù)據(jù)量比較小。在實(shí)際開發(fā)過程中，這個(gè)rehash 操作并不是一次性、集中式完成的，而是分多次、漸進(jìn)式地完成的。

　　　　漸進(jìn)式rehash 的詳細(xì)步驟：

　　　　　　1、為ht[1] 分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表

　　　　　　2、在幾點(diǎn)鐘維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash 開始

　　　　　　3、在rehash 進(jìn)行期間，每次對字典執(zhí)行CRUD操作時(shí)，程序除了執(zhí)行指定的操作以外，還會(huì)將ht[0]中的數(shù)據(jù)rehash 到ht[1]表中，并且將rehashidx加一

　　　　　　4、當(dāng)ht[0]中所有數(shù)據(jù)轉(zhuǎn)移到ht[1]中時(shí)，將rehashidx 設(shè)置成-1，表示rehash 結(jié)束

　　　　采用漸進(jìn)式rehash 的好處在于它采取分而治之的方式，避免了集中式rehash 帶來的龐大計(jì)算量。

5、跳躍表

　　5.1 概述

　　　　跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。跳躍表是一種隨機(jī)化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在對數(shù)期望時(shí)間下完成，并且比起平衡樹來說，跳躍表的實(shí)現(xiàn)要簡單直觀得多。

　　　　Redis 只在兩個(gè)地方用到了跳躍表，一個(gè)是實(shí)現(xiàn)有序集合鍵，另外一個(gè)是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

　　5.2 跳躍表的定義

 　　　　我們先來看一下一整個(gè)跳躍表的完整結(jié)構(gòu)：

　　　　 Redis 的跳躍表 主要由兩部分組成：zskiplist（鏈表）和zskiplistNode （節(jié)點(diǎn)）

　　　5.2.1 zskiplistNode（節(jié)點(diǎn)） 數(shù)據(jù)結(jié)構(gòu)：

typedef struct zskiplistNode{
　　　//層
     struct zskiplistLevel{
　　　　　//前進(jìn)指針
        struct zskiplistNode *forward;
　　　　//跨度
        unsigned int span;
    } level[];
　　//后退指針
    struct zskiplistNode *backward;
　　//分值
    double score;
　　//成員對象
    robj *obj;
}

　　　　1、層：level 數(shù)組可以包含多個(gè)元素，每個(gè)元素都包含一個(gè)指向其他節(jié)點(diǎn)的指針。

　　　　2、前進(jìn)指針：用于指向表尾方向的前進(jìn)指針

　　　　3、跨度：用于記錄兩個(gè)節(jié)點(diǎn)之間的距離

　　　　4、后退指針：用于從表尾向表頭方向訪問節(jié)點(diǎn)

　　　　5、分值和成員：跳躍表中的所有節(jié)點(diǎn)都按分值從小到大排序。成員對象指向一個(gè)字符串，這個(gè)字符串對象保存著一個(gè)SDS值

　　　5.2. zskiplist 數(shù)據(jù)結(jié)構(gòu)：

typedef struct zskiplist {
     //表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
     structz skiplistNode *header,*tail;
     //表中節(jié)點(diǎn)數(shù)量
     unsigned long length;
     //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
     int level;

}zskiplist;

　　　　 從結(jié)構(gòu)圖中我們可以清晰的看到，header，tail分別指向跳躍表的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)。level 用于記錄最大的層數(shù)，length 用于記錄我們的節(jié)點(diǎn)數(shù)量。

　　5.3 總結(jié)

• 　跳躍表是有序集合的底層實(shí)現(xiàn)之一
  

•    主要有zskiplist 和zskiplistNode兩個(gè)結(jié)構(gòu)組成

•    每個(gè)跳躍表節(jié)點(diǎn)的層高都是1至32之間的隨機(jī)數(shù)

•    在同一個(gè)跳躍表中，多個(gè)節(jié)點(diǎn)可以包含相同的分值，但每個(gè)節(jié)點(diǎn)的對象必須是唯一的

•    節(jié)點(diǎn)按照分值的大小從大到小排序，如果分值相同，則按成員對象大小排序

 6、整數(shù)集合（Intset）

　　6.1 概述

　　　　《Redis 設(shè)計(jì)與實(shí)現(xiàn)》 中這樣定義整數(shù)集合：“整數(shù)集合是集合建的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合中只包含整數(shù)，且這個(gè)集合中的元素?cái)?shù)量不多時(shí)，redis就會(huì)使用整數(shù)集合intset作為集合的底層實(shí)現(xiàn)?！?/p>

 　　　　我們可以這樣理解整數(shù)集合，他其實(shí)就是一個(gè)特殊的集合，里面存儲(chǔ)的數(shù)據(jù)只能夠是整數(shù)，并且數(shù)據(jù)量不能過大。

　　6.2 整數(shù)集合的實(shí)現(xiàn)

typedef struct intset{
    //編碼方式
    uint32_t enconding;
   // 集合包含的元素?cái)?shù)量
    uint32_t length;
    //保存元素的數(shù)組    
    int8_t contents[];

}  

 　 我們觀察一下一個(gè)完成的整數(shù)集合結(jié)構(gòu)圖：

　　　　1、encoding：用于定義整數(shù)集合的編碼方式

　　　　2、length：用于記錄整數(shù)集合中變量的數(shù)量

           3、contents：用于保存元素的數(shù)組，雖然我們在數(shù)據(jù)結(jié)構(gòu)圖中看到，intset將數(shù)組定義為int8_t，但實(shí)際上數(shù)組保存的元素類型取決于encoding

　　6.3 整數(shù)集合的升級(jí)

　　　　在上述數(shù)據(jù)結(jié)構(gòu)圖中我們可以看到，intset 在默認(rèn)情況下會(huì)幫我們設(shè)定整數(shù)集合中的編碼方式，但是當(dāng)我們存入的整數(shù)不符合整數(shù)集合中的編碼格式時(shí)，就需要使用到Redis 中的升級(jí)策略來解決

　　　　Intset 中升級(jí)整數(shù)集合并添加新元素共分為三步進(jìn)行：

　　　　　　1、根據(jù)新元素的類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小，并為新元素分配空間

　　　　　   2、將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成新的編碼格式，重新分配空間

　　　　　　3、將新元素加入到底層數(shù)組中

　　　比如，我們現(xiàn)在有如下的整數(shù)集合：

　　　　我們現(xiàn)在需要插入一個(gè)32位的整數(shù)，這顯然與整數(shù)集合不符合，我們將進(jìn)行編碼格式的轉(zhuǎn)換，并為新元素分配空間：

　　　　第二步，將原有數(shù)據(jù)他們的數(shù)據(jù)類型轉(zhuǎn)換為與新數(shù)據(jù)相同的類型：（重新分配空間后的數(shù)據(jù)）

　　　　第三部，將新數(shù)據(jù)添加到數(shù)組中：

 　　6.3.1 整數(shù)集合升級(jí)的好處

　　　　　　1、提升靈活性

　　　　　　2、節(jié)約內(nèi)存

　　6.4 總結(jié)

　　　　整數(shù)集合是集合建的底層實(shí)現(xiàn)之一

　　　　整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組，這個(gè)數(shù)組以有序，無重復(fù)的范式保存集合元素，在有需要時(shí)，程序會(huì)根據(jù)新添加的元素類型改變這個(gè)數(shù)組的類型

　　　　升級(jí)操作為整數(shù)集合帶來了操作上的靈活性，并且盡可能地節(jié)約了內(nèi)存

　　　　整數(shù)集合只支持升級(jí)操作，不支持降級(jí)操作

7、壓縮列表

　　7.1 概述

　　　　壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只把汗少量列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)，要么就是長度比較短的字符串，那么Redis 就會(huì)使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)。

　　7.2 壓縮列表的構(gòu)成

　　　　一個(gè)壓縮列表的組成如下：

　　　　1、zlbytes:用于記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)

　　　　2、zltail：記錄要列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)

　　　　3、zllen：記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量。

　　　　4、entryX：要說列表包含的各個(gè)節(jié)點(diǎn)

　　　　5、zlend：用于標(biāo)記壓縮列表的末端

　　7.3 總結(jié)

　　　　壓縮列表是一種為了節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)

　　　　壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一

　　　　壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者整數(shù)值

　　　　添加新節(jié)點(diǎn)到壓縮列表，可能會(huì)引發(fā)連鎖更新操作。