快捷導(dǎo)航

redis數(shù)據(jù)結(jié)構(gòu)之壓縮列表

更新時(shí)間：2022年03月21日 09:25:37 作者：周杰倫本人

這篇文章主要介紹了redis數(shù)據(jù)結(jié)構(gòu)之壓縮列表，壓縮列表是列表list和hash數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)之一，是redis為了節(jié)約內(nèi)存而開發(fā)的，由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，下面詳細(xì)內(nèi)容需要的小伙伴可以參考一下

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

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

壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值

ziplist 數(shù)據(jù)結(jié)構(gòu)：壓縮列表各個(gè)組成部分

壓縮列表各個(gè)組成部分詳細(xì)說明：

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

每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值，其中字節(jié)數(shù)組可以是以下三種長(zhǎng)度的其中一種

長(zhǎng)度小于等于63字節(jié)的字節(jié)數(shù)組

長(zhǎng)度小于等于16383字節(jié)的字節(jié)數(shù)組

長(zhǎng)度小于等于4294967295字節(jié)的字節(jié)數(shù)組

數(shù)值則可以是以下六種長(zhǎng)度的其中一種：

1: 4位長(zhǎng)介于0至12之間的無(wú)符號(hào)整數(shù)
2：1字節(jié)長(zhǎng)的有符號(hào)整數(shù)
3: 3字節(jié)長(zhǎng)的有符號(hào)整數(shù)
4：int16類型整數(shù)
5：int32類型整數(shù)
6 : int64類型整數(shù)

壓縮列表的數(shù)據(jù)結(jié)構(gòu)：

壓縮列表是redis為了節(jié)約內(nèi)存而開發(fā)的，由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

創(chuàng)建一個(gè)空的ziplist：

/*
?* 新創(chuàng)建一個(gè)空 ziplist
?*?
?* 復(fù)雜度：O(1)
?*
?* 返回值：新創(chuàng)建的 ziplist
?*/
unsigned char *ziplistNew(void) {
? ? // 分配 2 個(gè) 32 bit，一個(gè) 16 bit，以及一個(gè) 8 bit
? ? // 分別用于 <zlbytes><zltail><zllen> 和 <zlend>
? ? unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
? ? unsigned char *zl = zmalloc(bytes);

? ? // 設(shè)置長(zhǎng)度
? ? ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);

? ? // 設(shè)置表尾偏移量
? ? ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);

? ? // 設(shè)置列表項(xiàng)數(shù)量
? ? ZIPLIST_LENGTH(zl) = 0;

? ? // 設(shè)置表尾標(biāo)識(shí)
? ? zl[bytes-1] = ZIP_END;

? ? return zl;
}

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

壓縮列表組成部分：

zlbytes：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)
zltail：記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址的字節(jié)數(shù)
entryX：列表節(jié)點(diǎn)
zlend：用于標(biāo)記壓縮列表的末端

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

preivous_entry_length：記錄壓縮列表中前一個(gè)節(jié)點(diǎn)的長(zhǎng)度
encoding：記錄節(jié)點(diǎn)content屬性保存數(shù)據(jù)的類型以及長(zhǎng)度
content：負(fù)責(zé)保存節(jié)點(diǎn)的值，值的類型和長(zhǎng)度由節(jié)點(diǎn)的encoding屬性決定。

當(dāng)我們知道一個(gè)指向某個(gè)節(jié)點(diǎn)起始地址的指針，那么通過這個(gè)指針以及這個(gè)節(jié)點(diǎn)的preivous_entry_length屬性，我們可以一直向前一個(gè)節(jié)點(diǎn)回溯，最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)。

連鎖更新：

每個(gè)節(jié)點(diǎn)的preivous_entry_length屬性記錄前一個(gè)節(jié)點(diǎn)的長(zhǎng)度

如果前一個(gè)節(jié)點(diǎn)長(zhǎng)度小于254字節(jié)，preivous_entry_length屬性需要用1字節(jié)長(zhǎng)的空間來(lái)保存這個(gè)長(zhǎng)度值

如果前一個(gè)節(jié)點(diǎn)長(zhǎng)度大于等于254字節(jié)，preivous_entry_length屬性需要用5字節(jié)長(zhǎng)的空間來(lái)保存這個(gè)長(zhǎng)度值

如果前一個(gè)節(jié)點(diǎn)長(zhǎng)度變大，這個(gè)節(jié)點(diǎn)的preivous_entry_length就要擴(kuò)展，這個(gè)節(jié)點(diǎn)的擴(kuò)展引起下一個(gè)節(jié)點(diǎn)的擴(kuò)展，這就是連鎖更新

redis將這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為連鎖更新

在添加新節(jié)點(diǎn)和刪除節(jié)點(diǎn)都可能引發(fā)連鎖更新。

連鎖更新最壞情況下需要對(duì)壓縮列表進(jìn)行N次空間重分配操作，每次空間重分配的最壞復(fù)雜度為O(N)，所以連鎖更新的最壞復(fù)雜度為O(N的平方)，平均復(fù)雜度為O(N)

總結(jié)：

壓縮列表是為了節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)，它是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一，壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或整數(shù)值，添加新節(jié)點(diǎn)或刪除節(jié)點(diǎn)可能引發(fā)連鎖更新操作，這種操作出現(xiàn)幾率不高。

到此這篇關(guān)于redis數(shù)據(jù)結(jié)構(gòu)之壓縮列表的文章就介紹到這了,更多相關(guān)redis壓縮列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: