簡單動態(tài)字符串
Redis 底層使用 C 語言實現(xiàn)的则披，但是 Redis 沒有直接使用 C 語言傳統(tǒng)的字符串表示，而是構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string铣墨，SDS）的抽象類型浦夷。
當(dāng) Redis 需要的不僅僅是一個字符串字面量邑飒，而是一個可以被修改的字符串值時，Redis 就會使用 SDS 來表示字符串值帅涂。
下面來看一下议薪，為什么 Redis 會使用 SDS 而不是 C 字符串。
SDS 的定義
struct sdshdr{
//記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量
//等于 SDS 所保存字符串的長度
int len;
//記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
int free;
//字節(jié)數(shù)組媳友，用于保存字符串
char buf[];
}
上圖是 SDS 結(jié)構(gòu)實例斯议，free 表示生于多少空間，len 表示占用了多少空間醇锚，末尾 ‘\0’ 不統(tǒng)計哼御。buf 用于存儲。
SDS 對比 C 字符串優(yōu)勢：
1.常數(shù)復(fù)雜度獲取字符串長度搂抒，C 字符串獲取長度需要遍歷整個字符串艇搀。
2.杜絕緩沖區(qū)溢出，SDS 完全杜絕了緩沖區(qū)溢出求晶，在新分配和拼接的時候焰雕，都會判斷空間夠不夠。
3.減少修改字符串時帶來的內(nèi)存重分配次數(shù)芳杏。應(yīng)用空間預(yù)分配和惰性kongjianshifang機制矩屁。
4.二進制安全，可以保存任意格式的二進制數(shù)據(jù)爵赵。
5.兼容部分 C 字符串函數(shù)吝秕。
鏈表
Redis 構(gòu)建了自己的鏈表實現(xiàn)，當(dāng)一個列表鍵包含了數(shù)量比較多的元素空幻，又或者列表中包含的與那素都是比較長的字符串時烁峭，Redis 就會使用鏈表作為列表鍵的底層實現(xiàn)。
除了鏈表鍵之外，發(fā)布與訂閱约郁、慢查詢缩挑、監(jiān)視器等功能也用到了鏈表。
鏈表節(jié)點結(jié)構(gòu)：
typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}
多個 listNode 組成的雙端鏈表
Redis 應(yīng)用一個 list 結(jié)構(gòu)來持有鏈表鬓梅，如下：
typedef struct list{
//表頭
listNode *head;
//表尾
listNode * tail;
//節(jié)點個數(shù)
unsigned long len;
//節(jié)點值復(fù)制函數(shù)
void (dup)(void ptr);
//節(jié)點釋放函數(shù)
void (free)(void ptr);
//節(jié)點值對比函數(shù)
int (match)(void *ptr,void *key);
} list;
list 結(jié)構(gòu)為鏈表提供了表頭指針 head供置、表尾指針 tail、以及鏈表長度技術(shù)器 len绽快，dup 函數(shù)用于復(fù)制節(jié)點所保存的值芥丧，free 函數(shù)用于釋放鏈表節(jié)點所保存的值，match 函數(shù)用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等坊罢。
list 示意圖：
字典
字典续担，又稱為符號表、關(guān)聯(lián)數(shù)組或映射艘绍，是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)赤拒。
Redis 的字典使用哈希表作為底層實現(xiàn)秫筏，一個哈希表里面可以有多個哈希表結(jié)點诱鞠，每個哈希表結(jié)點就保存了字典中的一個鍵值對。
哈希表結(jié)構(gòu)：
typedef struct dictht{
//哈希表數(shù)組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼这敬，用于計算索引值總是等于 size-1
unsigned long sizemask;
//該哈希表已有節(jié)點的數(shù)量
unsigned long used;
} dictht;
table 屬性是一個數(shù)組航夺，數(shù)組中每個元素都是一個指向 dictEntry 結(jié)構(gòu)的指針，每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對崔涂。size 記錄哈希表的大小阳掐，used 標(biāo)識哈希表已有節(jié)點的數(shù)量。sizemark 總是等于 size - 1冷蚂。
哈希表節(jié)點：
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
unit64_tu64;
int64_ts64;
}v;
//指向下個哈希表節(jié)點缭保，形成鏈表
struct dictEntry *next;
}dictEntry;
next 屬性指向另一個哈希表節(jié)點指針，這個指針可以將多個哈希值相同的鍵值對連接在一起蝙茶，來解決哈希沖突艺骂。
字典結(jié)構(gòu)：
typedef struct dict{
//類型特定函數(shù)
dictType *type;
//私有數(shù)據(jù)
void *privdata;
//哈希表
dict ht[2];
//rehash 索引
//當(dāng) rehash 不在進行時，值為 -1
int rehashidx;
}dict;
type 屬性是一個指向 dictType 結(jié)構(gòu)的指針隆夯，每個 dictType 結(jié)構(gòu)保存了一簇用于特定類型鍵值對的函數(shù)钳恕。
privdata 屬性保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。
跳躍表
跳躍表是一種有序數(shù)據(jù)結(jié)構(gòu)蹄衷，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針忧额，從而達到快速訪問節(jié)點的目的。
大部分情況下愧口，跳躍表可以和平衡樹相匹配睦番。
Redis 只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵耍属，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)托嚣。
跳表示例：
header：指向跳躍表的表頭節(jié)點大咱。
tail：指向跳躍表的表尾節(jié)點。
level：記錄目前跳躍表內(nèi)注益，層數(shù)最大的那個節(jié)點的層數(shù)碴巾。
length：記錄跳躍表的長度，也即是丑搔，跳躍表目前包含節(jié)點的數(shù)量厦瓢。
跳表節(jié)點每一層都有前進指針和跨度，跨度標(biāo)識前進指針指向的節(jié)點和當(dāng)前節(jié)點的距離啤月。
每個節(jié)點都有一個后退指針煮仇，指向前一個節(jié)點。
1.0 2.0 3.0 是每個節(jié)點的分值谎仲，按順序排列浙垫。
o1,o2,o3 是節(jié)點所保存的成員對象。
跳躍表節(jié)點
typedef struct zskiplistNode{
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span郑诺；
}level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
}zskiplistNode;
跳躍表
typedef struct zskiplist{
//表頭節(jié)點和表尾節(jié)點
struct skiplistNode *header, *tail;
表中節(jié)點的數(shù)量
unsigned long length夹姥；
//表中層樹最大的節(jié)點的層數(shù)
int level;
}zskiplist;
整數(shù)集合
整數(shù)集合是 Redis 用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，可以保存的類型為 int16_t辙诞、int32_t 或者 int64_t 的整數(shù)辙售，并且保證集合不會出現(xiàn)重復(fù)元素。
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素數(shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
contents 是整數(shù)集合的底層實現(xiàn)飞涂，整數(shù)集合的每個元素都是 contents 數(shù)字的一個數(shù)組項旦部。
length 屬性記錄了整數(shù)集合包含的元素數(shù)量。
encoding 決定 contents 數(shù)組的類型较店。
整數(shù)集合的升級
每當(dāng)我們要將一個新元素添加到整數(shù)集合里面士八，并且新元素的類型比整數(shù)集合現(xiàn)有元素的類型長，整數(shù)集合就要做升級梁呈。
升級分為三步:
1.根據(jù)新元素類型婚度，擴展整數(shù)集合底層數(shù)組的空間大小，并為新元素分配空間捧杉。
例如下圖陕见，原本集合中的元素是 int16_t 類型的 1,2,3。然后將 65535 添加進去味抖，因為 65535 是 int32_t 類型评甜，所以就要做升級。
2.將底層數(shù)組現(xiàn)有元素轉(zhuǎn)換成新元素相同類型仔涩，所有元素如下圖忍坷，從后往前，一次重新放到新分配的空間的 3,2,1 的位置。
整數(shù)集合升級好處就是靈活性和盡可能的節(jié)約內(nèi)存佩研。
整數(shù)集合不支持降級操作柑肴。
壓縮列表
壓縮列表是列表鍵和哈希鍵的底層實現(xiàn)之一，當(dāng)一個列表鍵只包含少量列表項旬薯，并且每個列表要么就是小整數(shù)值晰骑，要么就是長度比較短的字符串，那么 Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)绊序。
壓縮列表的構(gòu)成：
壓縮列表節(jié)點構(gòu)成
每個壓縮列表節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值硕舆。
previous_entry_length，記錄了壓縮列表中前一個節(jié)點的長度骤公。
encoding抚官，記錄了節(jié)點的 content 屬性所保存的數(shù)據(jù)類型及長度。
content阶捆，保存節(jié)點的值凌节。
壓縮列表有連鎖更新機制，跟上面那個整數(shù)集合升級有點像洒试。
previous_entry_length 記錄了壓縮列表中前一個節(jié)點的長度倍奢，previous_entry_length 的大小是一個字節(jié)，兩個字節(jié)或者五個字節(jié)儡司，根據(jù)前一個元素大小有關(guān)娱挨。但是假如在多小于 254 字節(jié)數(shù)之前添加一個大于等于 254 字節(jié)的數(shù)余指，后續(xù)的 previous_entry_length 都要挨個更新長度捕犬。
最后
至此 Redis 的底層數(shù)據(jù)結(jié)構(gòu)就介紹完了，來看下下面這個表酵镜，Redis 使用的不同類型隊形的編碼方式碉碉。是不是就很清晰了。
參考：Redis 設(shè)計與實現(xiàn)
