建站
咨詢
售后
建站咨詢
新聞中心
哈嘍，大家好，我是指北君。
創(chuàng)新互聯(lián)專注于洛浦企業(yè)網(wǎng)站建設,響應式網(wǎng)站設計,商城開發(fā)。洛浦網(wǎng)站建設公司,為洛浦等地區(qū)提供建站服務。全流程按需搭建網(wǎng)站，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務
前段時間有朋友面試京東的時候，遇到這樣的面試題。
講講Redis的數(shù)據(jù)類型以及其對應的底層數(shù)據(jù)結構
那么今天指北君帶大家了解一下Redis基本數(shù)據(jù)類型對應的底層數(shù)據(jù)結構。
1. 前言
Redis的鍵值對中的常見數(shù)據(jù)類型有String (字符串)、List(列表)、Hash(哈希)、Set(集合)、Zset(有序集合)。那么其對應的底層數(shù)據(jù)結構有SDS(simple dynamic string)、鏈表、字典、跳躍表、壓縮列表、快速列表，整數(shù)集合等。
下面我們來了解一下其底層數(shù)據(jù)結構的精妙之處。
2. Redis底層數(shù)據(jù)結構
2.1 SDS
Redis自定義了一種簡單動態(tài)字符串(simple dynamic string)，將其作為Redis的默認字符串表示。
其主要結構如下：
- len表示這個SDS字符串長度，如果buff字節(jié)數(shù)組中保存了5個字符那么長度就是5。同時也方便獲取SDS的長度。
- alloc表示分配的字符數(shù)組長度。其值一般是大于SDS字符串長度(len)，由于Redis的設計場景就是會頻繁的訪問，修改數(shù)據(jù)，所以無論是數(shù)據(jù)增大或者是縮小都需要盡量減少重新分配內存的操作。所以SDS會預留一些空間，在下一次修改數(shù)據(jù)的時候可以直接使用原先預分配的內存，同時在每次數(shù)據(jù)操作的時候也會動態(tài)的增加或者減少預留內存空間，。Redis3.0的版本的SDS結構中使用free， 表示未分配的空間，但也是同一個設計思想。
- flags 標志位，低3位表示類型，其余5位未使用。
- buf 實際存儲數(shù)據(jù)的數(shù)組，可以保存字符，也可以保存二進制數(shù)據(jù)。
redis6.0中SDS定義如下 (越來越節(jié)約使用內存了，內存是省出來的!)
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
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[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
相對于C語言的字符串，SDS具有以下優(yōu)點。
- 獲取字符串的長度復雜度更低(常數(shù)復雜度)。
- 更加節(jié)省內存(針對不同長度設置了不同的數(shù)據(jù)類型 sdshdr5、sdshdr8、sdshdr16等。)
- 杜絕緩沖區(qū)溢出。
- 大大減少了修改字符串長度時所需要的內存分配次數(shù)。
- 二進制安全。
2.2 鏈表
鏈表是大家比較熟悉的數(shù)據(jù)結構了，鏈表提供了高效的節(jié)點重排能力，順序訪問，通過增刪節(jié)點調整長度等特點。Redis List對象的底層實現(xiàn)之一就是鏈表。
每一個鏈表節(jié)點使用如下的結構來表示。
/* Node, List, and Iterator are the only data structures used currently. */
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
而多了listNode可以通過prev 和 next 指針組成一個雙端隊列如下圖：
多個節(jié)點可以組成一個鏈表，Redis使用了List結構來持有這些節(jié)點，操作更方便。其結構如下：
typedef struct list {
listNode *head; //鏈表頭節(jié)點指針
listNode *tail; //鏈表尾節(jié)點指針
void *(*dup)(void *ptr); // 用于復制鏈表節(jié)點所保存的值
void (*free)(void *ptr); // 用于釋放鏈表節(jié)點所保存的值
int (*match)(void *ptr, void *key); //用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等
unsigned long len; // 鏈表所包含的節(jié)點數(shù)量
} list;簡單結構如下圖：
Redis鏈表具有如下特性：
- 由于是雙端鏈表，有prev和next指針，獲取節(jié)點的前置節(jié)點和后置節(jié)點的復雜度為O(1)。
- 頭節(jié)點的prev和尾節(jié)點的next均指向NULL，為無環(huán)鏈表，可以以NULL為鏈表訪問終點。
- 鏈表本身提供了指針，可以快速獲取鏈表的表頭節(jié)點和表尾節(jié)點。
- 自帶鏈表長度計數(shù)器，可以快速獲取鏈表長度。
- 鏈表可以保存各種不同類型的值。
2.3 字典
字典是一種用于保存鍵值對的抽象數(shù)據(jù)結構。
在字典中，一個鍵(key)可以和一個值(value)進行關聯(lián)，稱之為鍵值對。字典中每個鍵都是獨一無二的，并且程序都是通過key來操作更新value或者刪除數(shù)據(jù)等。
Redis的字典使用哈希表作為底層實現(xiàn)的， 一個哈希表可以包含多個哈希表節(jié)點，而每個哈希表節(jié)點就保存了字典中的一個鍵值對。
下面再講一下哈希表，哈希表節(jié)點，以及字典的實現(xiàn)。
哈希表及哈希表節(jié)點結構，字典結構 如下：
//字典結構
typedef struct dict {
dictType *type; // 類型特定的函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //長度為2的哈希表數(shù)組， 一般情況下字典僅使用 ht[0]哈希表， ht[1]在rehash的時候會使用到。
long rehashidx; /* 未進行rehash的時候 rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
//哈希表結構
typedef struct dictht {
dictEntry **table; //哈希數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表掩碼，用于計算索引值， 總是等于size-1
unsigned long used; //表示已有節(jié)點數(shù)量
} dictht;
//哈希節(jié)點
typedef struct dictEntry {
void *key; //鍵
union { //value值，包含了多種類型的值，不同類型的值可以使用不同的數(shù)據(jù)結構存儲，節(jié)省內存。
void *val; //其值可以是一個指針
uint64_t u64; //其值也可以是一個uint64_t 整數(shù)
int64_t s64; //其值可以是一個int64_t 整數(shù)
double d; //其值可以是一個double
} v;
struct dictEntry *next; //指向像一個哈希節(jié)點
} dictEntry;
普通狀態(tài)下的字典結構示意圖：
添加新建的機制是大家比較熟悉的思路啦。
使用字典設置的哈希函數(shù)計算key的哈希值，
- 哈希值與sizemask 進行 & 運算，計算出索引值。然后加入到數(shù)組中。
- 如果出現(xiàn)哈希沖突，那么會使用鏈地址法解決沖突，使用next指針指向下一個哈希節(jié)點。
哈希表保存的鍵值逐漸增多或者減少地過程中，程序會對哈希表進行擴展或者收縮，這個過程稱之為rehash。
rehash過程中會使用上面的ht[0] ht[1]，具體過程這里就不詳細說了，會另外專門寫一篇來介紹。
2.4 跳躍表
跳躍表(skiplist )是一種有序數(shù)據(jù)結構，它在每個節(jié)點中維護多個指向其他節(jié)點的指針，從而可以快速訪問。其支持平均O(logN) 復雜度的節(jié)點查找。
Zset使用了跳躍表和字典作為其底層實現(xiàn)。其好處就是可以進行高效的范圍查詢，也可以進行高效的單點查詢。
在源碼中其結構如下：
typedef struct zskiplistNode { //跳躍表節(jié)點 sds ele; //
typedef struct zskiplistNode { //跳躍表節(jié)點
sds ele; //成員對象，各個節(jié)點中成員對象唯一的。
double score; //分值
struct zskiplistNode *backward; //后退指針
struct zskiplistLevel { //層， 最大32層
struct zskiplistNode *forward; //前進指針
unsigned long span; //跨度
} level[];
} zskiplistNode;
typedef struct zskiplist { //跳躍表
struct zskiplistNode *header, *tail;//指向 跳躍表頭 和表尾節(jié)點
unsigned long length; // 節(jié)點數(shù)量
int level; //跳躍表中層數(shù)最大的節(jié)點層數(shù)量
} zskiplist;
typedef struct zset { // zset的數(shù)據(jù)結構使用了 字典dict 和 zskiplist
dict *dict;
zskiplist *zsl;
} zset;關于跳躍表節(jié)點的各參數(shù)解釋如下：
- 層 level：跳躍表節(jié)點的level數(shù)組可以包含多個節(jié)點元素，每個元素都包含指向其他節(jié)點的指針，程序可以通過這些指針來加快訪問其他節(jié)點的速度，層數(shù)越多訪問效率越高。每創(chuàng)建一個新的跳躍表節(jié)點，程序會隨機生成一個1-32之間層數(shù)的值，作為level數(shù)組的大小。表示節(jié)點的高度。
- 前進指針，forward ：每層有一個指向表尾方向的前進指針，可以通過表頭向表尾訪問節(jié)點。
- 跨度 span：記錄兩個節(jié)點之間的距離。
- 后退指針 backward：節(jié)點的后退指針，用于從表尾向表頭訪問節(jié)點，每個節(jié)點只有一個后退指針，所以每次只能后退一個節(jié)點。
- 分值 score：分值是一個浮點數(shù)，跳躍表中的節(jié)點按照分值來排序。
- 成員對象 ele：一個指針，指向一個SDS對象。
下面我們畫一個跳躍表的示意圖：
圖中如果要訪問節(jié)點3，則只需要通過頭節(jié)點第四層的前進指針，就可以找到此節(jié)點。
如果需要增加元素的時候，會先使用高層前進指針去遍歷，并對比score值，然后逐步縮小插入元素的位置范圍，然后確定最終的位置。這樣其平均時間復雜度為O(logN). 相比于鏈表的O(N)的時間復雜度來說，其效率大大提高。只不過其代價就是需要多一點的內存空間。
個人感覺和MySql的索引有點類似。
2.5壓縮列表 ziplist
壓縮列表是 Redis中l(wèi)ist和 hash 對象的底層實現(xiàn)之一。壓縮列表是為了節(jié)約內存而開發(fā)的，是由一系列連續(xù)編碼的內存塊組成。其結構示意如下：
其中各節(jié)點說明如下：
- zlbytes ，4字節(jié)， 記錄壓縮列表占用的內存字節(jié)數(shù)，對壓縮列表僅進行內存重分配，或計算zlend尾節(jié)點位置時使用。
- zltail ，4字節(jié)， 記錄壓縮列表尾節(jié)點距離壓縮列表的起始地址有多少個字節(jié)?？梢钥焖儆嬎愕玫轿补?jié)點的地址。
- zlen， 2字節(jié) ，記錄了壓縮列表包含的節(jié)點數(shù)量。
- entry X 壓縮列表中的節(jié)點，其長度取決于節(jié)點內容
- zlend ， 1字節(jié) ， 特殊值OxFF (255) 標記壓縮列表末端。
其中每一個壓縮列表節(jié)點entry由如下部分組成：
- previous_entry_length 記錄了壓縮列表中前一個節(jié)點的長度，其屬性可以是1或5個字節(jié)。如果前一個節(jié)點的長度小于254，那么其長度就是1字節(jié)，表示前一節(jié)點的長度。如果遷移節(jié)點的長度大于254字節(jié)， 那么其屬性長度則為5個字節(jié)，其中第一個字節(jié)會設置為OxFE(254) , 后面的4個字節(jié)用來表示前一節(jié)點的長度。
- encoding 表示content 屬性保存的數(shù)據(jù)類型以及長度。content保存字節(jié)數(shù)組時，encoding的值為1，2，5字節(jié)， 最高前兩位分別為00，01，10， 最高前兩位后面的其他位數(shù)則記錄content的長度。content保存整數(shù)編碼時，最高2位為11， 其余位記錄整數(shù)類型及。
- content 保存節(jié)點的內容，可以保存字節(jié)數(shù)組或者整數(shù)。
由于previous_entry_length 記錄了前一個節(jié)點的長度，而且其可能為1個字節(jié)或者5個字節(jié)，如果前一個節(jié)點的長度從254之下增加到254之上，那么previous_entry_length 的值就要使用5個字節(jié)類表示。而如果后面的節(jié)點均存在同樣的情況，那么壓縮列表就會出現(xiàn)連鎖更新，導致內存空間重新分配，從而導致壓縮列表增加節(jié)點或者刪除節(jié)點的最壞時間復雜度位O(N2).
新版本的redis中，引入了listpack。其目的是替換ziplist，整體結構類似。
其entry結構如下：
len保存了當前節(jié)點encoding及data的長度綜合，從而可以避免連鎖更新
2.6快速列表
快速列表(quicklist)可以看成是雙向鏈表和壓縮列表的一種組合。Redis3.2之后 list對象使用快速列表作為其底層實現(xiàn)。
快速列表使用了quickListNode節(jié)點組成雙向鏈表，然后在每個快速列表節(jié)點內部使用壓縮列表存儲數(shù)據(jù)，從而可以控制壓縮列表的長度，避免連鎖更新帶來的性能影響。
其中快速列表的源碼結構如下：
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 : QL_FILL_BITS; /* fill factor for individual nodes */
unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
typedef struct quicklistBookmark {
quicklistNode *node;
char *name;
} quicklistBookmark;
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 中維護了一個quicklistBookmark數(shù)組，并且有執(zhí)行qulickListNode 頭尾的指針。
每一個quicklistBookmark 中有一個quickListNode的指針，同時每一個quickListNode又有指向前一個后一個node的指針。
其結構示意圖如下：
2.7 整數(shù)集合
整數(shù)集合(intset) 是集合鍵底層實現(xiàn)之一，當一個集合只包含整數(shù)元素的時候，Redis會使用整數(shù)集合作為集合鍵的實現(xiàn)。
整數(shù)集合的源碼如下：
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;整數(shù)集合底層是一個數(shù)組，如果每一個元素都在16位以內的整數(shù)類型(-32768 到 32767)，則數(shù)組的每個元素都為int16_t ， 如果新加的整數(shù)超過這個范圍，并且在32位以內的話， 整個數(shù)組中的每一個元素都會升級成int32_t 表示的整數(shù)， 如果新加入的是64 位才能表示的整數(shù)的話，所以的元素又會再一次升級。
但是整數(shù)集合不支持降級，及 整數(shù)集合中如果有一個64位的整數(shù)，即使移除此元素，整個集合也不會降級。
這樣做具有一定的靈活性，而且可以節(jié)省內存。當需要升級的時候才進行升級。
總結通過以上 Redis 底層數(shù)據(jù)結構可以看出，其設計核心總是在節(jié)約內內存，提高訪問速度。所以Redis快，這小巧妙的底層設計也是功不可沒。同時我們也可以根據(jù)著些設計思想去優(yōu)化我們自己的代碼，優(yōu)秀的設計總是值得去學習的。
新聞名稱：講講Redis各個數(shù)據(jù)類型的底層數(shù)據(jù)結構
文章源于：http://fisionsoft.com.cn/article/dhjedcj.html
