Redis（Remote Dictionary Server）是一個開源的高性能鍵值存儲系統，廣泛應用于緩存、消息隊列、排行榜等場景。Redis之所以能夠提供如此高效的性能，很大程度上得益于其底層數據結構的精心設計。本文將詳細介紹Redis的六種底層數據結構：簡單動態字符串（SDS）、鏈表（Linked List）、字典（Dictionary）、跳躍表（Skip List）、整數集合（IntSet）和壓縮列表（ZipList）。通過對這些數據結構的深入理解，我們可以更好地掌握Redis的工作原理，并優化其在實際應用中的使用。
簡單動態字符串（Simple Dynamic String，SDS）是Redis中用于存儲字符串數據的基本數據結構。與C語言中的原生字符串不同，SDS在C字符串的基礎上進行了擴展，提供了更多的功能和更高的性能。
SDS的結構定義如下：
struct sdshdr {
int len; // 字符串的長度
int free; // 未使用的空間
char buf[]; // 字符串的實際內容
};
len：表示字符串的實際長度。free：表示字符串中未使用的空間。buf：存儲字符串的實際內容。SDS相較于C語言的原生字符串具有以下優勢：
O(1)時間復雜度獲取字符串長度：C語言中的字符串需要通過遍歷整個字符串來計算長度，時間復雜度為O(n)。而SDS通過len字段直接記錄字符串的長度，時間復雜度為O(1)。
避免緩沖區溢出：C語言中的字符串操作容易導致緩沖區溢出，而SDS在進行字符串操作時會自動檢查空間是否足夠，并在必要時進行擴展。
減少內存重分配次數：SDS通過free字段記錄未使用的空間，可以在字符串增長時減少內存重分配的次數，從而提高性能。
二進制安全：SDS可以存儲任意二進制數據，而C語言中的字符串以\0結尾，無法存儲包含\0的數據。
SDS廣泛應用于Redis中的字符串類型數據存儲，如鍵值對的鍵和值、列表的元素等。由于其高效的性能和靈活的特性，SDS成為了Redis中最基礎的數據結構之一。
鏈表（Linked List）是Redis中用于存儲列表類型數據的基本數據結構。Redis中的鏈表是一個雙向鏈表，每個節點包含指向前后節點的指針。
鏈表的結構定義如下：
typedef struct listNode {
struct listNode *prev; // 前驅節點
struct listNode *next; // 后繼節點
void *value; // 節點的值
} listNode;
typedef struct list {
listNode *head; // 鏈表的頭節點
listNode *tail; // 鏈表的尾節點
unsigned long len; // 鏈表的長度
void *(*dup)(void *ptr); // 節點值復制函數
void (*free)(void *ptr); // 節點值釋放函數
int (*match)(void *ptr, void *key); // 節點值比較函數
} list;
listNode：鏈表的節點，包含指向前后節點的指針和節點的值。list：鏈表的結構，包含頭節點、尾節點、長度以及一些操作函數。鏈表相較于數組具有以下優勢：
動態擴展：鏈表可以動態地增加或刪除節點，不需要預先分配固定大小的內存空間。
插入和刪除操作高效：在鏈表中插入或刪除節點的時間復雜度為O(1)，而數組中的插入和刪除操作需要移動元素，時間復雜度為O(n)。
靈活的內存管理：鏈表中的節點可以分散在內存中的不同位置，不需要連續的內存空間。
鏈表廣泛應用于Redis中的列表類型數據存儲，如列表鍵、發布/訂閱系統中的消息隊列等。由于其高效的插入和刪除操作，鏈表在處理動態數據時表現出色。
字典（Dictionary）是Redis中用于存儲鍵值對數據的基本數據結構。Redis中的字典是一個哈希表，通過哈希函數將鍵映射到哈希表中的索引位置。
字典的結構定義如下：
typedef struct dictEntry {
void *key; // 鍵
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
struct dictEntry *next; // 指向下一個節點的指針
} dictEntry;
typedef struct dictht {
dictEntry **table; // 哈希表數組
unsigned long size; // 哈希表的大小
unsigned long sizemask; // 哈希表大小掩碼
unsigned long used; // 哈希表中已使用的節點數
} dictht;
typedef struct dict {
dictType *type; // 字典類型
void *privdata; // 私有數據
dictht ht[2]; // 哈希表數組
long rehashidx; // 重哈希索引
unsigned long iterators; // 當前正在運行的迭代器數量
} dict;
dictEntry：字典的節點，包含鍵、值和指向下一個節點的指針。dictht：哈希表，包含哈希表數組、大小、掩碼和已使用的節點數。dict：字典的結構，包含字典類型、私有數據、哈希表數組、重哈希索引和迭代器數量。字典相較于其他數據結構具有以下優勢：
高效的查找操作：通過哈希函數將鍵映射到哈希表中的索引位置，查找操作的時間復雜度為O(1)。
動態擴展：字典可以根據需要動態擴展哈希表的大小，避免哈希沖突導致的性能下降。
靈活的鍵值對存儲：字典可以存儲任意類型的鍵和值，適用于各種場景。
字典廣泛應用于Redis中的鍵值對數據存儲，如哈希表鍵、集合鍵等。由于其高效的查找操作和靈活的鍵值對存儲，字典成為了Redis中最常用的數據結構之一。
跳躍表（Skip List）是Redis中用于存儲有序集合數據的基本數據結構。跳躍表是一種概率平衡的數據結構，通過多層鏈表實現高效的查找、插入和刪除操作。
跳躍表的結構定義如下：
typedef struct zskiplistNode {
sds ele; // 元素值
double score; // 分數
struct zskiplistNode *backward; // 后退指針
struct zskiplistLevel {
struct zskiplistNode *forward; // 前進指針
unsigned long span; // 跨度
} level[]; // 層級數組
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 頭節點和尾節點
unsigned long length; // 跳躍表的長度
int level; // 跳躍表的層級
} zskiplist;
zskiplistNode：跳躍表的節點，包含元素值、分數、后退指針和層級數組。zskiplist：跳躍表的結構，包含頭節點、尾節點、長度和層級。跳躍表相較于其他有序數據結構具有以下優勢：
高效的查找操作：通過多層鏈表實現快速查找，時間復雜度為O(log n)。
動態擴展：跳躍表可以根據需要動態調整層級，保持高效的查找性能。
簡單的實現：跳躍表的實現相對簡單，易于理解和維護。
跳躍表廣泛應用于Redis中的有序集合數據存儲，如有序集合鍵、排行榜等。由于其高效的查找操作和動態擴展能力，跳躍表在處理有序數據時表現出色。
整數集合（IntSet）是Redis中用于存儲整數類型數據的基本數據結構。整數集合是一個有序的整數數組，支持高效的查找、插入和刪除操作。
整數集合的結構定義如下：
typedef struct intset {
uint32_t encoding; // 編碼方式
uint32_t length; // 集合的長度
int8_t contents[]; // 集合的內容
} intset;
encoding：表示整數集合的編碼方式，可以是INTSET_ENC_INT16、INTSET_ENC_INT32或INTSET_ENC_INT64。length：表示整數集合的長度。contents：存儲整數集合的實際內容。整數集合相較于其他數據結構具有以下優勢：
高效的查找操作：通過二分查找實現快速查找，時間復雜度為O(log n)。
內存緊湊：整數集合使用緊湊的內存布局，節省內存空間。
動態擴展：整數集合可以根據需要動態調整編碼方式，支持不同范圍的整數。
整數集合廣泛應用于Redis中的整數類型數據存儲，如集合鍵中的整數元素等。由于其高效的查找操作和緊湊的內存布局，整數集合在處理整數數據時表現出色。
壓縮列表（ZipList）是Redis中用于存儲小型列表和哈希表數據的基本數據結構。壓縮列表是一種緊湊的內存布局，通過連續的內存塊存儲多個元素。
壓縮列表的結構定義如下：
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
zlbytes：表示壓縮列表的總字節數。zltail：表示壓縮列表的尾節點偏移量。zllen：表示壓縮列表的元素個數。entry：表示壓縮列表的元素，包含前一個元素的長度、當前元素的編碼和內容。zlend：表示壓縮列表的結束標志。壓縮列表相較于其他數據結構具有以下優勢：
內存緊湊：壓縮列表使用連續的內存塊存儲多個元素，節省內存空間。
高效的插入和刪除操作：壓縮列表支持在任意位置插入和刪除元素，時間復雜度為O(n)。
靈活的存儲：壓縮列表可以存儲不同類型的數據，如整數、字符串等。
壓縮列表廣泛應用于Redis中的小型列表和哈希表數據存儲，如列表鍵、哈希表鍵等。由于其緊湊的內存布局和高效的插入刪除操作，壓縮列表在處理小型數據時表現出色。
Redis的六種底層數據結構——簡單動態字符串（SDS）、鏈表（Linked List）、字典（Dictionary）、跳躍表（Skip List）、整數集合（IntSet）和壓縮列表（ZipList）——各自具有獨特的優勢和適用場景。通過對這些數據結構的深入理解，我們可以更好地掌握Redis的工作原理，并優化其在實際應用中的使用。無論是高效的查找操作、動態擴展能力，還是緊湊的內存布局，這些數據結構都為Redis的高性能提供了堅實的基礎。在實際開發中，根據具體需求選擇合適的數據結構，可以顯著提升系統的性能和穩定性。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
