8 大类型使用的内部存储结构
string  sds
list    quicklist
set     dict
zset    元素及value小于阈值 ziplist  , 否则 zskiplist
hash    元素及value小于阈值 ziplist ,否则 hash
bitmap  sds
hyperloglog    sds
geo     元素及value小于阈值 ziplist  , 否则 zskiplist





redisDb
数据库实例 , 每个 Redis  16 个 redisDb
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;




Dict
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

type      保存 hash 函数及 key/value 赋值、比较函数
ht[2]     存储数据的数组 ,默认使用 0 号数组，如果 0 号哈希表元素过多，则分配一个 2 倍 0 号哈希表大小的空间给 1 号哈希表，然后进行逐步迁移
rehashidx  迁移位置标志



Dictht & DictEntry


typedef struct dictht {
    # 哈希表数组
    dictEntry **table;
    # 哈希表大小
    unsigned long size;
    #哈希表大小掩码 
    unsigned long sizemask;
    # 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;


dictEntry
key   sds 字符串
value 存储各种数据类型的 redisObject




redisObject

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

type  
数据类型 7 种类型
OBJ_STRING 
OBJ_LIST 
OBJ_SET 
OBJ_ZSET     有序集合
OBJ_HASH 
OBJ_MODULE   模块
OBJ_STREAM  消息队列/流


encoding
内部编码方式  10 种编码方式

OBJ_ENCODING_RAW
OBJ_ENCODING_INT
OBJ_ENCODING_HT
OBJ_ENCODING_ZIPLIST
OBJ_ENCODING_ZIPMAP
OBJ_ENCODING_SKIPLIST
OBJ_ENCODING_EMBSTR
OBJ_ENCODING_QUICKLIST
OBJ_ENCODING_STREAM
OBJ_ENCODING_INTSET

LRU  
LRU 时间 或 LFU 频率 或时间

refcount  
引用计数 ， 计数为 0 表明该对象没有被使用，会被释放，回收内存


ptr  指向存储数据的指针




sds  simple dynamic string
sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64
根据实际长度，选择不同的数据结构


struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};


除了 sdshdr5 之外，其他的几个数据结构都包含 4 个字段：
len    字符串长度
alloc  给字符串分配的内存大小
flags  当前字节数组的属性
buf    字符串值和结束符 \0



sds 三种编码方式  INT RAW EMBSTR

INT  ptr 直接指向具体的数据

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}
字符串长度小于等于 44  ， 使用 embstr  否则  RAW

object encoding xxx
embstr
raw
embstr 专门用于保存短字符串
raw编码    调用两次内存分配函数分别创建 redisObject 和 sdshdr 
embstr编码 调用一次内存分配函数分配一块连续的空间，空间中依次包含redisObject和sdshdr 


sds 主要作为字符串的内部数据结构，同时也是 hyperloglog、bitmap 类型的内部数据结构




ziplist（压缩列表）
节约内存，减少内存碎片
连续的内存空间


ziplist 包含 5 个部分
zlbytes  ziplist占用的总内存
Zltail   尾节点到起始位置的字节数
Zllen    总共包含的节点/内存块数
Entry    各个数据节点 
Zlend    魔数 255，用来标记压缩列表的结束


存储节点 zlentry
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

prevRawLen     前置节点长度
preRawLenSize   
len      当前节点的长度
lensize     
encoding  当前节点编码类型
entryData  当前节点数据


ziplist 连续紧凑存储，没有冗余空间，插入新的元素需要 realloc 扩展内存，
如果占用空间太大，realloc 重新分配内存和拷贝的开销会很大，
所以 ziplist 不适合存储过多元素，也不适合存储过大的字符串


ziplist 是 hash、sorted set 的内部存储结构之一，
hash  元素不超过 512 个 ,且值不超过 64个字节，使用 ziplist 作为内存存储结构，
由参数 hash-max-ziplist-entries  hash-max-ziplist-value 控制

sorted set ，当元素个数不超过 128个并且值不超过 64 字节，使用 ziplist 来存储，
zset-max-ziplist-entries   zset-max-ziplist-value  



quicklist（快速列表）

quicklist   3.2 之后引入，用来替换 linkedlist
linkedlist 每个节点有前后指针，要占用 16 字节，且每个节点独立分配内存，容易导致内存碎片化

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;


quicklist 基于 ziplist 的双向链表,数据分段存储到 ziplist，然后将这些 ziplist 用双向指针连接


quicklist 结构体说明
head tail  分别指向第一个和最后一个 ziplist 节点 
count  总的元素个数
len    ziplist 节点个数
compress    LZF算法的压缩深度


quicklistNode
prev/next 双向指针
ziplist 节点 ，单个 ziplist 节点可以存放多个元素


quicklist 是 list 列表的内部数据结构
头尾读写数据很快，时间复杂度 O(1)
支持从中间任意位置插入或读写元素，但速度较慢，时间复杂度 O(n)


zskiplist（跳跃表）


跳跃表是一种有序数据结构
通过在每个节点维持多个指向其他节点的指针，加速访问
大部分场景，跳跃表的效率和平衡树接近，跳跃表支持平均 O(logN) 和最差 O(n) 复杂度的节点查找，
并且跳跃表的实现比平衡树要简单

使用跳跃表两种场景
sorted set ，如果元素数较多或元素长度较大，使用跳跃表作为内部数据结构。
默认元素数超过 128 或者最大元素的长度超过 64，采用 zskiplist 存储

集群结点中用作内部数据结构

zskiplistNode  zskiplist 
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

跳跃表 zskiplist 结构 
header  头节点
tail    尾节点
length   长度，不包含表头节点的节点数量
level    除表头节点外的所有节点中，层数最大的那个节点的层数

zskiplistNode  
ele    节点元素
score  节点分数 
backward  指向当前节点的前一个节点的指针
level      forwad 前进指针   span 跨度， forward 指向的节点到当前节点的距离