redis數據結構綜述

這里所說的數據結構是針對 redis 內部存儲 key-value 的，其他諸如 redis 配置相關的數據結構，不在此篇討論范圍。 一覽 redis 數據結構 dict ，哈希表，redis 所有的 key-value 都存儲在里面。 // 哈希表（字典）數據結構，redis 的所有鍵值對都會存儲在這

這里所說的數據結構是針對 redis 內部存儲 key-value 的，其他諸如 redis 配置相關的數據結構，不在此篇討論范圍。

一覽 redis 數據結構

dict，哈希表，redis 所有的 key-value 都存儲在里面。

// 哈希表（字典）數據結構，redis 的所有鍵值對都會存儲在這里。其中包含兩個哈希表。
typedef struct dict {
 // 哈希表的類型，包括哈希函數，比較函數，鍵值的內存釋放函數
 dictType *type;
 // 存儲一些額外的數據
 void *privdata;
 // 兩個哈希表
 dictht ht[2];
 // 哈希表重置下標，指定的是哈希數組的數組下標
 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
 // 綁定到哈希表的迭代器個數
 int iterators; /* number of iterators currently running */
} dict;

redisObject，任何 value 都會被包裝成一個 redisObject，redisObject 能指定 value 的類型，編碼方式等數據屬性。

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

zset，是一個跳表，插入刪除速度非常快。

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

adlist，普通的雙鏈表。

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

ziplist，是一個壓縮的雙鏈表，實現了針對 CPU cache 的優化。ziplist 實際上一個字符串，通過一系列的算法來實現壓縮雙鏈表。

intset，整數集合。

typedef struct intset {
 // 每個整數的類型
 uint32_t encoding;
 // intset 長度
 uint32_t length;
 // 整數數組
 int8_t contents[];
} intset;

sds，字符串數據結構，因為經常涉及字符串的操作，redis 做了特殊的實現，文檔中將其稱為 Hacking String.

typedef char *sds;

zipmap，已經被廢棄，我不會討論這個數據結構。

redis 命令和相關的數據結構

以添加數據的一類命令 SET,HSET,LPUSH,SADD,ZADD 為例，分別看看哪個命令底層用了哪些數據結構。

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

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

LPUSH 命令底層所使用的即為壓縮雙鏈表 ziplist。

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

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

我將在接下來的系列文章中一一講解每一個數據結構，以及選用相應數據結構的目的。

搗亂 2014-6-9

http://daoluan.net

原文地址：redis 數據結構綜述, 感謝原作者分享。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com