<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • Redis 原理 - List

    List 數據結構

    1. Redis 3.2 前,使用 壓縮列表zipList 或 雙向鏈表linkedList
      當同時滿足下面兩個條件時,使用zipList存儲數據

      • list保存的每個元素長度小于64字節
      • 列表中數據個數少于512個
    2. Redis 3.2 及之后的底層實現方式: quickList
      quickList 是一個基于 zipList 的雙向鏈表, quickList 的每個節點都是一個 zipList , 結合了雙向鏈表和 zipList 的優點

    雙向鏈表就不多說了,就是基礎的數據結構

    壓縮列表(zipList)

    struct ziplist<T> {
        int32 zlbytes; // 整個壓縮列表占用字節數
        int32 zltail_offset; // 最后一個元素距離壓縮列表起始位置的偏移量,用于快速定位到最后一個節點
        int16 zllength; // 元素個數
        T[] entries; // 元素內容列表,挨個挨個緊湊存儲
        int8 zlend; // 標志壓縮列表的結束,值恒為 0xFF
    }
    
    struct entry {
        int prevlen; // 前一個 entry 的字節長度
        int encoding; // 元素類型編碼
        byte[] content; // 元素內容
    }
    

    ziplist內存布局.png

    • 優勢: 內存連續,高效順序訪問,減少內存碎片.
    • 劣勢: 當數據量過大時,zipList就不那么好用了. 因為為了保證它存儲內容在內存中的連續性,插入的復雜度為O(N),而且如果超出zipList內存大小,還會做重新分配的內存空間,并將內容復制到新的地址. 如果數量大的話,重新分配內存和拷貝內存會消耗大量時間. 所以不適合大型字符串,也不適合存儲量多的元素..

    適用場景: 少量數據, 讀遠大于寫,提供高效的讀取操作

    快速列表(quickList)

    是zipList和linkedList的結合體,是將linkedList按段切分,每一段用zipList來緊湊存儲

    typedef struct quicklist {
        quicklistNode *head; // 指向quicklist的頭節點
        quicklistNode *tail; // 指向quicklist的尾節點
        unsigned long count; // 壓縮列表中總元素數量
        unsigned int len; //鏈表節點的個數 quicklistNode
        int fill : 16; // ziplist大小限定,由list-max-ziplist-size給定
        unsigned int compress : 16; // 節點壓縮深度設置,由list-compress-depth給定
    } quicklist;
    
    typedef struct quicklistNode {
        struct quicklistNode *prev; // 指向上一個ziplist節點
        struct quicklistNode *next; // 指向下一個ziplist節點
        unsigned char *zl; // 數據指針,如果沒有被壓縮,就指向ziplist結構,反之指向quicklistLZF結構
        unsigned int sz; // 指向的ziplist的字節數
        unsigned int count : 16; // 指向的ziplist的元素個數
        unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
        unsigned int container : 2;  // 預留字段,存放數據的方式,1--NONE,2--ziplist
        unsigned int recompress : 1;     // 解壓標記,當查看一個被壓縮的數據時,需要暫時解壓,標記此參數為1,之后再重新進行壓縮
        unsigned int attempted_compress : 1; /* node can't compress; too small */
        unsigned int extra : 10; // 擴展字段
    } quicklistNode;
    
    typedef struct quicklistLZF {
        unsigned int sz; // LZF壓縮后占用的字節數
        char compressed[]; // 柔性數組,存放壓縮后的ziplist字節數組
    } quicklistLZF;
    

    quickList結構圖.png

    在向quicklist添加一個元素的時候,不會像普通的鏈表那樣,直接新建一個鏈表節點。而是會檢查插入位置的 ziplist 是否能容納該元素,如果能夠容納,那么就直接保存到ziplist,如果不能容納,才會新建一個Node節點,并保存到新的 ziplist 中。

    總結

    quickList 結合了 ziplist 和 雙向鏈表的優點, 相當于把 雙向鏈表 拆分為 一段段的 ziplist , 每一段的 ziplist 是連續存儲的, 可以做到高效的順序訪問,有利于減少內存碎片.

    List的常用命令

    • LPUSH key element ... 向列表的左側插入一個或多個元素
    • RPUSH key element ... 向列表的右側插入一個或多個元素
    • LPOP key 移除并返回列表左側的第一個元素
    • RPOP key 移除并返回列表右側的第一個元素
    • LRANGE key start stop 返回索引范圍內的所有元素
    • BLPOP key timeout 移除并返回列表左側的第一個元素,沒有元素時會阻塞等待指定的時間
    • BRPOP key timeout 移除并返回列表右側的第一個元素,沒有元素時會阻塞等待指定的時間
    • 更多的List命令,請查閱 官方文檔
    posted @ 2022-06-28 10:58  Broadm  閱讀(21)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看