一、概述
redis是一個(gè)開源的使用ANSI C語言編寫、遵守BSD協(xié)議、支持網(wǎng)絡(luò)、可基于內(nèi)存亦可持久化的日志型、Key-Value數(shù)據(jù)庫，與Memcached類似，卻優(yōu)于Memcached的一個(gè)高性能的key-value數(shù)據(jù)庫。下面讓我們來詳細(xì)介紹一下redis中五大數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)。
二、簡單動態(tài)字符串
1、概述
Redis是一個(gè)開源的使用ANSI C語言編寫的key-value 數(shù)據(jù)庫，我們可能會較為主觀的認(rèn)為 Redis 中的字符串就是采用了C語言中的傳統(tǒng)字符串表示，但其實(shí)不然，Redis沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis的默認(rèn)字符串表示：redis>SET msg "hello world"
SDS 定義：
struct sdshdr{
//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
//等于 SDS 保存字符串的長度
int len;
//記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
int free;
//字節(jié)數(shù)組，用于保存字符串
char buf[];
}
圖片來源：《Redis設(shè)計(jì)與實(shí)現(xiàn)》
我們看上面對于 SDS 數(shù)據(jù)類型的定義：
- len 保存了SDS保存字符串的長度
- buf[] 數(shù)組用來保存字符串的每個(gè)元素
- free j記錄了 buf 數(shù)組中未使用的字節(jié)數(shù)量
2、與C語言相比較
一般來說，SDS 除了保存數(shù)據(jù)庫中的字符串值以外，SDS 還可以作為緩沖區(qū)（buffer）：包括 AOF 模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的輸入緩沖區(qū)。后面在介紹Redis的持久化時(shí)會進(jìn)行介紹。
三、鏈表
1、概述
鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問方式，并且可以通過增刪節(jié)點(diǎn)來靈活地調(diào)整鏈表的長度。
鏈表在Redis 中的應(yīng)用非常廣泛，比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。當(dāng)一個(gè)列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長的字符串時(shí)，Redis 就會使用鏈表作為列表鍵的底層實(shí)現(xiàn)。
每個(gè)鏈表節(jié)點(diǎn)使用一個(gè)listNode結(jié)構(gòu)表示（adlist.h/listNode）：
typedef struct listNode{
//前置節(jié)點(diǎn)
struct listNode *prev;
//后置節(jié)點(diǎn)
struct listNode *next;
//節(jié)點(diǎn)的值
void *value;
}listNode
鏈表的數(shù)據(jù)結(jié)構(gòu)：
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 (*free) (void *ptr);
//節(jié)點(diǎn)值釋放函數(shù)
void (*free) (void *ptr);
//節(jié)點(diǎn)值對比函數(shù)
int (*match) (void *ptr,void *key);
}list;
組成結(jié)構(gòu)圖
2、Redis鏈表特性
- 雙端：鏈表具有前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的引用，獲取這兩個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度都為O(1)。
- 無環(huán)：表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結(jié)束。
- 帶鏈表長度計(jì)數(shù)器：通過 len 屬性獲取鏈表長度的時(shí)間復(fù)雜度為 O(1)。
- 多態(tài)：鏈表節(jié)點(diǎn)使用 void* 指針來保存節(jié)點(diǎn)值，可以保存各種不同類型的值。
四、字典
1、概述
字典又稱為符號表或者關(guān)聯(lián)數(shù)組、或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個(gè)鍵 key 都是唯一的，通過 key 可以對值來進(jìn)行查找或修改。C 語言中沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，所以字典依然是 Redis自己構(gòu)建的。
哈希表結(jié)構(gòu)定義：
typedef struct dictht{
//哈希表數(shù)組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計(jì)算索引值
//總是等于 size-1
unsigned long sizemask;
//該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
}dictht
哈希表是由數(shù)組 table 組成，table 中每個(gè)元素都是指向 dict.h/dictEntry 結(jié)構(gòu)，dictEntry 結(jié)構(gòu)定義如下：
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
}dictEntry
key 用來保存鍵，val 屬性用來保存值，值可以是一個(gè)指針，也可以是uint64_t整數(shù)，也可以是int64_t整數(shù)。
注意這里還有一個(gè)指向下一個(gè)哈希表節(jié)點(diǎn)的指針，我們知道哈希表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放地址法和鏈地址法。這里采用的便是鏈地址法，通過next這個(gè)指針可以將多個(gè)哈希值相同的鍵值對連接在一起，用來解決哈希沖突。
五、跳躍表
1、概述
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。跳躍表是一種隨機(jī)化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在對數(shù)期望時(shí)間下完成，并且比起平衡樹來說，跳躍表的實(shí)現(xiàn)要簡單直觀得多。
Redis 只在兩個(gè)地方用到了跳躍表，一個(gè)是實(shí)現(xiàn)有序集合鍵，另外一個(gè)是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
Redis中跳躍表節(jié)點(diǎn)定義如下：
typedef struct zskiplistNode {
//層
struct zskiplistLevel{
//前進(jìn)指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
} zskiplistNode
多個(gè)跳躍表節(jié)點(diǎn)構(gòu)成一個(gè)跳躍表：
typedef struct zskiplist{
//表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
structz skiplistNode *header, *tail;
//表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
}zskiplist;
- header和tail指針分別指向跳躍表的表頭和表尾節(jié)點(diǎn)；
- length屬性記錄節(jié)點(diǎn)的數(shù)量；
- level屬性記錄層數(shù)最高的幾點(diǎn)的層數(shù)量；
- 下圖分別展示了完整的跳躍表和單個(gè)節(jié)點(diǎn)的詳細(xì)結(jié)構(gòu)圖：
2、特性
跳表具有如下性質(zhì)：
- 由很多層結(jié)構(gòu)組成
- 每一層都是一個(gè)有序的鏈表
- 最底層(Level 1)的鏈表包含所有元素
- 如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現(xiàn)。
- 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。
六、整數(shù)集合
1、概述
《Redis 設(shè)計(jì)與實(shí)現(xiàn)》 中這樣定義整數(shù)集合：“整數(shù)集合是集合建的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合中只包含整數(shù)，且這個(gè)集合中的元素?cái)?shù)量不多時(shí)，redis就會使用整數(shù)集合intset作為集合的底層實(shí)現(xiàn)。”
我們可以這樣理解整數(shù)集合，他其實(shí)就是一個(gè)特殊的集合，里面存儲的數(shù)據(jù)只能夠是整數(shù)，并且數(shù)據(jù)量不能過大。
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素?cái)?shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
我們觀察一下一個(gè)完成的整數(shù)集合結(jié)構(gòu)圖：
- encoding：用于定義整數(shù)集合的編碼方式
- length：用于記錄整數(shù)集合中變量的數(shù)量
- contents：用于保存元素的數(shù)組，雖然我們在數(shù)據(jù)結(jié)構(gòu)圖中看到，intset將數(shù)組定義為int8_t，但實(shí)際上數(shù)組保存的元素類型取決于encoding
2、特性
- 整數(shù)集合是集合建的底層實(shí)現(xiàn)之一
- 整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組，這個(gè)數(shù)組以有序，無重復(fù)的范式保存集合元素，在有需要時(shí)，程序會根據(jù)新添加的元素類型改變這個(gè)數(shù)組的類型
- 升級操作為整數(shù)集合帶來了操作上的靈活性，并且盡可能地節(jié)約了內(nèi)存2
- 整數(shù)集合只支持升級操作，不支持降級操作
七、壓縮列表
1、概述
壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)，要么就是長度比較短的字符串，那么Redis 就會使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)。
一個(gè)壓縮列表的組成如下：
- zlbytes:用于記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)
- zltail：記錄要列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)
- zllen：記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量
- entryX：要說列表包含的各個(gè)節(jié)點(diǎn)
- zlend：用于標(biāo)記壓縮列表的末端
2、特性
- 壓縮列表是一種為了節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)
- 壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一
- 壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者整數(shù)值
- 添加新節(jié)點(diǎn)到壓縮列表，可能會引發(fā)連鎖更新操作。
