【Redis原理】底層數據結構五種數據類型

文章目錄

動態字符串SDS`(simple dynamic string )`
- SDS結構定義
- SDS動態擴容
IntSet
- IntSet 結構定義
- IntSet的升級
Dict
- Dict結構定義
- Dict的擴容
- Dict的收縮
- Dict 的rehash
ZipList
- ZipListEntry
- - encoding 編碼
  - - 字符串
    - 整數
- ZipList的連鎖更新問題
QuickList
- QuickList源碼
SkipList
RedisObject
五種數據類型
- String
- List
- Set
- ZSet
- - SkipList + DH
  - ZipList
- Hash

動態字符串SDS`(simple dynamic string )`

我們都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可見字符串是Redis中最常用的一種數據結構。

不過Redis沒有直接使用C語言中的字符串，因為C語言字符串存在很多問題：

// c語言，聲明字符串
char* s = "hello"
// 本質是字符數組： {'h', 'e', 'l', 'l', 'o', '\0'}

對于上述存儲方式而言：

獲取字符串的長度需要通過運算（strlen()）
非二進制安全 字符串的結尾是以 “\0” 字符標識，字符串??不能包含有 “\0” 字符，因此不能保存?進制數據
不可修改

因此直接使用C語言中的字符串對于 Redis 而言是有缺陷的。

SDS結構定義

Redis 是? C 語?實現的，但是它沒有直接使? C 語?的 char* 字符數組來實現字符串，?是??封裝了?個名為簡單動態字符串（simple dynamic string SDS）的數據結構來表示字符串，也就是 Redis 的String 數據類型的底層數據結構是 SDS

就本質而言，SDS是一個結構體，源碼定義如下：

struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; //buf已保存的字符串字節數，不包含結束標示\0uint8_t alloc; //buf申請的總的字節數，不包含結束標示\0unsigned char flags; //不同SDS的頭類型，用來控制SDS的頭大小char buf[]; //存儲的字符串內容
};

可見 SDS的構成是由頭部信息（len alloc flags）＋真實string數據構成的
例如：一個包含字符串“name”的SDS結構如下：
在這里插入圖片描述
針對上面的定義，你是否有諸多疑問？如果沒有，那么請看接下來的問題你是否清楚；如果有，那么我相信通過下面的問題能夠幫你解惑：

Q1：既然len 表示已保存字符串的字節數，那根據上面給出的SDS源碼定義，uint8_t表示的最大值為255，且不包含\0,這意味著真實有效字符串長度最大只能是254，但是Redis 中設置key對應的value時長度可能會超過254，這怎么解決？

A1：結論：Redis中提供了多種SDS存儲方案，通過設置flags可以選擇合適的存儲結構，具體如下
flags可選擇的值：

#define SDS_TYPE_8 1 1yte
#define SDS_TYPE_16 2 2byte
#define SDS_TYPE_32 3 4byte
#define SDS_TYPE_64 4 8byte

通過對flags的設置，相應地，SDS結構中的 len alloc 字段的類型也會與之變化。例如，flags設置為 SDS_TYPE_16,此時len 和alloc 的類型就為uint16_t，這樣可保存的字符串長度就足夠了

Q2：一個SDS為什么要設置這么多不同大小的結構，直接使用SDS_TYPE_64不就能存儲所有string類型的value了？

A2：結論：理論上是可以的，但是如果使用SDS_TYPE_64，意味著SDS頭部信息中的len 和 alloc 兩個字段各占8byte，并且日常使用set key value 時 value的長度絕大多數不會超過254byte，因此使用SDS_TYPE_8就可以滿足大部分需求，相比之下，使用SDS_TYPE_64就會造成大量的內存資源浪費

Q3：C中的字符串定義不是二進制安全的，那SDS中是如何保證二進制安全的？

A3：SDS頭部信息中記錄了字符串的真實長度（len）以及buf的容量（alloc）,因此在SDS這種結構下，字符串取多長，字符串中是否由特殊字符（如\0）這些內容都不需要關心，只需要根據字符串的起始地址 + 字符串長度即可獲取其值，因此是二進制安全的。至于數據部分最后的\0是為了兼容C語言而存在的

SDS動態擴容

SDS之所以叫做動態字符串，是因為它具備動態擴容的能力。
例如一個內容為“hi”的SDS：
在這里插入圖片描述
假如我們要給SDS追加一段字符串,Amy，這里首先會申請新內存空間:

如果新字符串小于1M，則新空間為擴展后字符串長度的兩倍+1；
如果新字符串大于1M，則新空間為擴展后字符串長度+1M+1。稱為內存預分配。

最終，擴容后的結果如下所示：
在這里插入圖片描述

SDS的優點：

獲取字符串長度的時間復雜度為O(1)
支持動態擴容
減少內存分配次數
二進制安全

IntSet

IntSet 結構定義

IntSet是Redis中set集合的一種實現方式，基于整數數組來實現，并且具備長度可變、有序等特征

結構定義如下：

typedef struct intset {uint32_t encoding; //編碼方式，支持存放16位、32位、64位整數uint32_t length; //元素個數int8_t contents[]; //整數數組，保存集合數據
} intset;其中的encoding包含三種模式，表示存儲的整數大小不同：
/* Note that these encodings are ordered, so:* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t)) //2字節整數
#define INTSET_ENC_INT32 (sizeof(int32_t)) //4字節整數
#define INTSET_ENC_INT64 (sizeof(int64_t)) //8字節整數

為了方便查找，Redis會將intset中所有的整數按照升序依次保存在contents數組中，結構如圖：

在這里插入圖片描述
現在，數組中每個數字都在int16_t的范圍內，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節大小為:

encoding：4字節
length：4字節
contents：2字節 * 3 = 6字節

從上述contents 大小的計算以及 contents 的類型 int8_t contents[] 可以看出，IntSet中contents是指向數組首地址的指針，僅僅是記錄數據首元素地址，而訪問數組中的每一個元素時的步長是由encoding來決定的。

上述例子中encoding的值為INTSET_ENC_INT16，因此尋址步長為2byte，也即數組每個元素的大小為2byte，因此contents中存儲的元素占用6byte

IntSet的升級

現在，假設有一個intset，元素為{5,10，20}，采用的編碼是INTSET_ENC_INT16，則每個整數占2字節：
在這里插入圖片描述
我們向該其中添加一個數字：50000，這個數字超出了int16_t的范圍，因此intset會自動升級編碼方式到合適的大小。

具體流程如下：

升級編碼為INTSET_ENC_INT32, 每個整數占4字節，并按照新的編碼方式及元素個數擴容數組
倒序依次將數組中的元素拷貝到擴容后的正確位置
插入新元素
將inset的encoding屬性改為INTSET_ENC_INT32，將length屬性改為4

關鍵源碼解讀

IntSet新增流程

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {// 獲取當前值編碼uint8_t valenc = _intsetValueEncoding(value);// 要插入的位置uint32_t pos; if (success) *success = 1;// 判斷編碼是不是超過了當前intset的編碼if (valenc > intrev32ifbe(is->encoding)) {// 超出編碼，需要升級return intsetUpgradeAndAdd(is,value);} else {// 在當前intset中查找值與value一樣的元素的角標posif (intsetSearch(is,value,&pos)) {//如果找到了，則無需插入，直接結束并返回失敗if (success) *success = 0; return is;}// 數組擴容is = intsetResize(is,intrev32ifbe(is->length)+1);// 移動數組中pos之后的元素到pos+1，給新元素騰出空間if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);}// 插入新元素_intsetSet(is,pos,value);// 重置元素長度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

IntSet升級流程

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {// 獲取當前intset編碼uint8_t curenc = intrev32ifbe(is->encoding);// 獲取新編碼uint8_t newenc = _intsetValueEncoding(value);// 獲取元素個數int length = intrev32ifbe(is->length); // 判斷新元素是大于0還是小于0 ，小于0插入隊首、大于0插入隊尾int prepend = value < 0 ? 1 : 0;// 重置編碼為新編碼is->encoding = intrev32ifbe(newenc);// 重置數組大小is = intsetResize(is,intrev32ifbe(is->length)+1);// 倒序遍歷，逐個搬運元素到新的位置，_intsetGetEncoded按照舊編碼方式查找舊元素while(length--) // _intsetSet按照新編碼方式插入新元素_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));/* 插入新元素，prepend決定是隊首還是隊尾*/if (prepend)_intsetSet(is,0,value);else_intsetSet(is,intrev32ifbe(is->length),value);// 修改數組長度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

在這里插入圖片描述

總結：

Redis會確保Intset中的元素唯一、有序
具備類型升級機制，可以節省內存空間
底層采用二分查找方式來查詢

Dict

Dict結構定義

我們知道Redis是一個鍵值型（Key-Value Pair）的數據庫，我們可以根據鍵實現快速的增刪改查。而鍵與值的映射關系正是通過Dict來實現的。

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節點（DictEntry）、字典（Dict）

我們先來了解一下哈希表和哈希節點的源碼定義：

// 哈希表 DictHashTable
typedef struct dictht {// 指針數組，數組中的每一個元素是一個指向entry的指針dictEntry **table; // 哈希表大小unsigned long size;     // 哈希表大小的掩碼，總等于size - 1unsigned long sizemask;     // entry個數unsigned long used; 
} dictht;// 哈希節點 DictEntry
typedef struct dictEntry {void *key; // 鍵union {void *val;uint64_t u64;int64_t s64;double d;} v; // 值// 下一個Entry的指針，用于解決哈希沖突struct dictEntry *next; 
} dictEntry;

當我們向Dict添加鍵值對時，Redis首先根據key計算出hash值（h），然后利用 h & sizemask來計算元素應該存儲到數組中的哪個索引位置。

例如：我們存儲k1=v1，假設k1的哈希值h =1，則1&3 =1，因此k1=v1要存儲到數組角標1位置
在這里插入圖片描述
這里的 3 是sizemark的值，因為Dict在初始化的時候size最小是4

假設此時來了一組新的k-v，為k2 = v2, 并且經過運算，k2的hash值得到的角標也是1，此時就會產生哈希沖突，解決該沖突使用鏈地址法，且采用頭插的方式，具體如下：
在這里插入圖片描述

到這里，哈希表和哈希節點的相關內容告一段落，我們接下來研究一下這個字典Dict的源碼

// 字典Dict
typedef struct dict {dictType *type; // dict類型，內置不同的hash函數void *privdata;     // 私有數據，在做特殊hash運算時用// 一個Dict包含兩個哈希表，其中一個是當前數據，另一個一般是空，rehash時使用dictht ht[2]; long rehashidx;   // rehash的進度，-1表示未進行int16_t pauserehash; // rehash是否暫停，1則暫停，0則繼續
} dict;

鑒于此，將上述的例子稍作更改，假設k1最終得到的角標是1， k2最終得到的角標是2，那么最終的組織結構應如下所示：
在這里插入圖片描述

Dict的擴容

Dict中的HashTable就是數組結合單向鏈表的實現，當集合中元素較多時，必然導致哈希沖突增多，鏈表過長，則查詢效率會大大降低

Dict在每次新增鍵值對時都會檢查負載因子（LoadFactor = used/size），滿足以下兩種情況時會觸發哈希表擴容：

哈希表的 LoadFactor >= 1，并且服務器沒有執行 BGSAVE 或者 BGREWRITEAOF 等后臺進程
哈希表的 LoadFactor > 5

具體的源碼如下：

static int _dictExpandIfNeeded(dict *d){// 如果正在rehash，則返回okif (dictIsRehashing(d)) return DICT_OK;    // 如果哈希表為空，則初始化哈希表為默認大小：4if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);// 當負載因子（used/size）達到1以上，并且當前沒有進行bgrewrite等子進程操作// 或者負載因子超過5，則進行 dictExpand ，也就是擴容if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){// 擴容大小為used + 1，底層會對擴容大小做判斷，實際上找的是第一個大于等于 used+1 的 2^nreturn dictExpand(d, d->ht[0].used + 1);}return DICT_OK;
}

Dict的收縮

Dict除了擴容以外，每次刪除元素時，也會對負載因子做檢查，當LoadFactor < 0.1 時，會做哈希表收縮。
核心源碼邏輯如下：

// t_hash.c # hashTypeDeleted() 
...
if (dictDelete((dict*)o->ptr, field) == C_OK) {deleted = 1;// 刪除成功后，檢查是否需要重置Dict大小，如果需要則調用dictResize重置if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
...// server.c 文件
int htNeedsResize(dict *dict) {long long size, used;// 哈希表大小size = dictSlots(dict);// entry數量used = dictSize(dict);// size > 4（哈希表初識大小）并且 負載因子低于0.1return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}int dictResize(dict *d){unsigned long minimal;// 如果正在做bgsave或bgrewriteof或rehash，則返回錯誤if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;// 獲取used，也就是entry個數minimal = d->ht[0].used;// 如果used小于4，則重置為4if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;// 重置大小為minimal，其實是第一個大于等于minimal的2^nreturn dictExpand(d, minimal);
}

Dict 的rehash

不管是擴容還是收縮，必定會創建新的哈希表，導致哈希表的size和sizemask變化，而key的查詢與sizemask有關。因此必須對哈希表中的每一個key重新計算索引，插入新的哈希表，這個過程稱為rehash。過程是這樣的：

計算新hash表的realeSize，值取決于當前要做的是擴容還是收縮：
①如果是擴容，則新size為第一個大于等于dict.ht[0].used + 1的2^n
②如果是收縮，則新size為第一個大于等于dict.ht[0].used的2^n （不得小于4）
按照新的realeSize申請內存空間，創建dictht，并賦值給dict.ht[1]
設置dict.rehashidx = 0，標示開始rehash
將dict.ht[0]中的每一個dictEntry都rehash到dict.ht[1]
釋放原來的dict.ht[0]的內存，并將dict.ht[1]賦值給dict.ht[0]，同時把dict.ht[1]初始化為空哈希表

下面通過一個例子來說明上述的流程：

初始階段，有一個Dict, 哈希表ht[0]中右4個有效元素，ht[1] 為null
在這里插入圖片描述
此時需要插入一個新的鍵值對<k5,v5>，由于ht[0]中的有效元素已經為4，此時再插入ht[0]的時候負載因子一定會大于1，假設此時服務器沒有執行 BGSAVE 或者 BGREWRITEAOF 等后臺進程，那么就會觸發 Dict的擴容操作

接下來就進入遷移流程

在這里插入圖片描述
最后，做ht[0] 與 ht[1] 的交接工作

至此流程完畢

Q：上述的步驟4是否可以一次性將所有元素做rehash？
A：Dict的rehash并不是一次性完成的。試想一下，如果Dict中包含數百萬的entry，要在一次rehash完成，極有可能導致主線程阻塞。因此Dict的rehash是分多次、漸進式的完成，因此稱為漸進式rehash
因此，rehash的最終完整流程應該是：

計算新hash表的realeSize，值取決于當前要做的是擴容還是收縮：
①如果是擴容，則新size為第一個大于等于dict.ht[0].used + 1的2^n
②如果是收縮，則新size為第一個大于等于dict.ht[0].used的2^n （不得小于4）
按照新的realeSize申請內存空間，創建dictht，并賦值給dict.ht[1]
設置dict.rehashidx = 0，標示開始rehash
每次執行新增、查詢、修改、刪除操作時，都檢查一下dict.rehashidx是否大于-1，如果是則將dict.ht[0].table[rehashidx]的entry鏈表rehash到dict.ht[1]，并且將rehashidx++。直至dict.ht[0]的所有數據都rehash到dict.ht[1]
釋放原來的dict.ht[0]的內存，并將dict.ht[1]賦值給dict.ht[0]，同時把dict.ht[1]初始化為空哈希表
將rehashidx賦值為-1，代表rehash結束
在rehash過程中，新增操作，則直接寫入ht[1]，查詢、修改和刪除則會在dict.ht[0]和dict.ht[1]依次查找并執行。這樣可以確保ht[0]的數據只減不增，隨著rehash最終為空

總結：

Dict的結構：

Dict底層是數組加鏈表來解決哈希沖突
Dict包含兩個哈希表，ht[0]平常用，ht[1]用來rehash

Dict的伸縮：

當LoadFactor大于5或者LoadFactor大于1并且沒有子進程任務時，Dict擴容
當LoadFactor小于0.1時，Dict收縮
擴容大小為第一個大于等于used + 1的2^n
收縮大小為第一個大于等于used 的2^n
Dict采用漸進式rehash，每次訪問Dict時執行一次rehash
rehash時ht[0]只減不增，新增操作只在ht[1]執行，其它操作在兩個哈希表

ZipList

ZipList 是一種特殊的“雙端鏈表”(具有雙端鏈表的特性但不是鏈表結構) ，由一系列特殊編碼的連續內存塊組成。可以在任意一端進行壓入/彈出操作, 并且該操作的時間復雜度為 O(1)

在這里插入圖片描述
關于ZIP List的組成字段介紹如下：

ZipListEntry

ZipList 中的Entry并不像普通鏈表那樣記錄前后節點的指針，因為記錄兩個指針要占用16個字節，浪費內存。而是采用了下面的結構：
在這里插入圖片描述

previous_entry_length：前一節點的長度，占1個或5個字節
①如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
②如果前一節點的長度大于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據
encoding：編碼屬性，記錄content的數據類型（字符串還是整數）以及長度，占用1個、2個或5個字節
contents：負責保存節點的數據，可以是字符串或整數

ZipList中所有存儲長度的數值均采用小端字節序

encoding 編碼

ipListEntry中的encoding編碼分為字符串和整數兩種：

字符串

如果encoding是以00、01或者10開頭，則證明content是字符串
在這里插入圖片描述
例如，我們要保存字符串：ab和 bc

整數

如果encoding是以11開始，則證明content是整數，且encoding固定只占用1個字節

在這里插入圖片描述
例如，一個ZipList中包含兩個整數值：2和5

在這里插入圖片描述

ZipList的連鎖更新問題

ZipList的每個Entry都包含previous_entry_length來記錄上一個節點的大小，長度是1個或5個字節

如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
如果前一節點的長度大于等于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據

現在，假設我們有N個連續的、長度為250~253字節之間的entry，因此entry的previous_entry_length屬性用1個字節即可表示，如圖所示：
在這里插入圖片描述
假設現在需要插入一個大小為254byte的entry：

那么此時該entry的后一個節點中記錄前一節點長度的變量pre_entry_len就不能用一個字節，而是要用5個字節來記錄，同理，后續的每一個entry的pre_entry_len都需要用5個字節記錄，因為他們的前一個entry大小都大于等于254字節了。

這種現象就被稱為 ZipList的連鎖更新

在這里插入圖片描述

總結一下：ZipList這種特殊情況下產生的連續多次空間擴展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導致連鎖更新的發生。

ZipList特性：

壓縮列表的可以看做一種連續內存空間的"雙向鏈表"
列表的節點之間不是通過指針連接，而是記錄上一節點和本節點長度來尋址，內存占用較低
如果列表數據過多，導致鏈表過長，可能影響查詢性能
增或刪較大數據時有可能發生連續更新問題

QuickList

Q1：ZipList雖然節省內存，但申請內存必須是連續空間，如果內存占用較多，申請內存效率很低。怎么辦？
A1：為了緩解這個問題，我們必須限制ZipList的長度和entry大小。

Q2：但是我們要存儲大量數據，超出了ZipList最佳的上限該怎么辦？
A2：我們可以創建多個ZipList來分片存儲數據。

Q3：數據拆分后比較分散，不方便管理和查找，這多個ZipList如何建立聯系？
A3：Redis在3.2版本引入了新的數據結構QuickList，它是一個雙端鏈表，只不過鏈表中的每個節點都是一個ZipList。

在這里插入圖片描述
了避免QuickList中的每個ZipList中entry過多，Redis提供了一個配置項：list-max-ziplist-size來限制

如果值為正，則代表ZipList的允許的entry個數的最大值
如果值為負，則代表ZipList的最大內存大小，分5種情況
①-1：每個ZipList的內存占用不能超過4kb
②-2：每個ZipList的內存占用不能超過8kb
③-3：每個ZipList的內存占用不能超過16kb
④-4：每個ZipList的內存占用不能超過32kb
⑤-5：每個ZipList的內存占用不能超過64kb

其默認值為 -2
在這里插入圖片描述
除了控制ZipList的大小，QuickList還可以對節點的ZipList做壓縮。通過配置項list-compress-depth來控制。因為鏈表一般都是從首尾訪問較多，所以首尾是不壓縮的。這個參數是控制首尾不壓縮的節點個數。

0：特殊值，代表不壓縮
1：標示QuickList的首尾各有1個節點不壓縮，中間節點壓縮
2：標示QuickList的首尾各有2個節點不壓縮，中間節點壓縮（以此類推）

默認值：
在這里插入圖片描述

QuickList源碼

typedef struct quicklist {// 頭節點指針quicklistNode *head; // 尾節點指針quicklistNode *tail; // 所有ziplist的entry的數量unsigned long count;    // ziplists總數量unsigned long len;// ziplist的entry上限，默認值 -2 int fill : QL_FILL_BITS;// 首尾不壓縮的節點數量unsigned int compress : QL_COMP_BITS;// 內存重分配時的書簽數量及數組，一般用不到unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;typedef struct quicklistNode {// 前一個節點指針struct quicklistNode *prev;// 下一個節點指針struct quicklistNode *next;// 當前節點的ZipList指針unsigned char *zl;// 當前節點的ZipList的字節大小unsigned int sz;// 當前節點的ZipList的entry個數unsigned int count : 16;  // 編碼方式：1，ZipList; 2，lzf壓縮模式unsigned int encoding : 2;// 數據容器類型（預留）：1，其它；2，ZipListunsigned int container : 2;// 是否被解壓縮。1：則說明被解壓了，將來要重新壓縮unsigned int recompress : 1;unsigned int attempted_compress : 1; //測試用unsigned int extra : 10; /*預留字段*/
} quicklistNode;

結構示意圖：
在這里插入圖片描述

QuickList的特點：

是一個節點為ZipList的雙端鏈表
節點采用ZipList，解決了傳統鏈表的內存占用問題
控制了ZipList大小，解決連續內存空間申請效率問題
中間節點可以壓縮，進一步節省了內存

SkipList

kipList（跳表）首先是鏈表，但與傳統鏈表相比有幾點差異

元素按照升序排列存儲
節點可能包含多個指針，指針跨度不同。

跳表的數據結構

// t_zset.c
typedef struct zskiplist {// 頭尾節點指針struct zskiplistNode *header, *tail;// 節點數量unsigned long length;// 最大的索引層級，默認是1int level;
} zskiplist;// t_zset.c
typedef struct zskiplistNode {sds ele; // 節點存儲的值double score;// 節點分數，排序、查找用struct zskiplistNode *backward; // 前一個節點指針struct zskiplistLevel {struct zskiplistNode *forward; // 下一個節點指針unsigned long span; // 索引跨度} level[]; // 多級索引數組
} zskiplistNode;

在這里插入圖片描述

SkipList的特點：

跳躍表是一個雙向鏈表，每個節點都包含score和ele值
節點按照score值排序，score值一樣則按照ele字典排序
每個節點都可以包含多層指針，層數是1到32之間的隨機數
不同層指針到下一個節點的跨度不同，層級越高，跨度越大
增刪改查效率與紅黑樹基本一致，實現卻更簡單

RedisObject

Redis中的任意數據類型的鍵和值都會被封裝為一個RedisObject，也叫做Redis對象，源碼如下：
在這里插入圖片描述
Redis中會根據存儲的數據類型不同，選擇不同的編碼方式，共包含11種不同類型：

Redis中會根據存儲的數據類型不同，選擇不同的編碼方式。每種數據類型的使用的編碼方式如下：

五種數據類型

String

String是Redis中最常見的數據存儲類型：

其基本編碼方式是 RAW，基于簡單動態字符串SDS實現，存儲上限為512MB。
如果存儲的SDS長度小于44字節，則會采用EMBSTR編碼，此時object head與SDS是一段連續空間。申請內存時只需要調用一次內存分配函數，效率更高。
如果存儲的字符串是整數值，并且大小在LONG_MAX范圍內，則會采用INT編碼：直接將數據保存在RedisObject的ptr指針位置（剛好8字節），不再需要SDS了。

下面給出不同編碼方式下的string 圖解：
RAW
在這里插入圖片描述

EMBSTR

在這里插入圖片描述

INT
在這里插入圖片描述

List

Redis的List類型可以從首、尾操作列表中的元素
在這里插入圖片描述
在3.2版本之前，Redis采用ZipList和LinkedList來實現List，當元素數量小于512并且元素大小小于64字節時采用ZipList編碼，超過則采用LinkedList編碼。

在3.2版本之后，Redis統一采用QuickList來實現List

//創建 quicklist obj
robj *createQuicklistObject(void) {// 申請內存并初始化QuickListquicklist *l = quicklistCreate();// 創建RedisObject，type為OBJ_LIST// ptr指向 QuickListrobj *o = createObject(OBJ_LIST,l);// 設置編碼為 QuickListo->encoding = OBJ_ENCODING_QUICKLIST;return o;
}void pushGenericCommand(client *c, int where, int xx) {int j;// 嘗試找到KEY對應的listrobj *lobj = lookupKeyWrite(c->db, c->argv[1]);// 檢查類型是否正確if (checkType(c,lobj,OBJ_LIST)) return;// 檢查是否為空if (!lobj) {if (xx) {addReply(c, shared.czero);return;}// 為空，則創建新的QuickListlobj = createQuicklistObject();quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,server.list_compress_depth);dbAdd(c->db,c->argv[1],lobj);}// 略 ...
}

list 的數據組織格式示意圖：

在這里插入圖片描述

Set

Set是Redis中的單列集合，滿足下列特點：

不保證有序性
保證元素唯一（常用于判斷元素是否存在）
求交集、并集、差集

可以看出，Set對查詢元素的效率要求非常高，因此：
為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來存儲元素，value統一為null
當存儲的所有數據都是整數，并且元素數量不超過set-max-intset-entries(默認值512)時，Set會采用IntSet編碼，以節省內存。

創建Set的核心代碼：
在這里插入圖片描述

執行Set的add操作核心代碼：
在這里插入圖片描述
下面通過一個例子說明上述ADD函數的邏輯：

假設初始set中存儲了3個整型數據，此時Set采用的編碼方式是IntSet
在這里插入圖片描述
現在執行 sadd s1 m1
此時根據add的邏輯，需要轉換Set的編碼方式為HT，因此會創建Dict,并將原來的三個整數存儲進去同時存儲m1

此時該Set的編碼方式就變成了HT編碼

ZSet

ZSet也就是SortedSet，其中每一個元素都需要指定一個score值和member值，并且需要滿足以下要求：

可以根據score值排序后
member必須唯一
可以根據member查詢分數

在這里插入圖片描述

因此，zset底層數據結構必須滿足鍵值存儲、鍵必須唯一、可排序這幾個需求

SkipList：可以排序，并且可以同時存儲score和ele值（member）,但是SkipList 中是以score大小做升序排列的，自身無法做到鍵唯一
HT（Dict）：可以鍵值存儲，并且可以根據key找value，可以通過邏輯限制做到鍵唯一，但是無法做到可排序

那么。ZSet底層到底是用的是哪種數據結構呢？總的來講，ZSet底層采用了兩套數據結構來存儲。分別是 SkipList + DH 組合以及 ZipList數據結構

SkipList + DH

結構定義

// zset結構
typedef struct zset {// Dict指針dict *dict;// SkipList指針zskiplist *zsl;
} zset;robj *createZsetObject(void) {zset *zs = zmalloc(sizeof(*zs));robj *o;// 創建Dictzs->dict = dictCreate(&zsetDictType,NULL);// 創建SkipListzs->zsl = zslCreate(); o = createObject(OBJ_ZSET,zs);o->encoding = OBJ_ENCODING_SKIPLIST;return o;
}

內存結構圖如下所示：
在這里插入圖片描述

針對上述內存結構圖，通過分析我們可以發現：同一份數據ZSet底層由于采用兩種數據結構相結合的方式存儲數據，導致數據多次存儲，出現數據冗余，并且兩種存儲結構對于內存的開銷相對是較大的

當元素數量不多時，HT和SkipList的優勢不明顯，而且更耗內存。因此ZSet還會采用ZipList結構來節省內存

ZipList

使用ZipList作為ZSet的底層數據結構需要滿足以下兩個條件：

元素數量小于zset_max_ziplist_entries，默認值128
每個元素都小于zset_max_ziplist_value字節，默認值64

具體源碼實現如下：
在這里插入圖片描述
其中zsetAdd函數中會針對ZSet當前的狀態以及添加元素的具體情況對 ZSet底層的數據結構作出相應的改變

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {/* 判斷編碼方式*/// 是ZipList編碼if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {unsigned char *eptr;// 判斷當前元素是否已經存在，已經存在則更新score即可if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {//...略return 1;} else if (!xx) {// 元素不存在，需要新增，則判斷ziplist長度有沒有超、元素的大小有沒有超if (zzlLength(zobj->ptr)+1 >server.zset_max_ziplist_entries|| 	sdslen(ele) > server.zset_max_ziplist_value || !ziplistSafeToAdd(zobj->ptr, sdslen(ele))){ // 如果超出，則需要轉為SkipList編碼zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);} else {zobj->ptr = zzlInsert(zobj->ptr,ele,score);if (newscore) *newscore = score;*out_flags |= ZADD_OUT_ADDED;return 1;}} else {*out_flags |= ZADD_OUT_NOP;return 1;}}    // 本身就是SKIPLIST編碼，無需轉換if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {// ...略} else {serverPanic("Unknown sorted set encoding");}return 0; /* Never reached. */
}