redis中的數據結構和編碼：

    背景：

•         1>redis在內部使用redisObject結構體來定義存儲的值對象。
•         2>每種類型都有至少兩種內部編碼，Redis會根據當前值的類型和長度來決定使用哪種編碼實現。
•         3>編碼類型轉換在Redis寫入數據時自動完成，這個轉換過程是不可逆的，轉換規(guī)則只能從小內存編碼向大內存編碼轉換。
  

    源碼：

        值對象redisObject：

            typedef struct redisObject {
                unsigned type:4;                /* 對象類型 */
                unsigned encoding:4;            /* 內部編碼 */
                unsigned lru:LRU_BITS;     /* lru time (relative to server.lruclock) */
                int refcount;                    /* 引用計數器，內存回收機制就是基于該值實現的 */
                void *ptr;                        /* 若要存儲的是整數值則直接存儲數據，否則表示指向數據的指針 */
            } robj;

        類型type：

            說明：查看當前鍵的類型：type key

            #define OBJ_STRING 0     /*字符串對象*/
            #define OBJ_LIST 1        /*列表對象*/
            #define OBJ_SET 2        /*集合對象*/
            #define OBJ_ZSET 3        /*有序集合對象*/
            #define OBJ_HASH 4        /*哈希對象*/

        編碼encoding；

            說明：查看當前鍵的編碼：object encoding key

            #define OBJ_ENCODING_RAW 0             /*Raw representation 簡單動態(tài)字符串*/
            #define OBJ_ENCODING_INT 1             /*Encoded as integer long long類型整數*/
            #define OBJ_ENCODING_HT 2            /* Encoded as hash table 字典*/
            #define OBJ_ENCODING_ZIPMAP 3        /* Encoded as zipmap 壓縮map*/
            #define OBJ_ENCODING_LINKEDLIST 4     /* Encoded as regular linked list 雙端鏈表*/
            #define OBJ_ENCODING_ZIPLIST 5         /* Encoded as ziplist 壓縮列表*/
            #define OBJ_ENCODING_INTSET 6         /* Encoded as intset 整數集合*/
            #define OBJ_ENCODING_SKIPLIST 7     /* Encoded as skiplist 跳躍表*/
            #define OBJ_ENCODING_EMBSTR 8         /* Embedded sds string encoding embstr編碼的簡單動態(tài)字符串*/
            #define OBJ_ENCODING_QUICKLIST 9     /* 基于壓縮列表的雙端列表實現的 快速表*/

        最后被訪問的時間lru：

            概念：記錄對象最后一次被訪問的時間。
            說明：
                1>查看當前鍵的空閑時間(該命令不會更新lru字段)；object idletime key 。可以通過scan + object idletime key 來收集長時間未被訪問的數據，然后手動清理。
                2>當配置了maxmemory和maxmemory-policy=volatile-lru或者allkeys-lru時，若內存超過了上限(maxmemory)后，則優(yōu)先回收長時間沒有被訪問的數據，從而回收內存。

        引用計數器refcount：    

            概念：記錄當前對象被引用的次數，當refcount=0時，可以安全回收當前對象空間。
            說明：獲取當前對象引用：object refcount key

    類型對應的編碼：

        字符串：
            int：存放整形值的字符串。
            embstr：存放字符的短字符串(大小不超過44個字節(jié))。
            raw：存放字符的長字符串(大小不超過44個字節(jié))。
           
            embstr和raw的比較：
                raw調用2次內存分配函數，釋放時當然也需要釋放兩次。
                embstr調用1次內存分配函數，分配一塊連續(xù)的內存，釋放時只需釋放一次。

        列表(list)：

            壓縮列表(ziplist)：
                結構：所有數據都是采用線性連續(xù)的內存結構(大致可類比數組)，目的是為了減少內存的占用，追求空間和時間的平衡。
                    1>以O(1)時間復雜度入隊和出隊。
                    2>讀寫操作涉及復雜的指針移動，最壞時間復雜度為O(n2)，故列表的元素不易太多。
                    3>新增刪除操作涉及內存重新分配，加大了操作的復雜性。

                優(yōu)點：占用內存較少，且占用的是一塊連續(xù)的內存，故加載的速度相對更快一些。
                缺點：當元素的個數較大時，訪問元素的時間較長。

                應用：

                   適合存儲小對象和長度有限(即使O(n2)的復雜度也不會太大)的數據。
                    當元素個數小于list-max-ziplist-entries(默認512) 且 所有元素值的大小都小于list-max-ziplist-value(默認64字節(jié))時，使用ziplist作為列表的內部實現。

            雙端鏈表(linkedlist)：

                優(yōu)點：元素的個數較多時，訪問元素的時間比壓縮列表更快一些。
                缺點：因為是雙向鏈表，故維護了前置指針、后置指針等結構，占用了更多的內存，且內存不是連續(xù)的，容易產生內存碎片。
                說明：當無法滿足ziplist的條件時，使用linkedlist作為列表的內部實現。
                應用：當列表對象元素較多時，壓縮列表就會轉化為更適合存儲大量元素的雙端鏈表。
               
            注意：只能小內存編碼向大內存編碼轉換。(若當元素增刪頻繁時，數據向壓縮編碼轉換是非常消耗CPU的，得不償失)

            快速列表(quicklist)：

                結構：一個雙向鏈表，鏈表的每一個節(jié)點都是一個ziplist，故quicklist結合了雙向鏈表和壓縮列表的優(yōu)點。
                Redis3.2開始，列表采用quicklist進行編碼。

        哈希(hash)：

            壓縮列表(ziplist)：

                應用：當元素個數小于hash-max-ziplist-entries(默認512) 且 所有元素value的大小都小于hash-max-ziplist-value(默認64字節(jié))時，使用ziplist作為哈希的內部實現。

            哈希表(hashtable)：

                優(yōu)點：讀寫時間復雜度O(1)
                缺點：占用內存較多。
                應用：當無法滿足ziplist的條件時，hashtable作為哈希的內部實現。

            hash算法：與傳統(tǒng)hash算法類似，根據key計算得到在哈希表中的位置，采用單鏈表解決沖突，達到加載因子時進行擴展，進而引發(fā)重哈希。

            rehash：采用增量式重哈希：

                概念：在擴容時不會一次性對所有的key進行rehash，而是將key的rehash操作分散延遲到其它操作(哈希表的查找、更新、刪除)中。
                優(yōu)點：避免由于大量的key在同一時間段進行rehash操作導致服務短暫無響應的問題。
                過程：在增量式的rehash過程中，會使用到兩張哈希表：
                    查找：先從老表中查找，再從新表中查找，此外還會對一些key進行rehash操作。
                    新增：新增的鍵值對添加到新表中。

        集合(set)：

            整數集合(intset)：
                結構：有序、不重復的整數集。
                    1>查找時間復雜度為O(logn)
                    2>插入時間復雜度為O(n)
                優(yōu)點：占用的內存遠小于hashtable，
                應用：當元素都是整數 且 元素個數小于set-max-intset-entries(默認512)時，使用intset作為集合的內部實現。

            哈希表(hashtable)：當無法滿足intset的條件時，使用hashtable作為集合的內部實現。

        有序集合(zset)：

            說明：redis給有序集合中的每個元素設置一個分數(score)作為排序的依據。
           
            壓縮列表(ziplist)：
                應用：當元素個數小于zset-max-ziplist-entries(默認128個) 且 每個元素的值都小于zset-max-ziplist-value(默認64字節(jié))時，使用ziplist作為有序集合的內部實現。
               
            跳躍表(skiplist)：
                結構：跳躍表通過在每個節(jié)點中(基于層和跨度等)維持多個指向其它節(jié)點的指針來實現快速訪問。
                    查找時間復雜度平均O(logn)、最壞O(n)。
                應用：當不滿足ziplist條件時，使用skiplist作為內部實現。

    內存優(yōu)化：

        場景：有海量key和value都比較小的數據，在redis中如何存儲才更省內存。
        原理：通過大幅減少key的數量來降低內存的消耗。
        實現：在客戶端通過分組將海量的key根據一定的策略映射到一組hash對象中，由于value較小，故hash類型的對象會使用占用內存較小的ziplist編碼。
            eg：如存在100萬個鍵，可以映射到1000個hash中，每個hash保存1000個元素。

以上就是redis中的數據結構和編碼詳解的詳細內容，更多關于redis中的數據結構和編碼的資料請關注腳本之家其它相關文章！