引言
前期我們了解了Redis的誕生背景，今天我們來探索下它的數據結構，一步步走近它的世界。
字符串類型?
redis中使用SDS（simple dynamic string）,自己構建的一種名為簡單動態(tài)字符串的抽象類型來表示字符串，區(qū)別于C語言字符串，以下簡稱C字符串。
1、SDS的定義
struct sdshdr {
? ? // 記錄buf數組中已經使用字節(jié)的數量，等于SDS所保存字符串的長度?
? ? int len;
? ? // 記錄buf數組中未使用字節(jié)的長度
? ? int free;
? ? // 字節(jié)數據，用于保存字符串
? ? char buf[];
}
2、SDS與C字符串的區(qū)別、
1、C字符串獲取長度的復雜度為O(N)，SDS獲取字符串長度的復雜度為O(1)。保證了redis獲取字符串的長度不會成為瓶頸；
2、C字符串底層實現是一個N+1個字符長的數組，每次字符串長度發(fā)生改變，都意味著要對數組進行一次重新分配，且容易造成緩沖區(qū)溢；
3、SDS則會進行空間預分配：自身長度不夠的情況下，當拼接字符串后長度小于1M，SDS的buf長度自動擴大1倍加1（空格），長度大于1M，每次擴展空間為加1M。
? ? ? 同時SDS有惰性空間釋放的特征，當縮短字符串的時候，SDS會利用free記錄未使用的空間，以備將來擴展使用；
4、二進制安全：C字符串除了字符串末尾之外，中間不可以包含空格，意味著它只能存放文本數據，而不能像SDS一樣 ，支持圖片、音頻、視頻、壓縮文件這樣的二進制數據。
鏈表
1、鏈表的定義
// 每一個鏈表節(jié)點都使用adlist.h/listNode結構來表示
typedef struct listNode {
? ? // 前置節(jié)點
? ? struct listNode * prev;
? ? // 后置節(jié)點
? ? struct listNode * next;
? ? // 節(jié)點的值
? ? void *value;
}?
typedef struct list {
????// 表頭節(jié)點
????listNode * head;
????// 表尾節(jié)點
????listNode?* tail;
????// 鏈表所包含的節(jié)點數量
????unsigned long len;
????// 節(jié)點值復制函數
? ? void *(*dup) (void *ptr);
????// 節(jié)點值釋放函數
? ? void (*free) (void *ptr);
? ? // 節(jié)點值對比函數
? ? int (*match) (void *ptr, void *key);
}?
特點：
1、雙端鏈表：獲取某節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是O(1)；
2、無環(huán)：表頭節(jié)點的prev指針和表尾節(jié)點的next指針都指向NULL，對鏈表的訪問以NULL為終點；
3、帶表頭指針和表尾指針：通過list結構的head和tail，獲取鏈表的表頭節(jié)點和表尾節(jié)點的復雜度都是O(1)；
4、帶鏈表長度計數器：獲取鏈表中節(jié)點數量的復雜度是O(1)；
5、多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點的值，并且可以通過list節(jié)點的dup、free、matct三個屬性為節(jié)點值設置類型特定的函數，所以鏈表可以用來保存各種不同類型的值。
哈希
是一個Mapmap，指值本身又是一種鍵值對結構，如 value={{field1,value1},......fieldN,valueN}}
1、結構定義
typedef struct dictht {
? ? //? ? 哈希表數組
? ? dictEntry **table;
? ? // 哈希表大小
? ? unsigned long size;
? ? //? ? 哈希表大小掩碼，用于計算索引值，總是等于 size -1
? ? unsigned long sizemask;
? ? //? ? 該哈希表已有節(jié)點的數量
? ? unsigned long used;
}
typedef struct dictEntry {
? ? // 健
? ? void *key;
? ? // 值
? ? union {
? ? ? ? void *val;
? ? ? ? uint64_tu64;
? ? ? ? int64_ts64;
? ? }
? ? // 指向下一個哈希表節(jié)點，形成鏈表
????struct dictEntry *next;
}
next屬性可以將多個哈希值相同的鍵值對鏈接在一起，以此來解決鍵沖突
2、rehash(漸進式)
負載因子 = 哈希表已保存節(jié)點數量 / 哈希表大??；
load_factor < 0.1，程序對hash表執(zhí)行收縮操作；
當服務器目前沒有在執(zhí)行BGSAVE或者BGREWRITEAOF，并且load_factor > =1;或則服務器目前正在在執(zhí)行BGSAVE或者BGREWRITEAOF，并且load_factor > =5，hash擴容
集合
特點
集合類型也是用來保存多個字符串的元素，但和列表不同的是集合中?
1. 不允許有重復的元素；
2.集合中的元素是無序的，不能通過索引下標獲取元素；
3.支持集合間的操作，可以取多個集合取交集、并集、差集。
有序集合
1、數據結構
typedef struct zskiplistNode {
? ? // 層
? ? struct zskiplistLevel {
? ? ? ? // 前進指針
? ? ? ? struct?zskiplistNode *forward;
? ? ? ? // 跨度
? ? ? ? unsigned int span;
????} level[];
? ? // 后退指針
? ??struct?zskiplistNode *backward;
? ? // 分值
????double score;
? ? // 成員對象
? ? rodj *obj;
}????zskiplistNode
2、特點
有序集合和集合有著必然的聯系，保留了集合不能有重復成員的特性，區(qū)別是，有序集合中的元素是可以排序的，它給每個元素設置一個分數，作為排序的依據。
（有序集合中的元素不可以重復，但是score 分數 可以重復，就和一個班里的同學學號不能重復，但考試成績可以相同）
