Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是怎樣的

本篇內(nèi)容介紹了“Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是怎樣的”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

整數(shù)集合

當(dāng)一個(gè)集合只包含整數(shù)，且這個(gè)集合的元素不多的時(shí)候，Redis 就會(huì)使用整數(shù)集合 intset 。首先看 intset 的數(shù)據(jù)結(jié)構(gòu)：

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

其實(shí) intset 的數(shù)據(jù)結(jié)構(gòu)比較好理解。一個(gè)數(shù)據(jù)保存元素，length 保存元素的數(shù)量，也就是contents的大小，encoding 用于保存數(shù)據(jù)的編碼方式。

通過代碼我們可以知道，encoding 的編碼類型包括了：

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

實(shí)際上我們可以看出來。 Redis encoding的類型，就是指數(shù)據(jù)的大小。作為一個(gè)內(nèi)存數(shù)據(jù)庫，采用這種設(shè)計(jì)就是為了節(jié)約內(nèi)存。

既然有從小到大的三個(gè)數(shù)據(jù)結(jié)構(gòu)，在插入數(shù)據(jù)的時(shí)候盡可能使用小的數(shù)據(jù)結(jié)構(gòu)來節(jié)約內(nèi)存，如果插入的數(shù)據(jù)大于原有的數(shù)據(jù)結(jié)構(gòu)，就會(huì)觸發(fā)擴(kuò)容。

擴(kuò)容有三個(gè)步驟：

1. 根據(jù)新元素的類型，修改整個(gè)數(shù)組的數(shù)據(jù)類型，并重新分配空間

2. 將原有的的數(shù)據(jù)，裝換為新的數(shù)據(jù)類型，重新放到應(yīng)該在的位置上，且保存順序性

3. 再插入新元素

整數(shù)集合不支持降級(jí)操作，一旦升級(jí)就不能降級(jí)了。

跳躍表

跳躍表是鏈表的一種，是一種利用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。跳表平均支持 O(logN)，最壞O(N)復(fù)雜度的查找。

跳表是由一個(gè)zskiplist 和 多個(gè) zskiplistNode 組成。我們先看看他們的結(jié)構(gòu)：

/* ZSETs use a specialized version of Skiplists *//*
 * 跳躍表節(jié)點(diǎn)
 */

typedef struct zskiplistNode {
    // 成員對(duì)象
    robj *obj;
    // 分值
    double score;
    // 后退指針
    struct zskiplistNode *backward;
    // 層
    struct zskiplistLevel {
        // 前進(jìn)指針
        struct zskiplistNode *forward;
        // 跨度
        unsigned int 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;

所以根據(jù)這個(gè)代碼我們可以畫出如下的結(jié)構(gòu)圖：

其實(shí)跳表就是一個(gè)利用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)，利用 level 作為鏈表的索引。

之前有人問過 Redis 的作者 為什么使用跳躍表，而不是 tree 來構(gòu)建索引？作者的回答是：

1. 省內(nèi)存。

2. 服務(wù)于 ZRANGE 或者 ZREVRANGE 是一個(gè)典型的鏈表場(chǎng)景。時(shí)間復(fù)雜度的表現(xiàn)和平衡樹差不多。

3. 最重要的一點(diǎn)是跳躍表的實(shí)現(xiàn)很簡(jiǎn)單就能達(dá)到 O(logN)的級(jí)別。

壓縮列表

壓縮鏈表 Redis 作者的介紹是，為了盡可能節(jié)約內(nèi)存設(shè)計(jì)出來的雙向鏈表。

對(duì)于一個(gè)壓縮列表代碼里注釋給出的數(shù)據(jù)結(jié)構(gòu)如下：

zlbytes 表示的是整個(gè)壓縮列表使用的內(nèi)存字節(jié)數(shù)

zltail 指定了壓縮列表的尾節(jié)點(diǎn)的偏移量

zllen 是壓縮列表 entry 的數(shù)量

entry 就是 ziplist 的節(jié)點(diǎn)

zlend 標(biāo)記壓縮列表的末端

這個(gè)列表中還有單個(gè)指針：

ZIPLIST_ENTRY_HEAD 列表開始節(jié)點(diǎn)的頭偏移量

ZIPLIST_ENTRY_TAIL 列表結(jié)束節(jié)點(diǎn)的頭偏移量

ZIPLIST_ENTRY_END 列表的尾節(jié)點(diǎn)結(jié)束的偏移量

再看看一個(gè) entry 的結(jié)構(gòu)：

/*
 * 保存 ziplist 節(jié)點(diǎn)信息的結(jié)構(gòu)
 */

typedef struct zlentry {
    // prevrawlen ：前置節(jié)點(diǎn)的長(zhǎng)度
    // prevrawlensize ：編碼 prevrawlen 所需的字節(jié)大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：當(dāng)前節(jié)點(diǎn)值的長(zhǎng)度
    // lensize ：編碼 len 所需的字節(jié)大小  
    unsigned int lensize, len;
    // 當(dāng)前節(jié)點(diǎn) header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 當(dāng)前節(jié)點(diǎn)值所使用的編碼類型
    unsigned char encoding;
    // 指向當(dāng)前節(jié)點(diǎn)的指針
    unsigned char *p;

} zlentry;

依次解釋一下這幾個(gè)參數(shù)。

prevrawlen 前置節(jié)點(diǎn)的長(zhǎng)度，這里多了一個(gè) size，其實(shí)是記錄了 prevrawlen 的尺寸。Redis 為了節(jié)約內(nèi)存并不是直接使用默認(rèn)的 int 的長(zhǎng)度，而是逐漸升級(jí)的。
同理 len 記錄的是當(dāng)前節(jié)點(diǎn)的長(zhǎng)度，lensize 記錄的是 len 的長(zhǎng)度。
headersize 就是前文提到的兩個(gè) size 之和。
encoding 就是這個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型。這里注意一下 encoding 的類型只包括整數(shù)和字符串。
p 節(jié)點(diǎn)的指針，不用過多的解釋。

需要注意一點(diǎn)，因?yàn)槊總€(gè)節(jié)點(diǎn)都保存了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，如果發(fā)生了更新或者刪除節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)之后的數(shù)據(jù)也需要修改，有一種最壞的情況就是如果每個(gè)節(jié)點(diǎn)都處于需要擴(kuò)容的零界點(diǎn)，就會(huì)造成這個(gè)節(jié)點(diǎn)之后的節(jié)點(diǎn)都要修改 size 這個(gè)參數(shù)，引發(fā)連鎖反應(yīng)。這個(gè)時(shí)候就是 壓縮鏈表最壞的時(shí)間復(fù)雜度 O(n^2)。不過所有節(jié)點(diǎn)都處于臨界值，這樣的概率可以說比較小。

“Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是怎樣的”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！