說(shuō)到Redis的數(shù)據(jù)結(jié)構(gòu)枫甲，我們大概會(huì)很快想到Redis的5種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)：字符串(String)装黑、列表(List)、散列(Hash)民傻、集合(Set)胰默、有序集合(Sorted Set)，以及他們的特點(diǎn)和運(yùn)用場(chǎng)景漓踢。不過(guò)它們是Redis對(duì)外暴露的數(shù)據(jù)結(jié)構(gòu)牵署，用于API的操作，而組成它們的底層基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)又是什么呢

• 簡(jiǎn)單動(dòng)態(tài)字符串（SDS）
• 鏈表
• 字典
• 跳躍表
• 整數(shù)集合
• 壓縮列表

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

Redis是用C語(yǔ)言寫的喧半，但是Redis并沒(méi)有使用C的字符串表示（C是字符串是以\0空字符結(jié)尾的字符數(shù)組）奴迅，而是自己構(gòu)建了一種簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string，SDS）的抽象類型挺据，并作為Redis的默認(rèn)字符串表示

在Redis中取具，包含字符串值的鍵值對(duì)底層都是用SDS實(shí)現(xiàn)的

SDS的定義

SDS的結(jié)構(gòu)定義在sds.h文件中，SDS的定義在Redis 3.2版本之后有一些改變扁耐，由一種數(shù)據(jù)結(jié)構(gòu)變成了5種數(shù)據(jù)結(jié)構(gòu)暇检，會(huì)根據(jù)SDS存儲(chǔ)的內(nèi)容長(zhǎng)度來(lái)選擇不同的結(jié)構(gòu)，以達(dá)到節(jié)省內(nèi)存的效果做葵，具體的結(jié)構(gòu)定義占哟，我們看以下代碼

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

// 3.2
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

3.2版本之后榨乎，會(huì)根據(jù)字符串的長(zhǎng)度來(lái)選擇對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}

下面以3.2版本的sdshdr8看一個(gè)示例

在這里插入圖片描述

• len：記錄當(dāng)前已使用的字節(jié)數(shù)（不包括'\0'），獲取SDS長(zhǎng)度的復(fù)雜度為O(1)
• alloc：記錄當(dāng)前字節(jié)數(shù)組總共分配的字節(jié)數(shù)量（不包括'\0'）
• flags：標(biāo)記當(dāng)前字節(jié)數(shù)組的屬性瘫筐，是sdshdr8還是sdshdr16等蜜暑，flags值的定義可以看下面代碼
• buf：字節(jié)數(shù)組，用于保存字符串策肝，包括結(jié)尾空白字符'\0'

// flags值定義
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

上面的字節(jié)數(shù)組的空白處表示未使用空間肛捍，是Redis優(yōu)化的空間策略隐绵，給字符串的操作留有余地，保證安全提高效率

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

C語(yǔ)言使用長(zhǎng)度為N+1的字符數(shù)組來(lái)表示長(zhǎng)度為N的字符串拙毫，字符數(shù)組的最后一個(gè)元素為空字符'\0'依许，但是這種簡(jiǎn)單的字符串表示方法并不能滿足Redis對(duì)于字符串在安全性、效率以及功能方面的要求缀蹄，那么使用SDS峭跳，會(huì)有哪些好處呢

參考于《Redis設(shè)計(jì)與實(shí)現(xiàn)》

常數(shù)復(fù)雜度獲取字符串長(zhǎng)度

C字符串不記錄字符串長(zhǎng)度，獲取長(zhǎng)度必須遍歷整個(gè)字符串缺前，復(fù)雜度為O(N)蛀醉；而SDS結(jié)構(gòu)中本身就有記錄字符串長(zhǎng)度的len屬性，所有復(fù)雜度為O(1)衅码。Redis將獲取字符串長(zhǎng)度所需的復(fù)雜度從O(N)降到了O(1)拯刁，確保獲取字符串長(zhǎng)度的工作不會(huì)成為Redis的性能瓶頸

杜絕緩沖區(qū)溢出，減少修改字符串時(shí)帶來(lái)的內(nèi)存重分配次數(shù)

C字符串不記錄自身的長(zhǎng)度逝段，每次增長(zhǎng)或縮短一個(gè)字符串垛玻，都要對(duì)底層的字符數(shù)組進(jìn)行一次內(nèi)存重分配操作。如果是拼接append操作之前沒(méi)有通過(guò)內(nèi)存重分配來(lái)擴(kuò)展底層數(shù)據(jù)的空間大小惹恃，就會(huì)產(chǎn)生緩存區(qū)溢出夭谤；如果是截?cái)鄑rim操作之后沒(méi)有通過(guò)內(nèi)存重分配來(lái)釋放不再使用的空間，就會(huì)產(chǎn)生內(nèi)存泄漏

而SDS通過(guò)未使用空間解除了字符串長(zhǎng)度和底層數(shù)據(jù)長(zhǎng)度的關(guān)聯(lián)巫糙，3.0版本是用free屬性記錄未使用空間，3.2版本則是alloc屬性記錄總的分配字節(jié)數(shù)量颊乘。通過(guò)未使用空間参淹，SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化的空間分配策略，解決了字符串拼接和截取的空間問(wèn)題

二進(jìn)制安全

C字符串中的字符必須符合某種編碼乏悄，除了字符串的末尾浙值，字符串里面是不能包含空字符的，否則會(huì)被認(rèn)為是字符串結(jié)尾檩小，這些限制了C字符串只能保存文本數(shù)據(jù)开呐，而不能保存像圖片這樣的二進(jìn)制數(shù)據(jù)

而SDS的API都會(huì)以處理二進(jìn)制的方式來(lái)處理存放在buf數(shù)組里的數(shù)據(jù)，不會(huì)對(duì)里面的數(shù)據(jù)做任何的限制规求。SDS使用len屬性的值來(lái)判斷字符串是否結(jié)束筐付，而不是空字符

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

雖然SDS的API是二進(jìn)制安全的，但還是像C字符串一樣以空字符結(jié)尾阻肿，目的是為了讓保存文本數(shù)據(jù)的SDS可以重用一部分C字符串的函數(shù)

C字符串與SDS對(duì)比

鏈表

鏈表是一種比較常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)了丛塌，特點(diǎn)是易于插入和刪除较解、內(nèi)存利用率高畜疾、且可以靈活調(diào)整鏈表長(zhǎng)度，但隨機(jī)訪問(wèn)困難印衔。許多高級(jí)編程語(yǔ)言都內(nèi)置了鏈表的實(shí)現(xiàn)啡捶，但是C語(yǔ)言并沒(méi)有實(shí)現(xiàn)鏈表，所以Redis實(shí)現(xiàn)了自己的鏈表數(shù)據(jù)結(jié)構(gòu)

鏈表在Redis中應(yīng)用的非常廣奸焙，列表（List）的底層實(shí)現(xiàn)就是鏈表瞎暑。此外，Redis的發(fā)布與訂閱忿偷、慢查詢金顿、監(jiān)視器等功能也用到了鏈表

鏈表節(jié)點(diǎn)和鏈表的定義

鏈表上的節(jié)點(diǎn)定義如下，adlist.h/listNode

typedef struct listNode {
    // 前置節(jié)點(diǎn)
    struct listNode *prev;
    // 后置節(jié)點(diǎn)
    struct listNode *next;
    // 節(jié)點(diǎn)值
    void *value;
} listNode;

鏈表的定義如下鲤桥，adlist.h/list

typedef struct list {
    // 鏈表頭節(jié)點(diǎn)
    listNode *head;
    // 鏈表尾節(jié)點(diǎn)
    listNode *tail;
    // 節(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);
    // 鏈表所包含的節(jié)點(diǎn)數(shù)量
    unsigned long len;
} list;

每個(gè)節(jié)點(diǎn)listNode可以通過(guò)prev和next指針?lè)植贾赶蚯耙粋€(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)組成雙端鏈表揍拆，同時(shí)每個(gè)鏈表還會(huì)有一個(gè)list結(jié)構(gòu)為鏈表提供表頭指針head、表尾指針tail茶凳、以及鏈表長(zhǎng)度計(jì)數(shù)器len嫂拴，還有三個(gè)用于實(shí)現(xiàn)多態(tài)鏈表的類型特定函數(shù)

• dup：用于復(fù)制鏈表節(jié)點(diǎn)所保存的值
• free：用于釋放鏈表節(jié)點(diǎn)所保存的值
• match：用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等

鏈表結(jié)構(gòu)圖

在這里插入圖片描述

鏈表特性

• 雙端鏈表：帶有指向前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的指針，獲取這兩個(gè)節(jié)點(diǎn)的復(fù)雜度為O(1)
• 無(wú)環(huán)：表頭節(jié)點(diǎn)的prev和表尾節(jié)點(diǎn)的next都指向NULL贮喧，對(duì)鏈表的訪問(wèn)以NULL結(jié)束
• 鏈表長(zhǎng)度計(jì)數(shù)器：帶有len屬性筒狠，獲取鏈表長(zhǎng)度的復(fù)雜度為O(1)
• 多態(tài)：鏈表節(jié)點(diǎn)使用 void*指針保存節(jié)點(diǎn)值，可以保存不同類型的值

字典

字典箱沦，又稱為符號(hào)表（symbol table）辩恼、關(guān)聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對(duì)（key-value pair）的抽象數(shù)據(jù)結(jié)構(gòu)谓形。字典中的每一個(gè)鍵都是唯一的灶伊，可以通過(guò)鍵查找與之關(guān)聯(lián)的值，并對(duì)其修改或刪除

Redis的鍵值對(duì)存儲(chǔ)就是用字典實(shí)現(xiàn)的寒跳，散列（Hash）的底層實(shí)現(xiàn)之一也是字典

我們直接來(lái)看一下字典是如何定義和實(shí)現(xiàn)的吧

字典的定義實(shí)現(xiàn)

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

哈希表結(jié)構(gòu)定義童太，dict.h/dictht

typedef struct dictht {
    // 哈希表數(shù)組
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩碼米辐，用于計(jì)算索引值，等于size-1
    unsigned long sizemask;
    // 哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;
} dictht;

哈希表是由數(shù)組table組成书释，table中每個(gè)元素都是指向dict.h/dictEntry結(jié)構(gòu)的指針翘贮，哈希表節(jié)點(diǎn)的定義如下

typedef struct dictEntry {
    // 鍵
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
    struct dictEntry *next;
} dictEntry;

其中key是我們的鍵征冷；v是鍵值择膝，可以是一個(gè)指針，也可以是整數(shù)或浮點(diǎn)數(shù)检激；next屬性是指向下一個(gè)哈希表節(jié)點(diǎn)的指針肴捉，可以讓多個(gè)哈希值相同的鍵值對(duì)形成鏈表腹侣，解決鍵沖突問(wèn)題

最后就是我們的字典結(jié)構(gòu)，dict.h/dict

typedef struct dict {
    // 和類型相關(guān)的處理函數(shù)
    dictType *type;
    // 私有數(shù)據(jù)
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引齿穗，當(dāng)rehash不再進(jìn)行時(shí)傲隶，值為-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器數(shù)量
    unsigned long iterators; /* number of iterators currently running */
} dict;

type屬性和privdata屬性是針對(duì)不同類型的鍵值對(duì)，用于創(chuàng)建多類型的字典窃页，type是指向dictType結(jié)構(gòu)的指針跺株，privdata則保存需要傳給類型特定函數(shù)的可選參數(shù)，關(guān)于dictType結(jié)構(gòu)和類型特定函數(shù)可以看下面代碼

typedef struct dictType {
    // 計(jì)算哈希值的行數(shù)
    uint64_t (*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;

dict的ht屬性是兩個(gè)元素的數(shù)組脖卖，包含兩個(gè)dictht哈希表乒省，一般字典只使用ht[0]哈希表，ht[1]哈希表會(huì)在對(duì)ht[0]哈希表進(jìn)行rehash（重哈希）的時(shí)候使用畦木，即當(dāng)哈希表的鍵值對(duì)數(shù)量超過(guò)負(fù)載數(shù)量過(guò)多的時(shí)候袖扛，會(huì)將鍵值對(duì)遷移到ht[1]上

rehashidx也是跟rehash相關(guān)的，rehash的操作不是瞬間完成的十籍，rehashidx記錄著rehash的進(jìn)度蛆封，如果目前沒(méi)有在進(jìn)行rehash，它的值為-1

結(jié)合上面的幾個(gè)結(jié)構(gòu)勾栗，我們來(lái)看一下字典的結(jié)構(gòu)圖（沒(méi)有在進(jìn)行rehash）

在這里插入圖片描述

在這里惨篱，哈希算法和rehash(重新散列)的操作不再詳細(xì)說(shuō)明，有機(jī)會(huì)以后單獨(dú)介紹

當(dāng)一個(gè)新的鍵值對(duì)要添加到字典中時(shí)围俘，會(huì)根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值砸讳，根據(jù)索引值放到對(duì)應(yīng)的哈希表上，即如果索引值為0界牡，則放到ht[0]哈希表上绣夺。當(dāng)有兩個(gè)或多個(gè)的鍵分配到了哈希表數(shù)組上的同一個(gè)索引時(shí)，就發(fā)生了鍵沖突的問(wèn)題欢揖，哈希表使用鏈地址法來(lái)解決，即使用哈希表節(jié)點(diǎn)的next指針奋蔚，將同一個(gè)索引上的多個(gè)節(jié)點(diǎn)連接起來(lái)她混。當(dāng)哈希表的鍵值對(duì)太多或太少，就需要對(duì)哈希表進(jìn)行擴(kuò)展和收縮泊碑，通過(guò)rehash(重新散列)來(lái)執(zhí)行

跳躍表

一個(gè)普通的單鏈表查詢一個(gè)元素的時(shí)間復(fù)雜度為O(N)坤按，即便該單鏈表是有序的。使用跳躍表（SkipList）是來(lái)解決查找問(wèn)題的馒过，它是一種有序的數(shù)據(jù)結(jié)構(gòu)臭脓，不屬于平衡樹結(jié)構(gòu)，也不屬于Hash結(jié)構(gòu)腹忽，它通過(guò)在每個(gè)節(jié)點(diǎn)維持多個(gè)指向其他節(jié)點(diǎn)的指針来累，而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的

跳躍表是有序集合（Sorted Set）的底層實(shí)現(xiàn)之一砚作，如果有序集合包含的元素比較多，或者元素的成員是比較長(zhǎng)的字符串時(shí)嘹锁，Redis會(huì)使用跳躍表做有序集合的底層實(shí)現(xiàn)

跳躍表的定義

跳躍表其實(shí)可以把它理解為多層的鏈表葫录，它有如下的性質(zhì)

• 多層的結(jié)構(gòu)組成，每層是一個(gè)有序的鏈表
• 最底層（level 1）的鏈表包含所有的元素
• 跳躍表的查找次數(shù)近似于層數(shù)领猾，時(shí)間復(fù)雜度為O(logn)米同，插入、刪除也為 O(logn)
• 跳躍表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)(通過(guò)拋硬幣來(lái)決定層數(shù))

那么如何來(lái)理解跳躍表呢摔竿，我們從最底層的包含所有元素的鏈表開(kāi)始面粮，給定如下的鏈表

image

在這里插入圖片描述

在這里插入圖片描述

跳躍表節(jié)點(diǎn)的刪除和添加都是不可預(yù)測(cè)的蓉驹，很難保證跳表的索引是始終均勻的，拋硬幣的方式可以讓大體上是趨于均勻的

假設(shè)我們已經(jīng)有了上述例子的一個(gè)跳躍表了揪利，現(xiàn)在往里面添加一個(gè)元素18态兴，通過(guò)拋硬幣的方式來(lái)決定它會(huì)出現(xiàn)的層數(shù)，是正面就繼續(xù)疟位，反面就停止瞻润，假如我拋了2次硬幣，第一次為正面，第二次為反面

在這里插入圖片描述

跳躍表的實(shí)現(xiàn)

Redis的跳躍表實(shí)現(xiàn)是由redis.h/zskiplistNode和redis.h/zskiplist（3.2版本之后redis.h改為了server.h）兩個(gè)結(jié)構(gòu)定義绍撞，zskiplistNode定義跳躍表的節(jié)點(diǎn)正勒，zskiplist保存跳躍表節(jié)點(diǎn)的相關(guān)信息

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 成員對(duì)象 （robj *obj;）
    sds ele;
    // 分值
    double score;
    // 后退指針
    struct zskiplistNode *backward;
    // 層
    struct zskiplistLevel {
        // 前進(jìn)指針
        struct zskiplistNode *forward;
        // 跨度
        // 跨度實(shí)際上是用來(lái)計(jì)算元素排名(rank)的，在查找某個(gè)節(jié)點(diǎn)的過(guò)程中楚午，將沿途訪過(guò)的所有層的跨度累積起來(lái)昭齐，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳躍表中的排位
        unsigned long span;
    } level[];
} zskiplistNode;

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

zskiplistNode結(jié)構(gòu)

• level數(shù)組（層）：每次創(chuàng)建一個(gè)新的跳表節(jié)點(diǎn)都會(huì)根據(jù)冪次定律計(jì)算出level數(shù)組的大小，也就是次層的高度矾柜，每一層帶有兩個(gè)屬性-前進(jìn)指針和跨度阱驾，前進(jìn)指針用于訪問(wèn)表尾方向的其他指針；跨度用于記錄當(dāng)前節(jié)點(diǎn)與前進(jìn)指針?biāo)腹?jié)點(diǎn)的距離（指向的為NULL怪蔑，闊度為0）
• backward（后退指針）：指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
• score（分值）：用來(lái)排序里覆，如果分值相同看成員變量在字典序大小排序
• obj或ele：成員對(duì)象是一個(gè)指針，指向一個(gè)字符串對(duì)象缆瓣，里面保存著一個(gè)sds喧枷；在跳表中各個(gè)節(jié)點(diǎn)的成員對(duì)象必須唯一，分值可以相同

zskiplist結(jié)構(gòu)

• header弓坞、tail表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
• length表中節(jié)點(diǎn)的數(shù)量
• level表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)

假設(shè)我們現(xiàn)在展示一個(gè)跳躍表隧甚，有四個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的高度分別是2渡冻、1戚扳、4、3

在這里插入圖片描述

在這里插入圖片描述

• 每個(gè)跳躍表節(jié)點(diǎn)的層數(shù)在1-32之間
• 一個(gè)跳躍表中，節(jié)點(diǎn)按照分值大小排序巍举，多個(gè)節(jié)點(diǎn)的分值是可以相同的脆荷，相同時(shí)，節(jié)點(diǎn)按成員對(duì)象大小排序
• 每個(gè)節(jié)點(diǎn)的成員變量必須是唯一的

整數(shù)集合

整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)懊悯，可以保存類型為int16_t简烘、int32_t、int64_t的整數(shù)值定枷，并且保證集合中不會(huì)出現(xiàn)重復(fù)元素
整數(shù)集合是集合（Set）的底層實(shí)現(xiàn)之一，如果一個(gè)集合只包含整數(shù)值元素届氢，且元素?cái)?shù)量不多時(shí)欠窒，會(huì)使用整數(shù)集合作為底層實(shí)現(xiàn)

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

整數(shù)集合的定義為inset.h/inset

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

• contents數(shù)組：整數(shù)集合的每個(gè)元素在數(shù)組中按值的大小從小到大排序，且不包含重復(fù)項(xiàng)
• length記錄整數(shù)集合的元素?cái)?shù)量，即contents數(shù)組長(zhǎng)度
• encoding決定contents數(shù)組的真正類型岖妄，如INTSET_ENC_INT16型将、INTSET_ENC_INT32、INTSET_ENC_INT64

在這里插入圖片描述

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

當(dāng)想要添加一個(gè)新元素到整數(shù)集合中時(shí)荐虐，并且新元素的類型比整數(shù)集合現(xiàn)有的所有元素的類型都要長(zhǎng)七兜，整數(shù)集合需要先進(jìn)行升級(jí)（upgrade），才能將新元素添加到整數(shù)集合里面福扬。每次想整數(shù)集合中添加新元素都有可能會(huì)引起升級(jí)腕铸，每次升級(jí)都需要對(duì)底層數(shù)組已有的所有元素進(jìn)行類型轉(zhuǎn)換
升級(jí)添加新元素：

• 根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小铛碑，并為新元素分配空間
• 把數(shù)組現(xiàn)有的元素都轉(zhuǎn)換成新元素的類型狠裹，并將轉(zhuǎn)換后的元素放到正確的位置，且要保持?jǐn)?shù)組的有序性
• 添加新元素到底層數(shù)組

整數(shù)集合的升級(jí)策略可以提升整數(shù)集合的靈活性汽烦，并盡可能的節(jié)約內(nèi)存

另外涛菠，整數(shù)集合不支持降級(jí)，一旦升級(jí)撇吞，編碼就會(huì)一直保持升級(jí)后的狀態(tài)

壓縮列表

壓縮列表（ziplist）是為了節(jié)約內(nèi)存而設(shè)計(jì)的俗冻，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序性（sequential）數(shù)據(jù)結(jié)構(gòu)，一個(gè)壓縮列表可以包含多個(gè)節(jié)點(diǎn)牍颈，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值
壓縮列表是列表（List）和散列（Hash）的底層實(shí)現(xiàn)之一迄薄，一個(gè)列表只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)是小整數(shù)值或比較短的字符串颂砸，會(huì)使用壓縮列表作為底層實(shí)現(xiàn)（在3.2版本之后是使用quicklist實(shí)現(xiàn)）

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

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

在這里插入圖片描述

各部分組成說(shuō)明如下

• zlbytes：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)，在壓縮列表內(nèi)存重分配人乓，或者計(jì)算zlend的位置時(shí)使用
• zltail：記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)勤篮，通過(guò)該偏移量，可以不用遍歷整個(gè)壓縮列表就可以確定表尾節(jié)點(diǎn)的地址
• zllen：記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量色罚，但該屬性值小于UINT16_MAX（65535）時(shí)碰缔，該值就是壓縮列表的節(jié)點(diǎn)數(shù)量，否則需要遍歷整個(gè)壓縮列表才能計(jì)算出真實(shí)的節(jié)點(diǎn)數(shù)量
• entryX：壓縮列表的節(jié)點(diǎn)
• zlend：特殊值0xFF（十進(jìn)制255）戳护，用于標(biāo)記壓縮列表的末端

壓縮列表節(jié)點(diǎn)的構(gòu)成

每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)字或者一個(gè)整數(shù)值金抡，結(jié)構(gòu)如下

在這里插入圖片描述

• previous_entry_ength：記錄壓縮列表前一個(gè)字節(jié)的長(zhǎng)度
• encoding：節(jié)點(diǎn)的encoding保存的是節(jié)點(diǎn)的content的內(nèi)容類型
• content：content區(qū)域用于保存節(jié)點(diǎn)的內(nèi)容，節(jié)點(diǎn)內(nèi)容類型和長(zhǎng)度由encoding決定

對(duì)象

上面介紹了Redis的主要底層數(shù)據(jù)結(jié)構(gòu)腌且，包括簡(jiǎn)單動(dòng)態(tài)字符串（SDS）梗肝、鏈表、字典铺董、跳躍表巫击、整數(shù)集合、壓縮列表。但是Redis并沒(méi)有直接使用這些數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)建鍵值對(duì)數(shù)據(jù)庫(kù)坝锰，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個(gè)對(duì)象系統(tǒng)粹懒，也就是我們所熟知的可API操作的Redis那些數(shù)據(jù)類型，如字符串(String)顷级、列表(List)凫乖、散列(Hash)、集合(Set)弓颈、有序集合(Sorted Set)

根據(jù)對(duì)象的類型可以判斷一個(gè)對(duì)象是否可以執(zhí)行給定的命令帽芽，也可針對(duì)不同的使用場(chǎng)景，對(duì)象設(shè)置有多種不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)恨豁，從而優(yōu)化對(duì)象在不同場(chǎng)景下的使用效率

參考：《Redis設(shè)計(jì)與實(shí)現(xiàn)》

C/C++Linux服務(wù)器開(kāi)發(fā)/后臺(tái)架構(gòu)師學(xué)習(xí)
Linux服務(wù)器開(kāi)發(fā)/架構(gòu)師面試題嚣镜、學(xué)習(xí)資料、教學(xué)視頻和學(xué)習(xí)路線圖（資料包括C/C++橘蜜，Linux菊匿，golang技術(shù)，Nginx计福，ZeroMQ跌捆，MySQL，Redis象颖，fastdfs佩厚，MongoDB，ZK说订，流媒體抄瓦，CDN，P2P陶冷，K8S钙姊，Docker，TCP/IP埂伦，協(xié)程煞额，DPDK，ffmpeg等）沾谜，免費(fèi)分享有需要的可以自行添加學(xué)習(xí)交流群