Redis兩種結(jié)構(gòu) listpack 和 quicklist

按照順序，本來應(yīng)該先介紹 quicklist 的結(jié)構(gòu)，quicklist 在 7.0 之前的版本是由雙向鏈表和壓縮列表構(gòu)成的，但是在 7.0 版本已經(jīng)變成了由雙向鏈表和 listpack 實現(xiàn)，所以在這里我們先介紹一下 listpack 的結(jié)構(gòu)。

1、listpack

listpack 是替換 ziplist 的數(shù)據(jù)結(jié)構(gòu)，所以在結(jié)構(gòu)上兩者是有些相似的，listpack 的結(jié)構(gòu)如下：

| 總字節(jié)長度 | entry個數(shù) | entry1 | entry2 | ... | entryN | end |

相比 ziplist，listpack 去除了到尾部節(jié)點，也就是到 entryN 的偏移量，但保留了其他屬性。

對于單個 entry 元素，其結(jié)構(gòu)如下：

| encoding | content | length |

encoding 表示 content 的編碼，endocing 表示實際存儲的內(nèi)容，length 表示該 entry 的長度

避免連鎖更新

使用 listpack 替代 ziplist 的一個好處是避免了連續(xù)更新的問題。

因為 ziplist 的每個元素都有一個屬性用于保存前一個節(jié)點元素的長度，因此前一個節(jié)點修改后會可能需要修改后一個節(jié)點的屬性，但是 listpack 沒有這個關(guān)聯(lián)關(guān)系，從而避免了影響后續(xù)元素的長度，也因此避免了連鎖更新的問題。

獲取最后一個節(jié)點

雖然 listpack 沒有了指向尾部節(jié)點的偏移量，但是同樣可以快速找到 listpack 的尾部節(jié)點，方式是通過 總字節(jié)長度屬性的值，可以直接獲取到 listpack 的尾部，然后根據(jù) entry 元素尾部的 length 屬性，就可以找到尾部 entry 的起始地址了。

2、 quicklist

在 Redis 3.2 版本，列表對象的底層實現(xiàn)變成了由 quicklist 實現(xiàn)，quicklist 實際上是壓縮列表和雙向鏈表的組合結(jié)構(gòu)，因為 quicklist 就是一個鏈表，而鏈表中每一個元素就是壓縮列表。

而在 Redis 7.0 版本，quicklst 變成了由雙向鏈表和 listpack 構(gòu)成的結(jié)構(gòu)。

這里直接介紹 quicklist 由雙向鏈表和 listpack 構(gòu)成的結(jié)構(gòu)。

quicklist 的結(jié)構(gòu)和雙向鏈表的結(jié)構(gòu)類似：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count; 
    unsigned long len; 
    ...
} quicklist;

對于一個 quicklist，它也有指向 quicklist 的頭節(jié)點和尾節(jié)點的指針，如結(jié)構(gòu)中的 head 和 tail。

count 屬性統(tǒng)計每個 quicklist 節(jié)點的 listpack 總數(shù)量的屬性

len 則是統(tǒng)計 quicklist 中 quicklistNode 的數(shù)量的屬性。

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             
    unsigned int count : 16; 
    ...
} quicklistNode;

對于一個 quicklistNode，擁有指向前置節(jié)點和后置節(jié)點的指針，還有指向其下 listpack 的 entry，以及 sz 表示該 listpack 的總字節(jié)長度，count 屬性則表示該 listpack 中包含的元素個數(shù)。

以上就是Redis數(shù)據(jù)結(jié)構(gòu)之listpack和quicklist使用學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)listpack quicklist的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論