共計 3813 個字符，預計需要花費 10 分鐘才能閱讀完成。
Redis 中數據結構的底層實現分析，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面丸趣 TV 小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
1、概述
Redis 是一個開源的使用 ANSI C 語言編寫的 key-value 數據庫，我們可能會較為主觀的認為 Redis 中的字符串就是采用了 C 語言中的傳統字符串表示，但其實不然，Redis 沒有直接使用 C 語言傳統的字符串表示，而是自己構建了一種名為簡單動態字符串（simple dynamic string SDS）的抽象類型，并將 SDS 用作 Redis 的默認字符串表示：redis SET msg hello world
SDS 定義：
struct sdshdr{ // 記錄 buf 數組中已使用字節的數量 // 等于 SDS 保存字符串的長度 int len; // 記錄 buf 數組中未使用字節的數量 int free; // 字節數組，用于保存字符串 char buf[]; }圖片來源：《Redis 設計與實現》
我們看上面對于 SDS 數據類型的定義：
len 保存了 SDS 保存字符串的長度
buf[] 數組用來保存字符串的每個元素
free j 記錄了 buf 數組中未使用的字節數量
2、與 C 語言相比較
一般來說，SDS 除了保存數據庫中的字符串值以外，SDS 還可以作為緩沖區（buffer）：包括 AOF 模塊中的 AOF 緩沖區以及客戶端狀態中的輸入緩沖區。后面在介紹 Redis 的持久化時會進行介紹。
三、鏈表
1、概述
鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，并且可以通過增刪節點來靈活地調整鏈表的長度。
鏈表在 Redis 中的應用非常廣泛，比如列表鍵的底層實現之一就是鏈表。當一個列表鍵包含了數量較多的元素，又或者列表中包含的元素都是比較長的字符串時，Redis 就會使用鏈表作為列表鍵的底層實現。
每個鏈表節點使用一個 listNode 結構表示（adlist.h/listNode）：
typedef struct listNode{ // 前置節點 struct listNode *prev; // 后置節點 struct listNode *next; // 節點的值 void *value; }listNode鏈表的數據結構：
typedef struct list{ // 表頭節點 listNode *head; // 表尾節點 listNode *tail; // 鏈表所包含的節點數量 unsigned long len; // 節點值復制函數 void (*free) (void *ptr); // 節點值釋放函數 void (*free) (void *ptr); // 節點值對比函數 int (*match) (void *ptr,void *key); }list;組成結構圖
2、Redis 鏈表特性
雙端：鏈表具有前置節點和后置節點的引用，獲取這兩個節點時間復雜度都為 O(1)。
無環：表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL, 對鏈表的訪問都是以 NULL 結束。
帶鏈表長度計數器：通過 len 屬性獲取鏈表長度的時間復雜度為 O(1)。
多態：鏈表節點使用 void* 指針來保存節點值，可以保存各種不同類型的值。
四、字典
1、概述
字典又稱為符號表或者關聯數組、或映射（map），是一種用于保存鍵值對的抽象數據結構。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進行查找或修改。C 語言中沒有內置這種數據結構的實現，所以字典依然是 Redis 自己構建的。
哈希表結構定義：
typedef struct dictht{ // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼，用于計算索引值 // 總是等于 size-1 unsigned long sizemask; // 該哈希表已有節點的數量 unsigned long used; }dictht哈希表是由數組 table 組成，table 中每個元素都是指向 dict.h/dictEntry 結構，dictEntry 結構定義如下：
typedef struct dictEntry{ // 鍵 void *key; // 值 union{ void *val; uint64_tu64; int64_ts64; }v; // 指向下一個哈希表節點，形成鏈表 struct dictEntry *next; }dictEntrykey 用來保存鍵，val 屬性用來保存值，值可以是一個指針，也可以是 uint64_t 整數，也可以是 int64_t 整數。
注意這里還有一個指向下一個哈希表節點的指針，我們知道哈希表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放地址法和鏈地址法。這里采用的便是鏈地址法，通過 next 這個指針可以將多個哈希值相同的鍵值對連接在一起，用來解決哈希沖突。
五、跳躍表
1、概述
跳躍表（skiplist）是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。跳躍表是一種隨機化的數據, 跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 mdash; mdash; 查找、刪除、添加等操作都可以在對數期望時間下完成，并且比起平衡樹來說，跳躍表的實現要簡單直觀得多。
Redis 只在兩個地方用到了跳躍表，一個是實現有序集合鍵，另外一個是在集群節點中用作內部數據結構。
Redis 中跳躍表節點定義如下：
typedef struct zskiplistNode { // 層 struct zskiplistLevel{ // 前進指針 struct zskiplistNode *forward; // 跨度 unsigned int span; }level[]; // 后退指針 struct zskiplistNode *backward; // 分值 double score; // 成員對象 robj *obj; } zskiplistNode多個跳躍表節點構成一個跳躍表：
typedef struct zskiplist{ // 表頭節點和表尾節點 structz skiplistNode *header, *tail; // 表中節點的數量 unsigned long length; // 表中層數最大的節點的層數 int level; }zskiplist;header 和 tail 指針分別指向跳躍表的表頭和表尾節點；
length 屬性記錄節點的數量；
level 屬性記錄層數最高的幾點的層數量；
下圖分別展示了完整的跳躍表和單個節點的詳細結構圖：
2、特性
跳表具有如下性質：
由很多層結構組成
每一層都是一個有序的鏈表
最底層 (Level 1) 的鏈表包含所有元素
如果一個元素出現在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現。
每個節點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。
六、整數集合
1、概述
《Redis 設計與實現》中這樣定義整數集合：“整數集合是集合建的底層實現之一，當一個集合中只包含整數，且這個集合中的元素數量不多時，redis 就會使用整數集合 intset 作為集合的底層實現。”
我們可以這樣理解整數集合，他其實就是一個特殊的集合，里面存儲的數據只能夠是整數，并且數據量不能過大。
typedef struct intset{ // 編碼方式 uint32_t encoding; // 集合包含的元素數量 uint32_t length; // 保存元素的數組 int8_t contents[]; }intset;我們觀察一下一個完成的整數集合結構圖：
encoding：用于定義整數集合的編碼方式
length：用于記錄整數集合中變量的數量
contents：用于保存元素的數組，雖然我們在數據結構圖中看到，intset 將數組定義為 int8_t，但實際上數組保存的元素類型取決于 encoding
2、特性
整數集合是集合建的底層實現之一
整數集合的底層實現為數組，這個數組以有序，無重復的范式保存集合元素，在有需要時，程序會根據新添加的元素類型改變這個數組的類型
升級操作為整數集合帶來了操作上的靈活性，并且盡可能地節約了內存 2
整數集合只支持升級操作，不支持降級操作
七、壓縮列表
1、概述
壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數，要么就是長度比較短的字符串，那么 Redis 就會使用壓縮列表來做列表鍵的底層實現。
一個壓縮列表的組成如下：
zlbytes: 用于記錄整個壓縮列表占用的內存字節數
zltail：記錄要列表尾節點距離壓縮列表的起始地址有多少字節
zllen：記錄了壓縮列表包含的節點數量
entryX：要說列表包含的各個節點
zlend：用于標記壓縮列表的末端
2、特性
壓縮列表是一種為了節約內存而開發的順序型數據結構
壓縮列表被用作列表鍵和哈希鍵的底層實現之一
壓縮列表可以包含多個節點，每個節點可以保存一個字節數組或者整數值
添加新節點到壓縮列表，可能會引發連鎖更新操作。
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注丸趣 TV 行業資訊頻道，感謝您對丸趣 TV 的支持。
