首頁 > 軟體

redis資料結構之壓縮列表

2022-03-21 13:03:54

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

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

壓縮列表是Redis為了節約記憶體而開發的是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮列表可以包含任意多個節點，每個節點可以儲存一個位元組陣列或者一個整數值

ziplist 資料結構：壓縮列表各個組成部分

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

壓縮列表節點的構成：

每個壓縮列表節點可以儲存一個位元組陣列或者一個整數值，其中位元組陣列可以是以下三種長度的其中一種

長度小於等於63位元組的位元組陣列

長度小於等於16383位元組的位元組陣列

長度小於等於4294967295位元組的位元組陣列

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

  • 1:  4位元長介於0至12之間的無符號整數
  • 2：1位元組長的有符號整數
  • 3: 3位元組長的有符號整數
  • 4：int16型別整數
  • 5：int32型別整數
  • 6 : int64型別整數

壓縮列表的資料結構：

壓縮列表是redis為了節約記憶體而開發的，由一系列特殊編碼的連續記憶體塊組成的順序型資料結構。一個壓縮列表可以包含任意多個節點，每個節點儲存一個位元組陣列或者一個整數值。

建立一個空的ziplist：

/*
 * 新建立一個空 ziplist
 * 
 * 複雜度：O(1)
 *
 * 返回值：新建立的 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;
}

壓縮列表包含任意多個壓縮列表節點，每個節點可以儲存一個位元組陣列或者一個整數值。

壓縮列表組成部分：

  • zlbytes：記錄整個壓縮列表佔用的記憶體位元組數
  • zltail：記錄壓縮列表表尾節點距離壓縮列表的起始地址的位元組數
  • entryX：列表節點
  • zlend：用於標記壓縮列表的末端

壓縮列表節點的構成：

  • preivous_entry_length：記錄壓縮列表中前一個節點的長度
  • encoding：記錄節點content屬性儲存資料的型別以及長度
  • content：負責儲存節點的值，值的型別和長度由節點的encoding屬性決定。

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

連鎖更新：

每個節點的preivous_entry_length屬性記錄前一個節點的長度

如果前一個節點長度小於254位元組，preivous_entry_length屬性需要用1位元組長的空間來儲存這個長度值

如果前一個節點長度大於等於254位元組，preivous_entry_length屬性需要用5位元組長的空間來儲存這個長度值

如果前一個節點長度變大，這個節點的preivous_entry_length就要擴充套件，這個節點的擴充套件引起下一個節點的擴充套件，這就是連鎖更新

redis將這種在特殊情況下產生的連續多次空間擴充套件操作稱之為連鎖更新

在新增新節點和刪除節點都可能引發連鎖更新。

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

總結：

壓縮列表是為了節約記憶體而開發的順序型資料結構，它是列表鍵和雜湊鍵的底層實現之一，壓縮列表可以包含多個節點，每個節點可以儲存一個位元組陣列或整數值，新增新節點或刪除節點可能引發連鎖更新操作，這種操作出現機率不高。

到此這篇關於redis資料結構之壓縮列表 的文章就介紹到這了,更多相關redis壓縮列表 內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！


相關文章

  • 德漢姆中學就讀條件 德漢姆中學就讀條件

    <em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011

    2021-06-01 09:32:01

  • 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列

    综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所

    2021-06-01 09:31:42

  • 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！ 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！

    除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让

    2021-06-01 09:31:34

  • IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？ IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？

    目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加

    2021-06-01 09:31:24

  • 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊

    开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的

    2021-06-01 09:30:48

  • iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？ iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？

    不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它

    2021-06-01 09:30:45

IT145.com E-mail:sddin#qq.com