說明

說到Redis的數(shù)據(jù)結(jié)構(gòu)，我們大概會很快想到Redis的5種常見數(shù)據(jù)結(jié)構(gòu)：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)，以及他們的特點和運用場景。不過它們是Redis對外暴露的數(shù)據(jù)結(jié)構(gòu)，用于API的操作，而組成它們的底層基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)又是什么呢

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

Redis的GitHub地址https://github.com/antirez/redis

簡單動態(tài)字符串（SDS）

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

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

SDS的定義

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

// 3.0
struct sdshdr {
    // 記錄buf數(shù)組中已使用字節(jié)的數(shù)量，即SDS所保存字符串的長度
    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版本之后，會根據(jù)字符串的長度來選擇對應(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看一個示例

• len：記錄當(dāng)前已使用的字節(jié)數(shù)（不包括'\0'），獲取SDS長度的復(fù)雜度為O(1)
• alloc：記錄當(dāng)前字節(jié)數(shù)組總共分配的字節(jié)數(shù)量（不包括'\0'）
• flags：標記當(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語言使用長度為N+1的字符數(shù)組來表示長度為N的字符串，字符數(shù)組的最后一個元素為空字符'\0'，但是這種簡單的字符串表示方法并不能滿足Redis對于字符串在安全性、效率以及功能方面的要求，那么使用SDS，會有哪些好處呢

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

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

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

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

C字符串不記錄自身的長度，每次增長或縮短一個字符串，都要對底層的字符數(shù)組進行一次內(nèi)存重分配操作。如果是拼接append操作之前沒有通過內(nèi)存重分配來擴展底層數(shù)據(jù)的空間大小，就會產(chǎn)生緩存區(qū)溢出；如果是截斷trim操作之后沒有通過內(nèi)存重分配來釋放不再使用的空間，就會產(chǎn)生內(nèi)存泄漏

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

二進制安全

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

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

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

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

C字符串與SDS對比

鏈表

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

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

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

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

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

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

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

每個節(jié)點listNode可以通過prev和next指針分布指向前一個節(jié)點和后一個節(jié)點組成雙端鏈表，同時每個鏈表還會有一個list結(jié)構(gòu)為鏈表提供表頭指針head、表尾指針tail、以及鏈表長度計數(shù)器len，還有三個用于實現(xiàn)多態(tài)鏈表的類型特定函數(shù)

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

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

鏈表特性

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

字典

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

Redis的鍵值對存儲就是用字典實現(xiàn)的，散列（Hash）的底層實現(xiàn)之一也是字典

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

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

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

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

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

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

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

其中key是我們的鍵；v是鍵值，可以是一個指針，也可以是整數(shù)或浮點數(shù)；next屬性是指向下一個哈希表節(jié)點的指針，可以讓多個哈希值相同的鍵值對形成鏈表，解決鍵沖突問題

最后就是我們的字典結(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不再進行時，值為-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器數(shù)量
    unsigned long iterators; /* number of iterators currently running */
} dict;

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

typedef struct dictType {
    // 計算哈希值的行數(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);
    // 對比鍵的函數(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屬性是兩個元素的數(shù)組，包含兩個dictht哈希表，一般字典只使用ht[0]哈希表，``ht[1]哈希表會在對ht[0]哈希表進行rehash（重哈希）的時候使用，即當(dāng)哈希表的鍵值對數(shù)量超過負載數(shù)量過多的時候，會將鍵值對遷移到ht[1]`上

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

結(jié)合上面的幾個結(jié)構(gòu)，我們來看一下字典的結(jié)構(gòu)圖（沒有在進行rehash）

在這里，哈希算法和rehash(重新散列)的操作不再詳細說明，有機會以后單獨介紹

當(dāng)一個新的鍵值對要添加到字典中時，會根據(jù)鍵值對的鍵計算出哈希值和索引值，根據(jù)索引值放到對應(yīng)的哈希表上，即如果索引值為0，則放到ht[0]哈希表上。當(dāng)有兩個或多個的鍵分配到了哈希表數(shù)組上的同一個索引時，就發(fā)生了鍵沖突的問題，哈希表使用鏈地址法來解決，即使用哈希表節(jié)點的next指針，將同一個索引上的多個節(jié)點連接起來。當(dāng)哈希表的鍵值對太多或太少，就需要對哈希表進行擴展和收縮，通過rehash(重新散列)來執(zhí)行

跳躍表

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

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

跳躍表的定義

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

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

那么如何來理解跳躍表呢，我們從最底層的包含所有元素的鏈表開始，給定如下的鏈表

然后我們每隔一個元素，把它放到上一層的鏈表當(dāng)中，這里我把它叫做上浮（注意，科學(xué)的辦法是拋硬幣的方式，來決定元素是否上浮到上一層鏈表，我這里先簡單每隔一個元素上浮到上一層鏈表，便于理解），操作完成之后的結(jié)構(gòu)如下

查找元素的方法是這樣，從上層開始查找，大數(shù)向右找到頭，小數(shù)向左找到頭，例如我要查找17，查詢的順序是：13 -> 46 -> 22 -> 17；如果是查找35，則是 13 -> 46 -> 22 -> 46 -> 35；如果是54，則是 13 -> 46 -> 54

上面是查找元素，如果是添加元素，是通過拋硬幣的方式來決定該元素會出現(xiàn)到多少層，也就是說它會有 1/2的概率出現(xiàn)第二層、1/4 的概率出現(xiàn)在第三層......

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

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

跳躍表的刪除很簡單，只要先找到要刪除的節(jié)點，然后順藤摸瓜刪除每一層相同的節(jié)點就好了

跳躍表維持結(jié)構(gòu)平衡的成本是比較低的，完全是依靠隨機，相比二叉查找樹，在多次插入刪除后，需要Rebalance來重新調(diào)整結(jié)構(gòu)平衡

跳躍表的實現(xiàn)

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

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

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

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

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

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

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

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

zskiplist的頭結(jié)點不是一個有效的節(jié)點，它有ZSKIPLIST_MAXLEVEL層(32層)，每層的forward指向該層跳躍表的第一個節(jié)點，若沒有則為NULL，在Redis中，上面的跳躍表結(jié)構(gòu)如下

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

整數(shù)集合

整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，可以保存類型為int16_t、int32_t、int64_t的整數(shù)值，并且保證集合中不會出現(xiàn)重復(fù)元素

整數(shù)集合是集合（Set）的底層實現(xiàn)之一，如果一個集合只包含整數(shù)值元素，且元素數(shù)量不多時，會使用整數(shù)集合作為底層實現(xiàn)

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

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

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

• contents數(shù)組：整數(shù)集合的每個元素在數(shù)組中按值的大小從小到大排序，且不包含重復(fù)項
• length記錄整數(shù)集合的元素數(shù)量，即contents數(shù)組長度
• encoding決定contents數(shù)組的真正類型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64

整數(shù)集合的升級

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

升級添加新元素：

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

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

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

壓縮列表

壓縮列表（ziplist）是為了節(jié)約內(nèi)存而設(shè)計的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序性（sequential）數(shù)據(jù)結(jié)構(gòu)，一個壓縮列表可以包含多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值

壓縮列表是列表（List）和散列（Hash）的底層實現(xiàn)之一，一個列表只包含少量列表項，并且每個列表項是小整數(shù)值或比較短的字符串，會使用壓縮列表作為底層實現(xiàn)（在3.2版本之后是使用quicklist實現(xiàn)）

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

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

各部分組成說明如下

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

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

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

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

對象

上面介紹了Redis的主要底層數(shù)據(jù)結(jié)構(gòu)，包括簡單動態(tài)字符串（SDS）、鏈表、字典、跳躍表、整數(shù)集合、壓縮列表。但是Redis并沒有直接使用這些數(shù)據(jù)結(jié)構(gòu)來構(gòu)建鍵值對數(shù)據(jù)庫，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個對象系統(tǒng)，也就是我們所熟知的可API操作的Redis那些數(shù)據(jù)類型，如字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)

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

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