本文主要參考redis各類型數(shù)據(jù)存儲分析议慰，Redis-基本數(shù)據(jù)類型與內(nèi)部存儲結(jié)構(gòu)

背景

我們在之前的文章中介紹了Redis主要有五種數(shù)據(jù)結(jié)構(gòu)蝌蹂，分別是String补君、Hash膏燕、List芜飘、Set砰左、Sorted Set茂腥，并且大致說了下各自底層的數(shù)據(jù)結(jié)構(gòu)井联，這一篇就好好學(xué)習(xí)下這五種數(shù)據(jù)結(jié)構(gòu)的存儲。

Redis存儲對象

Redis使用dictEntry對象來存儲一個k-v值，我們來看下dictEntry的三個屬性值

key：redis的key是以SDS（簡單動態(tài)字符串）存儲靴寂。
val：reids的val是以redisObject對象存儲磷蜀，redisObject里面包含多個屬性，最重要的是type和encoding百炬，type表示value對象是何種數(shù)據(jù)類型褐隆，encoding表示不同數(shù)據(jù)類型在redis內(nèi)部的存儲方式。

Redis的內(nèi)存分配器默認(rèn)是jemalloc收壕，可以將內(nèi)存空間劃分為小妓灌，大，巨大三個范圍蜜宪，每個范圍又劃分了許多小的內(nèi)存塊單位，當(dāng)Redis存儲數(shù)據(jù)的時候會選擇最合適的內(nèi)存塊進行存儲祥山。

String

字符串對象的底層可以是int圃验，raw，embstr缝呕。

int：8個字節(jié)的長整數(shù)澳窑，在一定條件下會轉(zhuǎn)化為raw編碼字符串對象。
raw：大于39個字節(jié)的字符串供常，簡單動態(tài)字符串（SDS）摊聋，有點類似于List<String>，長度動態(tài)可變

struct sdshdr {
    // buf 中已占用空間的長度
    int len;
    // buf 中剩余可用空間的長度
    int free;
    // 數(shù)據(jù)空間
    char buf[]; // ’\0’空字符結(jié)尾
};

embstr：小于等于39個字節(jié)的字符串栈暇，在一定條件下也會轉(zhuǎn)化成raw編碼字符串對象麻裁，通過調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間。
String的常用命令的時間復(fù)雜度為O(1)源祈，讀寫一樣快煎源，當(dāng)遇到Incr，decr等操作時會轉(zhuǎn)成數(shù)據(jù)型進行計算香缺。

List

List對象的底層是quicklist手销，由ziplist和linkedlist組成的快速列表，所以list支持兩端插入和彈出图张，lpush锋拖，rpush，lpop祸轮，rpop等命令兽埃。可以獲得指定位置（或范圍）的元素倔撞，可以充當(dāng)數(shù)組讲仰、隊列、棧等。

typedef struct listNode {
    // 前置節(jié)點
   struct listNode *prev;
   // 后置節(jié)點
   struct listNode *next;
   // 節(jié)點的值
   void *value;
} listNode;

typedef struct list {
    // 表頭節(jié)點
   listNode *head;
   // 表尾節(jié)點
   listNode *tail;
   // 節(jié)點值復(fù)制函數(shù)
   void *(*dup)(void *ptr);
   // 節(jié)點值釋放函數(shù)
   void (*free)(void *ptr);
    // 節(jié)點值對比函數(shù)
   int (*match)(void *ptr, void *key);
    // 鏈表所包含的節(jié)點數(shù)量
   unsigned long len;
} list;

linkedlist：結(jié)構(gòu)有點類似java的linkedlist鄙陡，列表在增刪操作時時間復(fù)雜度較低冕房。
ziplist：當(dāng)一個列表鍵只包含少量列表項，且是小整數(shù)值或長度比較短的字符串時趁矾，redis會用ziplist代替linkedlist耙册，可以節(jié)省內(nèi)存空間，但是增刪時復(fù)雜度較高毫捣。
quickList： zipList 和 linkedList 的混合體详拙。它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲蔓同，多個 zipList 之間使用雙向指針串接起來饶辙。因為鏈表的附加空間相對太高，prev 和 next 指針就要占去 16 個字節(jié) (64bit 系統(tǒng)的指針是 8 個字節(jié))斑粱，另外每個節(jié)點的內(nèi)存都是單獨分配弃揽，會加劇內(nèi)存的碎片化，影響內(nèi)存管理效率则北。

Hash

Hash對象底層實現(xiàn)是ziplist或者hashtable矿微，當(dāng)Hash對象滿足hash元素數(shù)量小于512個并且所有鍵值對的鍵和值字符串長度都小于64字節(jié)時會使用ziplist，否則使用hashtable.

hashtable：hashtable有點類似java中hashmap尚揣，當(dāng)產(chǎn)生哈希沖突時使用鏈地址法來解決鍵沖突涌矢。

Set

Set的底層實現(xiàn)是intset或者hashtable

intset：當(dāng)一個集合只含有整數(shù)，并且元素不多時會使用intset存儲快骗，是一個無序set娜庇。

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數(shù)量
    uint32_t length;
    // 保存元素的數(shù)組
    int8_t contents[];
} intset;

Sorted Set

Sorted Set也叫ZSet，底層實現(xiàn)使用ziplist或者skiplist滨巴。

skiplist：跳躍表是很常見的一個提高查詢時間復(fù)雜度的結(jié)構(gòu)思灌，可以將平均時間復(fù)雜度降到logN，譬如在lucene索引中也使用到恭取，當(dāng)ZSet元素數(shù)量比較多或者成員是比較長的字符串時會使用skiplist作為底層實現(xiàn)泰偿。

typedef struct zskiplist {
     // 表頭節(jié)點和表尾節(jié)點
    struct zskiplistNode *header, *tail;
    // 表中節(jié)點的數(shù)量
    unsigned long length;
    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;
 } zskiplist;
typedef struct zskiplistNode {
    // 成員對象
    robj *obj;
    // 分值
    double score;
     // 后退指針
    struct zskiplistNode *backward;
    // 層
    struct zskiplistLevel {
        // 前進指針
        struct zskiplistNode *forward;
         // 跨度---前進指針?biāo)赶蚬?jié)點與當(dāng)前節(jié)點的距離
        unsigned int span;
    } level[];
} zskiplistNode;

Redis(五) -- 數(shù)據(jù)存儲