Redis的底層數(shù)據(jù)結(jié)構(gòu)有多少種

小編給大家分享一下Redis的底層數(shù)據(jù)結(jié)構(gòu)有多少種，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

1、簡(jiǎn)單動(dòng)態(tài)字符串（SDS）

Redis 雖然是用 C 語(yǔ)言寫的，但Redis沒(méi)有直接使用C語(yǔ)言傳統(tǒng)的字符串表示（以空字符 ‘\0’ 結(jié)尾的字符數(shù)組），二是自己構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string，SDS）的抽象類型，并將 SDS 作為 Redis的默認(rèn)字符串表示。
在Redis里面，C字符串只會(huì)作為字符串字面量（string literal）用在一些無(wú)須對(duì)字符串值進(jìn)行修改的地方，比如打印日志。

SDS 的定義：

struct sdshdr{
     //記錄buf數(shù)組中已使用字節(jié)的數(shù)量
     //等于 SDS 所保存字符串的長(zhǎng)度
     int len;
     
     //記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
     int free;
     
     //字節(jié)數(shù)組，用于保存字符串
     char buf[];
}

① free 屬性的值為 0，表示這個(gè)SDS沒(méi)有分配任何未使用的空間。
② len 屬性的值為 5，表示這個(gè)SDS保存了一個(gè)五字節(jié)長(zhǎng)的字符串。
③ buf 屬性是一個(gè)char 類型的數(shù)組，數(shù)組前五個(gè)字節(jié)分別保存了 ‘R’、‘e’、
‘d’、‘i’、‘s’ 五個(gè)字符，而最后一個(gè)字節(jié)則保存了空字符 ‘\0’ 。

（SDS遵循C字符串以空字符結(jié)尾的慣例，保存空字符的 1 字節(jié)空間不計(jì)算在SDS的 len屬性里面，并且為空字符分配額外的 1 字節(jié)空間，以及添加空字符到字符串末尾等操作，都是由SDS 函數(shù)自動(dòng)完成的，所有這個(gè)空字符對(duì)于SDS的使用者來(lái)說(shuō)是完全透明的。遵循空字符結(jié)尾這一慣例的好處是，SDS可以直接重用C字符串函數(shù)庫(kù)里面的函數(shù)。）

SDS 與 C 字浮串的區(qū)別：

（1）常數(shù)復(fù)雜度獲取字符串長(zhǎng)度
因?yàn)?C 字符串并不記錄自身的長(zhǎng)度信息， 所以為了獲取一個(gè) C 字符串的長(zhǎng)度， 程序必須遍歷整個(gè)字符串， 對(duì)遇到的每個(gè)字符進(jìn)行計(jì)數(shù)， 直到遇到代表字符串結(jié)尾的空字符為止， 這個(gè)操作的復(fù)雜度為 O(N) 。

和 C 字符串不同， 因?yàn)?SDS 在 len 屬性中記錄了 SDS 本身的長(zhǎng)度， 所以獲取一個(gè) SDS 長(zhǎng)度的復(fù)雜度僅為 O(1) 。

（2）杜絕緩沖區(qū)溢出
我們知道在 C 語(yǔ)言中使用 strcat 函數(shù)來(lái)進(jìn)行兩個(gè)字符串的拼接，一旦沒(méi)有分配足夠長(zhǎng)度的內(nèi)存空間，就會(huì)造成緩沖區(qū)溢出。而對(duì)于 SDS 數(shù)據(jù)類型，在進(jìn)行字符修改的時(shí)候，會(huì)首先根據(jù)記錄的 len 屬性檢查內(nèi)存空間是否滿足需求，如果不滿足，會(huì)進(jìn)行相應(yīng)的空間擴(kuò)展，然后在進(jìn)行修改操作，所以不會(huì)出現(xiàn)緩沖區(qū)溢出。

（3）減少修改字符串的內(nèi)存重新分配次數(shù)
C語(yǔ)言由于不記錄字符串的長(zhǎng)度，所以如果要修改字符串，必須要重新分配內(nèi)存（先釋放再申請(qǐng)），因?yàn)槿绻麤](méi)有重新分配，字符串長(zhǎng)度增大時(shí)會(huì)造成內(nèi)存緩沖區(qū)溢出，字符串長(zhǎng)度減小時(shí)會(huì)造成內(nèi)存泄露。

而對(duì)于SDS，由于len屬性和free屬性的存在，對(duì)于修改字符串SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種策略：

1、空間預(yù)分配：對(duì)字符串進(jìn)行空間擴(kuò)展的時(shí)候，擴(kuò)展的內(nèi)存比實(shí)際需要的多，這樣可以減少連續(xù)執(zhí)行字符串增長(zhǎng)操作所需的內(nèi)存重分配次數(shù)。

2、惰性空間釋放：對(duì)字符串進(jìn)行縮短操作時(shí)，程序不立即使用內(nèi)存重新分配來(lái)回收縮短后多余的字節(jié)，而是使用 free 屬性將這些字節(jié)的數(shù)量記錄下來(lái)，等待后續(xù)使用。（當(dāng)然SDS也提供了相應(yīng)的API，當(dāng)我們有需要時(shí)，也可以手動(dòng)釋放這些未使用的空間）。

（4）二進(jìn)制安全
因?yàn)镃字符串以空字符作為字符串結(jié)束的標(biāo)識(shí)，而對(duì)于一些二進(jìn)制文件（如圖片等），內(nèi)容可能包括空字符串，因此C字符串無(wú)法正確存??；而所有 SDS 的API 都是以處理二進(jìn)制的方式來(lái)處理 buf 里面的元素，并且 SDS 不是以空字符串來(lái)判斷是否結(jié)束，而是以 len 屬性表示的長(zhǎng)度來(lái)判斷字符串是否結(jié)束。

（5）兼容部分 C 字符串函數(shù)
雖然 SDS 的 API 都是二進(jìn)制安全的， 但它們一樣遵循 C 字符串以空字符結(jié)尾的慣例： 這些 API 總會(huì)將 SDS 保存的數(shù)據(jù)的末尾設(shè)置為空字符， 并且總會(huì)在為 buf 數(shù)組分配空間時(shí)多分配一個(gè)字節(jié)來(lái)容納這個(gè)空字符， 這是為了讓那些保存文本數(shù)據(jù)的 SDS 可以重用一部分 <string.h> 庫(kù)定義的函數(shù)。

（6）總

2、鏈表

作為一種常用數(shù)據(jù)結(jié)構(gòu)，鏈表內(nèi)置在很多高級(jí)的編程語(yǔ)言里面，因?yàn)镽edis使用的 C 語(yǔ)言并沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)，所以 Redis 構(gòu)建了自己的鏈表結(jié)構(gòu)。

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

typedef struct listNode {

    // 前置節(jié)點(diǎn)
    struct listNode *prev;

    // 后置節(jié)點(diǎn)
    struct listNode *next;

    // 節(jié)點(diǎn)的值
    void *value;

} listNode;

多個(gè) listNode 可以通過(guò) prev 和 next 指針組成雙端鏈表， 如圖 3-1 所示。

雖然僅僅使用多個(gè) listNode 結(jié)構(gòu)就可以組成鏈表， 但使用 adlist.h/list 來(lái)持有鏈表的話， 操作起來(lái)會(huì)更方便：

typedef struct list {

    // 表頭節(jié)點(diǎn)
    listNode *head;

    // 表尾節(jié)點(diǎn)
    listNode *tail;

    // 鏈表所包含的節(jié)點(diǎn)數(shù)量
    unsigned long len;

    // 節(jié)點(diǎn)值復(fù)制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點(diǎn)值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點(diǎn)值對(duì)比函數(shù)
    int (*match)(void *ptr, void *key);

} list;

list 結(jié)構(gòu)為鏈表提供了表頭指針 head 、表尾指針 tail ， 以及鏈表長(zhǎng)度計(jì)數(shù)器 len ， 而 dup 、 free 和 match 成員則是用于實(shí)現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：
① dup 函數(shù)用于復(fù)制鏈表節(jié)點(diǎn)所保存的值；
② free 函數(shù)用于釋放鏈表節(jié)點(diǎn)所保存的值；
③ match 函數(shù)則用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等。

圖 3-2 是由一個(gè) list 結(jié)構(gòu)和三個(gè) listNode 結(jié)構(gòu)組成的鏈表：

Redis 的鏈表實(shí)現(xiàn)的特性可以總結(jié)如下：
① 雙端： 鏈表節(jié)點(diǎn)帶有 prev 和 next 指針， 獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度都是 O(1) 。
② 無(wú)環(huán)： 表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL ， 對(duì)鏈表的訪問(wèn)以 NULL 為終點(diǎn)。
③ 帶表頭指針和表尾指針： 通過(guò) list 結(jié)構(gòu)的 head 指針和 tail 指針， 程序獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 。
④ 帶鏈表長(zhǎng)度計(jì)數(shù)器： 程序使用 list 結(jié)構(gòu)的 len 屬性來(lái)對(duì) list 持有的鏈表節(jié)點(diǎn)進(jìn)行計(jì)數(shù)， 程序獲取鏈表中節(jié)點(diǎn)數(shù)量的復(fù)雜度為 O(1) 。
⑤ 多態(tài)： 鏈表節(jié)點(diǎn)使用 void* 指針來(lái)保存節(jié)點(diǎn)值， 并且可以通過(guò) list 結(jié)構(gòu)的 dup 、 free 、 match 三個(gè)屬性為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)， 所以鏈表可以用于保存各種不同類型的值。

3、字典

字典又稱為符號(hào)表或者關(guān)聯(lián)數(shù)組、或映射（map），是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個(gè)鍵 key 都是唯一的，通過(guò) key 可以對(duì)值來(lái)進(jìn)行查找或修改。C 語(yǔ)言中沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，所以字典依然是 Redis 自己構(gòu)建的。

Redis 的字典使用哈希表作為底層實(shí)現(xiàn)， 一個(gè)哈希表里面可以有多個(gè)哈希表節(jié)點(diǎn)， 而每個(gè)哈希表節(jié)點(diǎn)就保存了字典中的一個(gè)鍵值對(duì)。

哈希表

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

typedef struct dictht {

    // 哈希表數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩碼，用于計(jì)算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;

} dictht;

圖 4-1 展示了一個(gè)大小為 4 的空哈希表 （沒(méi)有包含任何鍵值對(duì)）。

哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用 dictEntry 結(jié)構(gòu)表示， 每個(gè) dictEntry 結(jié)構(gòu)都保存著一個(gè)鍵值對(duì)：

typedef struct dictEntry {

    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
    struct dictEntry *next;

} dictEntry;

key 用來(lái)保存鍵，val 屬性用來(lái)保存值，值可以是一個(gè)指針，也可以是uint64_t 整數(shù)，也可以是 int64_t 整數(shù)。

注意這里還有一個(gè)指向下一個(gè)哈希表節(jié)點(diǎn)的指針，我們知道哈希表最大的問(wèn)題是存在哈希沖突，如何解決哈希沖突，有開(kāi)放地址法和鏈地址法。這里采用的便是鏈地址法，通過(guò) next 這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一起，用來(lái)解決哈希沖突。

（因?yàn)?dictEntry 節(jié)點(diǎn)組成的鏈表沒(méi)有指向鏈表表尾的指針， 所以為了速度考慮， 程序總是將新節(jié)點(diǎn)添加到鏈表的表頭位置（復(fù)雜度為 O(1)）， 排在其他已有節(jié)點(diǎn)的前面。）

字典

Redis 中的字典由 dict.h/dict 結(jié)構(gòu)表示：

typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
    int rehashidx; 
    /* rehashing not in progress if rehashidx == -1 */

} dict;

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

● type 屬性是一個(gè)指向 dictType 結(jié)構(gòu)的指針， 每個(gè) dictType 結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)， Redis 會(huì)為用途不同的字典設(shè)置不同的類型特定函數(shù)。
● 而 privdata 屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。

typedef struct dictType {

    // 計(jì)算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void *key);

    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);

    // 復(fù)制值的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);

    // 對(duì)比鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 銷毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);

    // 銷毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);

} dictType;

ht 屬性是一個(gè)包含兩個(gè)項(xiàng)的數(shù)組， 數(shù)組中的每個(gè)項(xiàng)都是一個(gè) dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會(huì)在對(duì) ht[0] 哈希表進(jìn)行 rehash 時(shí)使用。

除了 ht[1] 之外， 另一個(gè)和 rehash 有關(guān)的屬性就是 rehashidx ： 它記錄了 rehash 目前的進(jìn)度， 如果目前沒(méi)有在進(jìn)行 rehash ， 那么它的值為 -1 。

圖 4-3 展示了一個(gè)普通狀態(tài)下（沒(méi)有進(jìn)行 rehash）的字典：

① 哈希算法：Redis計(jì)算哈希值和索引值方法如下：

# 使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 屬性和哈希值，計(jì)算出索引值
# 根據(jù)情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

②解決哈希沖突：這個(gè)問(wèn)題上面我們介紹了，方法是鏈地址法。通過(guò)字典里面的 *next 指針指向下一個(gè)具有相同索引值的哈希表節(jié)點(diǎn)。

③擴(kuò)容和收縮(rehash)：當(dāng)哈希表保存的鍵值對(duì)太多或者太少時(shí)，就要通過(guò) rerehash(重新散列）來(lái)對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮。具體步驟：

1、為字典的 ht[1] 哈希表分配空間， 這個(gè)哈希表的空間大小取決于要執(zhí)行的操作， 以及 ht[0] 當(dāng)前包含的鍵值對(duì)數(shù)量 （也即是 ht[0].used 屬性的值）
● 如果執(zhí)行的是擴(kuò)展操作， 那么 ht[1] 的大小為第一個(gè)大于等于 ht[0].used * 2n； （也就是每次擴(kuò)展都是根據(jù)原哈希表已使用的空間擴(kuò)大一倍創(chuàng)建另一個(gè)哈希表）
● 如果執(zhí)行的是收縮操作， 每次收縮是根據(jù)已使用空間縮小一倍創(chuàng)建一個(gè)新的哈希表。
2、將保存在 ht[0] 中的所有鍵值對(duì) rehash 到 ht[1] 上面： rehash 指的是重新計(jì)算鍵的哈希值和索引值， 然后將鍵值對(duì)放置到 ht[1] 哈希表的指定位置上。
3、當(dāng) ht[0] 包含的所有鍵值對(duì)都遷移到了 ht[1] 之后 （ht[0] 變?yōu)榭毡恚?釋放 ht[0] ， 將 ht[1] 設(shè)置為 ht[0] ， 并在 ht[1] 新創(chuàng)建一個(gè)空白哈希表， 為下一次 rehash 做準(zhǔn)備。

④觸發(fā)擴(kuò)容與收縮的條件：
1、服務(wù)器目前沒(méi)有執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于1。

2、服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于5。

ps：負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小。

3、另一方面， 當(dāng)哈希表的負(fù)載因子小于 0.1 時(shí)， 程序自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行收縮操作。

⑤漸近式 rehash
什么叫漸進(jìn)式 rehash？也就是說(shuō)擴(kuò)容和收縮操作不是一次性、集中式完成的，而是分多次、漸進(jìn)式完成的。如果保存在Redis中的鍵值對(duì)只有幾個(gè)幾十個(gè)，那么 rehash 操作可以瞬間完成，但是如果鍵值對(duì)有幾百萬(wàn)，幾千萬(wàn)甚至幾億，那么要一次性的進(jìn)行 rehash，勢(shì)必會(huì)造成Redis一段時(shí)間內(nèi)不能進(jìn)行別的操作。所以Redis采用漸進(jìn)式 rehash，這樣在進(jìn)行漸進(jìn)式rehash期間，字典的刪除查找更新等操作可能會(huì)在兩個(gè)哈希表上進(jìn)行，第一個(gè)哈希表沒(méi)有找到，就會(huì)去第二個(gè)哈希表上進(jìn)行查找。但是進(jìn)行增加操作，一定是在新的哈希表上進(jìn)行的。

4、跳躍表

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其它節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。

具有如下性質(zhì)：
1、由很多層結(jié)構(gòu)組成；

2、每一層都是一個(gè)有序的鏈表，排列順序?yàn)橛筛邔拥降讓?，都至少包含兩個(gè)鏈表節(jié)點(diǎn)，分別是前面的head節(jié)點(diǎn)和后面的nil節(jié)點(diǎn)；

3、最底層的鏈表包含了所有的元素；

4、如果一個(gè)元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會(huì)出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）；

5、鏈表中的每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針，一個(gè)指向同一層的下一個(gè)鏈表節(jié)點(diǎn)，另一個(gè)指向下一層的同一個(gè)鏈表節(jié)點(diǎn)；

和鏈表、字典等數(shù)據(jù)結(jié)構(gòu)被廣泛地應(yīng)用在 Redis 內(nèi)部不同， Redis 只在兩個(gè)地方用到了跳躍表， 一個(gè)是實(shí)現(xiàn)有序集合鍵， 另一個(gè)是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)， 除此之外， 跳躍表在 Redis 里面沒(méi)有其他用途。

跳躍表節(jié)點(diǎn)（zskiplistNode）

該結(jié)構(gòu)包含以下屬性：
①層（level）：節(jié)點(diǎn)中用 L1 、 L2 、 L3 等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層， L1 代表第一層， L2 代表第二層，以此類推。每個(gè)層都帶有兩個(gè)屬性：前進(jìn)指針和跨度。前進(jìn)指針用于訪問(wèn)位于表尾方向的其他節(jié)點(diǎn)，而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進(jìn)指針，而那個(gè)數(shù)字就是跨度。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí)，訪問(wèn)會(huì)沿著層的前進(jìn)指針進(jìn)行。
每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候， 程序都根據(jù)冪次定律 （power law，越大的數(shù)出現(xiàn)的概率越?。?隨機(jī)生成一個(gè)介于 1 和 32 之間的值作為 level 數(shù)組的大小， 這個(gè)大小就是層的“高度”。（所以說(shuō)表頭節(jié)點(diǎn)的高度就是32）

②后退（backward）指針：節(jié)點(diǎn)中用 BW 字樣標(biāo)記節(jié)點(diǎn)的后退指針，它指向位于當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。后退指針在程序從表尾向表頭遍歷時(shí)使用。

③分值（score）：各個(gè)節(jié)點(diǎn)中的 1.0 、 2.0 和 3.0 是節(jié)點(diǎn)所保存的分值。在跳躍表中，節(jié)點(diǎn)按各自所保存的分值從小到大排列。

④成員對(duì)象（obj）：各個(gè)節(jié)點(diǎn)中的 o1 、 o2 和 o3 是節(jié)點(diǎn)所保存的成員對(duì)象。

注意表頭節(jié)點(diǎn)和其他節(jié)點(diǎn)的構(gòu)造是一樣的： 表頭節(jié)點(diǎn)也有后退指針、分值和成員對(duì)象， 不過(guò)表頭節(jié)點(diǎn)的這些屬性都不會(huì)被用到， 所以圖中省略了這些部分， 只顯示了表頭節(jié)點(diǎn)的各個(gè)層。

跳躍表（zskiplist）

① header ：指向跳躍表的表頭節(jié)點(diǎn)。
② tail ：指向跳躍表的表尾節(jié)點(diǎn)。
③ level ：記錄目前跳躍表內(nèi)，層數(shù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)（表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi)）。
④ length ：記錄跳躍表的長(zhǎng)度，也即是，跳躍表目前包含節(jié)點(diǎn)的數(shù)量（表頭節(jié)點(diǎn)不計(jì)算在內(nèi)）。

5、整數(shù)集合

整數(shù)集合（intset）是集合鍵的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合只包含整數(shù)值元素，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)，Redis就會(huì)使用集合作為集合鍵的底層實(shí)現(xiàn)。

整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)類型，它可以保存類型為int16_t、int32_t 或者int64_t 的整數(shù)值，并且保證集合中不會(huì)出現(xiàn)重復(fù)元素。

每個(gè) intset.h/intset 結(jié)構(gòu)表示一個(gè)整數(shù)集合：

typedef struct intset {

    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素?cái)?shù)量
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;

整數(shù)集合的每個(gè)元素都是 contents 數(shù)組的一個(gè)數(shù)據(jù)項(xiàng)，它們按照從小到大的順序排列，并且不包含任何重復(fù)項(xiàng)。

length 屬性記錄了 contents 數(shù)組的大小。

需要注意的是雖然 contents 數(shù)組聲明為 int8_t 類型，但是實(shí)際上contents 數(shù)組并不保存任何 int8_t 類型的值，其真正類型有 encoding 來(lái)決定。

① 升級(jí)（encoding int16_t -> int32_t -> int64_t）
當(dāng)我們新增的元素類型比原集合元素類型的長(zhǎng)度要大時(shí)，需要對(duì)整數(shù)集合進(jìn)行升級(jí)，才能將新元素放入整數(shù)集合中。具體步驟：
1、根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組的大小，并為新元素分配空間。
2、將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)成與新元素相同類型的元素，并將轉(zhuǎn)換后的元素放到正確的位置，放置過(guò)程中，維持整個(gè)元素順序都是有序的。
3、將新元素添加到整數(shù)集合中（保證有序）。
升級(jí)能極大地節(jié)省內(nèi)存。

② 降級(jí)
整數(shù)集合不支持降級(jí)操作，一旦對(duì)數(shù)組進(jìn)行了升級(jí)，編碼就會(huì)一直保持升級(jí)后的狀態(tài)。

6、壓縮列表

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

因?yàn)楣ｆI里面包含的所有鍵和值都是小整數(shù)值或者短字符串。

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開(kāi)發(fā)的， 由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。

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

每個(gè)壓縮列表節(jié)點(diǎn)都由 previous_entry_length 、 encoding 、 content 三個(gè)部分組成

① previous_entry_ength：記錄壓縮列表前一個(gè)字節(jié)的長(zhǎng)度。previous_entry_ength 的長(zhǎng)度可能是1個(gè)字節(jié)或者是5個(gè)字節(jié)。如果上一個(gè)節(jié)點(diǎn)的長(zhǎng)度小于254，則該節(jié)點(diǎn)只需要一個(gè)字節(jié)就可以表示前一個(gè)節(jié)點(diǎn)的長(zhǎng)度了。如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度大于等于254，則屬性的第一個(gè)字節(jié)為254，后面用四個(gè)字節(jié)表示當(dāng)前節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的長(zhǎng)度。利用此原理即當(dāng)前節(jié)點(diǎn)位置減去上一個(gè)節(jié)點(diǎn)的長(zhǎng)度即得到上一個(gè)節(jié)點(diǎn)的起始位置，壓縮列表可以從尾部向頭部遍歷。這么做很有效地減少了內(nèi)存的浪費(fèi)。

② encoding：節(jié)點(diǎn)的encoding保存的是節(jié)點(diǎn)的content的內(nèi)容類型以及長(zhǎng)度，encoding類型一共有兩種，一種字節(jié)數(shù)組一種是整數(shù)，encoding區(qū)域長(zhǎng)度為1字節(jié)、2字節(jié)或者5字節(jié)長(zhǎng)。

③ content：content區(qū)域用于保存節(jié)點(diǎn)的內(nèi)容，節(jié)點(diǎn)內(nèi)容類型和長(zhǎng)度由encoding決定。

連鎖更新問(wèn)題
連鎖更新在最壞情況下需要對(duì)壓縮列表執(zhí)行 N 次空間重分配操作， 而每次空間重分配的最壞復(fù)雜度為 O(N) ， 所以連鎖更新的最壞復(fù)雜度為 O(N^2) 。

要注意的是， 盡管連鎖更新的復(fù)雜度較高， 但它真正造成性能問(wèn)題的幾率是很低的

看完了這篇文章，相信你對(duì)“Redis的底層數(shù)據(jù)結(jié)構(gòu)有多少種”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！