Redis系列文章-數據結構篇
Redis系列文章
前言：
工作原因，在學習mybatis知識後，2個月沒有補充新的知識了，最近拿起書本開始學習。打算寫下這個Redis系列的文章。
目錄結構如下：
Redis內置數據結構
Redis持久化
Redis事件
Redis節點複製功能
Redis哨兵功能
Redis集群功能
Redis排序功能實現
Redis常見使用場景
Redis內置數據結構
說明: Redis數據庫里每個鍵值對都是由對象構成。其中鍵總是字符串對象，值可以為字符串對象(string)，列表對象(list)，集合對象(set)，有序集合對象(sortSet)，Hash對象(hash)。那這些對象在Redis中所使用的底層數據結構是什麼，本章重點去闡述Redis內置數據結構。
簡單動態字符串
Redis沒有直接使用C語言傳統的字符串，而是自己構建了一種名為簡單動態字符串的抽象類型。以下簡稱SDS。
舉個栗子，客戶端執行以下命令：
struct sdshdr {
// sds的長度
int len;
// buf[]中未使用空間
int free;
// 位元組數組，用於保存字符串
char buf[];
}
SDS結構圖如下:
SDS與普通C語言字符串
C語言字符串使用長度為N+1的字符串數組來表示長度為N的字符串，並且字符串最後一個元素總為 ‘/0’；SDS在C字符串基礎上加了free和len屬性，下文便分析SDS相較於C字符串的優勢。
常數複雜度獲取字符串長度
普通C字符串獲取字符長度，需要從字符數組遍歷到隊尾，時間複雜度為O(N)。SDS因為有len屬性，獲取字符長度只需讀取len的值就可，時間複雜度為O(1)。所以，客戶端使用STRLEN命令獲取字符串的長度，不會對性能造成任何影響。
杜絕緩存溢出
C語言字符串S1在修改字符串值時，若沒有為S1分配足夠的空間，會造成緩存溢出。
如S1，S2在內存中緊鄰着，S1保存着”yes”字符串，S2保存着”no”字符串。
現將S1字符串修改為”yessss”，若此時程序猿之前沒有為S1分配足夠的空間，那木就會出現如下情況。
s1的內容溢出到S2的位置了。但SDS不會出現這種情況，SDS在擴容時，會去檢查free的容量是否支撐此次擴容操作。若不支持，則會先進行內存分配，自動擴充到所需大小。
減少修改字符串時帶來的內存重分配次數
正如上文說的，C語言每次對字符串進行修改操作，都會涉及到內存重分配。但Redis作為數據庫，經常被用於數據頻繁修改，若每一次修改都需要進行內存重分配，會大大影響性能。而SDS通過引入free這一屬性，來解決這個問題。
空間預分配
當對SDS進行修改操作，新的字符串長度n大於原來字符串數組長度，且小於1mb。那木在修改後，新的SDS的字符數組長度為2*n。此時，SDS字符串數組中有len的長度未使用，則free = len，len = n; 舉個栗子：
現要將”hello”修改為”hello-world”，此時SDS進行一次內存重分配。按照上面的規則，修改後的字符串為11個位元組，那木會分配22位元組（此時不考慮後面的『\0』）,額外預留了11位元組。
如果接下來，將”hello-world”修改為”hello-world11″，則此時可以直接使用預留的空間，從而不用去重新內存分配。
惰性空間釋放
當將”hello-world”修改為”hello”時，Redis不會主動去釋放多餘的內存空間，將多餘的內存空間的大小寫到free屬性中。這樣做的原因是釋放內存空間也需要性能消耗，並且下次可能還會對字符串進行擴容操作。儘管如此，Redis也提供了相應的API對惰性空間進行釋放。
鏈表
Redis沒有使用C語言內置的鏈表數據結構，構建了自己的鏈表實現。
struct listNode{ // 前置節點 struct listNode *prev; // 後置節點 struct listNode *next; // 節點值 void *value; }listNode;
鏈表實現如下：
struct list{ // 表頭節點 listNode *head; // 表尾節點 listNode *tail; // 節點數量 long len; ...... }list;
可以看出，Redis內置的鏈表結構是一個包含鏈表長度，擁有雙端的雙向鏈表。因為雙向鏈表過於常見，所以總結如下：
1. 雙端： 擁有頭尾節點指針。獲取鏈表的表頭節點和表尾節點時間複雜度都為o(1)
2. 獲取鏈表長度複雜度： 擁有len屬性，獲取鏈表長度時間複雜度為o(1)
字典
字典作為一種數據結構，Redis構建了自己的字典實現。
舉個栗子，執行如下命令：
redis> SET msg hello
在數據庫中創建一個鍵值對，這個鍵值對就是保存在代表數據庫的字典裏面。除了數據庫外，字典也是Hash鍵（Redis對外提供的數據結構）的底層實現。
字典底層是用Hash表實現，數據結構如下：
struct dict{ // 類型特定函數 dictType *type; // 私有數據 void *privdata; // 2張hash表 dictht ht[2]; ... }dict;
重點關注hash表，是存放數據的數據結構，如下，是一個普通的字典，存了兩個鍵值對：
此處解釋一下，字典中包含了兩個hash表，但字典只會使用其中一個ht[0]，ht[1]只會在ht[0]進行rehash時使用。hash表結構簡單介紹下：
struct dictht{ // 哈希表數組 dictEntry **table; // 哈希表大小 long size; // 哈希表大小掩碼，用於計算索引 long sizemask; // 哈希表節點數 long used; }dictht;
當發生hash衝突時，hash表使用鏈地址法解決。若在來一個鍵k3，計算索引，發現位於位置1，但此時位置1已有數據k1，則放置在k1後。
跳躍表
跳躍表是很重要的數據結構，在大部分情況下，可以和平衡樹相媲美。Redis使用跳躍表作為有序集合鍵（對外提供的sortSet數據結構）的底層實現。
舉個栗子，客戶端執行如下命令
redis 127.0.0.1:6379> ZADD skip 1 key1 (integer) 1 redis 127.0.0.1:6379> ZADD skip 2 key2 (integer) 1 redis 127.0.0.1:6379> ZADD skip 3 key3 (integer) 1
那木數據庫會生成一個跳躍表來存放上述的數據（skip 是字符串鍵，所以不存在跳躍表裡）
跳躍表結構如上圖，擁有頭尾節點，節點數量，節點的最高層數（除去頭節點），節點按從小到大排列。下文變分析其中的結構。
跳躍表節點
struct zskiplistNode{ // 後退指針 struct zskiplistNode *backward; // 分值 double score; // 成員對象 robj *obj; // 層結構 struct zskiplistLevel{ // 前進指針 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[] }zskiplistNode
層
每次存入一個帶有分值的值時，會創建一個跳躍表節點。創建跳躍表節點時，程序會根據冪次定律隨機生成一個1-32間的值作為level數組的大小，這個大小就是層的高度。上圖分別展示了3個高度為4層，2層，5層的節點（頭節點32層，不存任何數據）
前進指針
每個層都有一個指向表尾方向的前進指針(level[i].forward)，用於從表頭向表尾方向訪問節點。
上圖虛線表示訪問跳躍表所以節點的過程。
1. 先訪問表頭節點，然後從第四層的前進指針移動到表中的第二個節點。
2. 在第二個節點時，程序沿着第二層的前進指針移動到表中第三個節點。
3. 在第三個節點時，程序同樣沿着第二層的前進指針移動到表中第四個節點。
4. 當程序沿着第四個節點的前進指針訪問，碰到NULL，代表已經訪問結束，結束遍歷。
跨度
層的跨度用於記錄兩個節點之間的距離。兩個節點之間跨度越大，他們就相距越遠。跨度是用來幹嘛的了？是用來計算排位的：在查找某個節點的過程中，將沿途訪問過的所有層的跨度累加起來，得到的結果就是目標節點在跳躍表中的排位。
舉個栗子，還是上圖，要找key3在跳躍表中的排位（即排在第幾位）那木在頭節點中的第5層前進指針直接指向key3，只經過一個層就可以得到了。跨度為3，則代表key3在跳躍表中的位數是第三位。
後退指針
節點可以通過後退指針反向遍歷跳躍表。但後退指針只能訪問它的前節點。這點與前進指針不同。
分值和成員
節點的分值是一個double型的浮點數。跳躍表所有節點都按照從小到大排列。在同一個跳躍表中，各個節點保存的成員對象必須唯一，但分值可以想同。
結語
Redis內置了很多的數據結構，本文只是介紹了平常經常使用的類型。後續想把更多的篇幅留給Redis數據庫的實現。任重而道遠，還是想寫好這個系列。
如果對mybatis感興趣可以移步我的github，我以前博客也對些許知識點進行了分析。覺得好的話麻煩點個star。一個純手寫的mybatis框架
