2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

?

redis對象	redis 數(shù)據(jù)結(jié)構(gòu)
字符串對象	?SDS(簡單動(dòng)態(tài)字符串)
列表對象	?壓縮列表(ziplist) 或 鏈表(linkedlist)
哈希對象	?壓縮列表 或 字典
集合對象	?整數(shù)集合 或 字典
有序集合對象	?壓縮列表 或 跳躍表和字典

?

類型編碼對象

REDIS_STRING	REDIS_ENCODING_INT	使用整數(shù)值實(shí)現(xiàn)的字符串對象。
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用?embstr?編碼的簡單動(dòng)態(tài)字符串實(shí)現(xiàn)的字符串對象。
REDIS_STRING	REDIS_ENCODING_RAW	使用簡單動(dòng)態(tài)字符串實(shí)現(xiàn)的字符串對象。
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用壓縮列表實(shí)現(xiàn)的列表對象。
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用雙端鏈表實(shí)現(xiàn)的列表對象。
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用壓縮列表實(shí)現(xiàn)的哈希對象。
REDIS_HASH	REDIS_ENCODING_HT	使用字典實(shí)現(xiàn)的哈希對象。
REDIS_SET	REDIS_ENCODING_INTSET	使用整數(shù)集合實(shí)現(xiàn)的集合對象。
REDIS_SET	REDIS_ENCODING_HT	使用字典實(shí)現(xiàn)的集合對象。
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用壓縮列表實(shí)現(xiàn)的有序集合對象。
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳躍表和字典實(shí)現(xiàn)的有序集合對象。

?

REDIS_STRING

編碼raw結(jié)構(gòu)

sds字符串?

?

struct sdshdr{

?? ?? //記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量

int len;?

//紀(jì)錄buf未使用字節(jié)的數(shù)量

int free

//存放字符串

char buf[];

};

作用 ： 作為redis 的部分鍵 和 值

REDIS_LIST?

?

列表實(shí)現(xiàn)通過 鏈表和壓縮列表

linkedlist?

?

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

作用 ：鏈表為列表鍵 鏈表節(jié)點(diǎn)為值 ?實(shí)現(xiàn)redis?發(fā)布與訂閱， 慢查詢， 監(jiān)視器， 等等。

?

REDIS_HASH

哈希鍵的實(shí)現(xiàn) 字典 ／壓縮列表

字典的實(shí)現(xiàn)

typedef struct dict {// 類型特定函數(shù)dictType *type;// 私有數(shù)據(jù)void *privdata;// 哈希表 rehash 時(shí)使用ht［1］dictht ht[2];// rehash 索引// 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;

?

哈希表的實(shí)現(xiàn)

typedef struct dictht {// 哈希表數(shù)組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計(jì)算索引值// 總是等于 size - 1unsigned long sizemask;// 該哈希表已有節(jié)點(diǎn)的數(shù)量unsigned long used;} dictht;

哈希表的節(jié)點(diǎn)

typedef struct dictEntry {// 鍵void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表struct dictEntry *next;} dictEntry;

通過鏈表解決沖突問題

負(fù)載因子為0.5 時(shí)擴(kuò)張 小于0.1收縮

?

REDIS_SET ?

通過整數(shù)集合和字典實(shí)現(xiàn)

?

整數(shù)集合結(jié)構(gòu) 只有小整數(shù) 才會(huì)在這里 其余都是在字典中實(shí)現(xiàn)

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

REDIS_ZSET

?

有序集合通過跳躍表和字典實(shí)現(xiàn)或壓縮列表

有序集合的跳躍表和字典實(shí)現(xiàn)

跳躍表的實(shí)現(xiàn)

?

typedef struct zskiplist {// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)struct zskiplistNode *header, *tail;// 表中節(jié)點(diǎn)的數(shù)量unsigned long length;// 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)int level;} zskiplist;

跳躍表的節(jié)點(diǎn)實(shí)現(xiàn)

typedef struct zskiplistNode {// 后退指針struct zskiplistNode *backward;// 分值 double 類型的浮點(diǎn)數(shù)， 跳躍表中的所有節(jié)點(diǎn)都按分值從小到大來排序double score;// 成員對象 指向sds對象 值robj *obj;// 層 層高范圍1－32 第一層level［0］struct zskiplistLevel {// 前進(jìn)指針 指向當(dāng)前層的下一個(gè)節(jié)點(diǎn)struct zskiplistNode *forward;// 跨度 紀(jì)錄與同層下一節(jié)點(diǎn)之間的距離unsigned int span;} level[];} zskiplistNode;

?

有序集合的實(shí)現(xiàn)

typedef struct zset {zskiplist *zsl; // 跳躍表dict *dict; // 字典} zset;

zset?結(jié)構(gòu)中的?dict?字典為有序集合創(chuàng)建了一個(gè)從成員到分值的映射， 字典中的每個(gè)鍵值對都保存了一個(gè)集合元素： 字典的鍵保存了元素的成員， 而字典的值則保存了元素的分值。 通過這個(gè)字典， 程序可以用?O(1)?復(fù)雜度查找給定成員的分值，?ZSCORE?命令就是根據(jù)這一特性實(shí)現(xiàn)的， 而很多其他有序集合命令都在實(shí)現(xiàn)的內(nèi)部用到了這一特性。

為什么有序集合需要同時(shí)使用跳躍表和字典來實(shí)現(xiàn)？

在理論上來說， 有序集合可以單獨(dú)使用字典或者跳躍表的其中一種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)， 但無論單獨(dú)使用字典還是跳躍表， 在性能上對比起同時(shí)使用字典和跳躍表都會(huì)有所降低。

舉個(gè)例子， 如果我們只使用字典來實(shí)現(xiàn)有序集合， 那么雖然以?O(1)?復(fù)雜度查找成員的分值這一特性會(huì)被保留， 但是， 因?yàn)樽值湟詿o序的方式來保存集合元素， 所以每次在執(zhí)行范圍型操作 —— 比如?ZRANK?、?ZRANGE?等命令時(shí)， 程序都需要對字典保存的所有元素進(jìn)行排序， 完成這種排序需要至少?O(N \log N)?時(shí)間復(fù)雜度， 以及額外的?O(N)?內(nèi)存空間 （因?yàn)橐獎(jiǎng)?chuàng)建一個(gè)數(shù)組來保存排序后的元素）。

另一方面， 如果我們只使用跳躍表來實(shí)現(xiàn)有序集合， 那么跳躍表執(zhí)行范圍型操作的所有優(yōu)點(diǎn)都會(huì)被保留， 但因?yàn)闆]有了字典， 所以根據(jù)成員查找分值這一操作的復(fù)雜度將從?O(1)?上升為?O(\log N)?。

因?yàn)橐陨显?#xff0c; 為了讓有序集合的查找和范圍型操作都盡可能快地執(zhí)行， Redis 選擇了同時(shí)使用字典和跳躍表兩種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)有序集合。

參考文獻(xiàn) 《redis設(shè)計(jì)與實(shí)現(xiàn)》

?

轉(zhuǎn)載于:https://my.oschina.net/haloooooo/blog/872961

總結(jié)

以上是生活随笔為你收集整理的redis 数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。