// 哈希表（字典）數(shù)據(jù)結(jié)構(gòu)，Redis 的所有鍵值對(duì)都會(huì)存儲(chǔ)在這里。其中包含兩個(gè)哈希表。
typedef struct dict {
    // 哈希表的類型，包括哈希函數(shù)，比較函數(shù)，鍵值的內(nèi)存釋放函數(shù)
    dictType *type;
    // 存儲(chǔ)一些額外的數(shù)據(jù)
    void *privdata;
    // 兩個(gè)哈希表
    dictht ht[2];
    // 哈希表重置下標(biāo)，指定的是哈希數(shù)組的數(shù)組下標(biāo)
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 綁定到哈希表的迭代器個(gè)數(shù)
    int iterators; /* number of iterators currently running */
} dict;

redisObject

redisObject，任何 value 都會(huì)被包裝成一個(gè) redisObject，redisObject 能指定 value 的類型，編碼方式等數(shù)據(jù)屬性。

typedef struct redisObject {
    // 剛剛好32 bits
    // 對(duì)象的類型，字符串/列表/集合/哈希表
    unsigned type:4;
    // 未使用的兩個(gè)位
    unsigned notused:2; /* Not used */
    // 編碼的方式，Redis 為了節(jié)省空間，提供多種方式來(lái)保存一個(gè)數(shù)據(jù)
    // 譬如：“123456789” 會(huì)被存儲(chǔ)為整數(shù)123456789
    unsigned encoding:4;
    // 當(dāng)內(nèi)存緊張，淘汰數(shù)據(jù)的時(shí)候用到
    unsigned lru:22; /* lru time (relative to server.lruclock) */
    // 引用計(jì)數(shù)
    int refcount;
    // 數(shù)據(jù)指針
    void *ptr;
} robj;

zset

zset，是一個(gè)跳表，插入刪除速度非?？?。

typedef struct zset {
    // 哈希表
    dict *dict;
    // 跳表
    zskiplist *zsl;
} zset;

adlist

adlist，普通的雙鏈表。

typedef struct list {
    // 頭指針
    listNode *head;
    // 尾指針
    listNode *tail;
    // 數(shù)據(jù)拷貝函數(shù)指針
    void *(*dup)(void *ptr);
    // 析構(gòu)函數(shù)指針
    void (*free)(void *ptr);
    // 數(shù)據(jù)比較指針
    int (*match)(void *ptr, void *key);
    // 鏈表長(zhǎng)度
    unsigned long len;
} list;

ziplist

ziplist，是一個(gè)壓縮的雙鏈表，實(shí)現(xiàn)了針對(duì) CPU cache 的優(yōu)化。ziplist 實(shí)際上一個(gè)字符串，通過(guò)一系列的算法來(lái)實(shí)現(xiàn)壓縮雙鏈表。

TODO 增加一個(gè)歡快的跳表結(jié)構(gòu)圖。

intset

intset，整數(shù)集合。

typedef struct intset {
    // 每個(gè)整數(shù)的類型
    uint32_t encoding;
    // intset 長(zhǎng)度
    uint32_t length;
    // 整數(shù)數(shù)組
    int8_t contents[];
} intset;

sds

sds，字符串?dāng)?shù)據(jù)結(jié)構(gòu)，因?yàn)榻?jīng)常涉及字符串的操作，Redis 做了特殊的實(shí)現(xiàn)，文檔中將其稱為 Hacking String.

typedef char *sds;

Redis 命令和相關(guān)的數(shù)據(jù)結(jié)構(gòu)

以添加數(shù)據(jù)的一類命令 SET,HSET,LPUSH,SADD,ZADD 為例，分別看看哪個(gè)命令底層用了哪些數(shù)據(jù)結(jié)構(gòu)。

SET 命令底層所使用的即為 sds，或者整型數(shù)據(jù)類型 int,long long 等，或者浮點(diǎn)型 float，double。不同的情況所使用的數(shù)據(jù)類不同，SET 底層所使用的數(shù)據(jù)類型是最為簡(jiǎn)單的。

HSET 命令底層所使用的即為壓縮雙鏈表 ziplist，而非哈希表 dict。LPUSH 命令底層所使用的即為壓縮雙鏈表ziplist。

SADD 命令情況較為特殊，SADD 所面向的是一個(gè)集合（set）。如果往集合總添加的數(shù)據(jù)都是整數(shù)，會(huì)采用整數(shù)集合intset；如果集合中的數(shù)據(jù)有一個(gè)不為整數(shù)，會(huì)采用哈希表 dict。因此，會(huì)一個(gè)特殊的情況，假使前N 個(gè)數(shù)據(jù)都為整數(shù)，第N+1 個(gè)數(shù)據(jù)為非整數(shù)，如字符串，那么數(shù)據(jù)結(jié)構(gòu)會(huì)從 intset 轉(zhuǎn)換為dict。

ZADD 也較為特殊，SADD 所面向的是一個(gè)有序集合（sorted set）。ZADD 底層數(shù)據(jù)結(jié)構(gòu)可以采用跳表 skiplist 和哈希表 dict 的結(jié)合；也可以采用 ziplist。具體選用哪種需要看 server.zset_max_ziplist_entries 和server.zset_max_ziplist_value 兩個(gè)配置變量的設(shè)置。前者摻合 dict 是為了能快速查找某個(gè)成員是否存在于跳表中。有序集一個(gè)較為普遍的應(yīng)用是排行榜。

除了雙鏈表 adlist，我將在接下來(lái)的系列文章中一一講解每一個(gè)數(shù)據(jù)結(jié)構(gòu)，以及選用相應(yīng)數(shù)據(jù)結(jié)構(gòu)的目的。

上一篇：Redis 事務(wù)機(jī)制下一篇：AOF 持久化策略