壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數，要么就是長度比較短的字符串，redis就會使用壓縮列表來做列表鍵的底層實現

當一個哈希鍵只包含少量鍵值對，并且每個鍵值對的鍵和值要么就是小整數值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做哈希鍵的底層實現。

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

ziplist 數據結構：壓縮列表各個組成部分

壓縮列表各個組成部分詳細說明：

壓縮列表節(jié)點的構成：

每個壓縮列表節(jié)點可以保存一個字節(jié)數組或者一個整數值，其中字節(jié)數組可以是以下三種長度的其中一種

長度小于等于63字節(jié)的字節(jié)數組

長度小于等于16383字節(jié)的字節(jié)數組

長度小于等于4294967295字節(jié)的字節(jié)數組

數值則可以是以下六種長度的其中一種：

• 1:  4位長介于0至12之間的無符號整數
• 2：1字節(jié)長的有符號整數
• 3: 3字節(jié)長的有符號整數
• 4：int16類型整數
• 5：int32類型整數
• 6 : int64類型整數

壓縮列表的數據結構：

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

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

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

? ? // 設置長度
? ? ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);

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

? ? // 設置列表項數量
? ? ZIPLIST_LENGTH(zl) = 0;

? ? // 設置表尾標識
? ? zl[bytes-1] = ZIP_END;

? ? return zl;
}

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

壓縮列表組成部分：

• zlbytes：記錄整個壓縮列表占用的內存字節(jié)數
• zltail：記錄壓縮列表表尾節(jié)點距離壓縮列表的起始地址的字節(jié)數
• entryX：列表節(jié)點
• zlend：用于標記壓縮列表的末端

壓縮列表節(jié)點的構成：

• preivous_entry_length：記錄壓縮列表中前一個節(jié)點的長度
• encoding：記錄節(jié)點content屬性保存數據的類型以及長度
• content：負責保存節(jié)點的值，值的類型和長度由節(jié)點的encoding屬性決定。

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

連鎖更新：

每個節(jié)點的preivous_entry_length屬性記錄前一個節(jié)點的長度

如果前一個節(jié)點長度小于254字節(jié)，preivous_entry_length屬性需要用1字節(jié)長的空間來保存這個長度值

如果前一個節(jié)點長度大于等于254字節(jié)，preivous_entry_length屬性需要用5字節(jié)長的空間來保存這個長度值

如果前一個節(jié)點長度變大，這個節(jié)點的preivous_entry_length就要擴展，這個節(jié)點的擴展引起下一個節(jié)點的擴展，這就是連鎖更新

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

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

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

總結：

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

到此這篇關于redis數據結構之壓縮列表 的文章就介紹到這了,更多相關redis壓縮列表 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論