如有侵權，請聯系～
如有錯誤，也歡迎批評指正～
本篇文章大部分是來自學習《Redis設計與實現》的筆記

1、RedisObject對象

在介紹Redis各種類型的數據結構之前，先了解一下RedisObject數據結構。RedisObject翻譯過來就是redis對象，它在redis服務端無時無刻都在，可以說redis服務端數據都是以redisObject形式存在。
例如，存儲hash值，那么鍵是存儲相應字符串的redisObject對象，值是存儲相應hash表的redisObject對象。

先整體看下redis數據協議轉換【redis之后在交互的時候是resp協議，在redis服務端都是redisObject】：

RedisObject的數據結構：

typedef struct redisObject {unsigned type:4;       // 數據類型（如字符串、列表、哈希等）unsigned encoding:4;   // 編碼方式（如 raw、int、ziplist 等）unsigned lru:LRU_BITS; // LRU 時間戳或 LFU 數據（用于淘汰策略）int refcount;          // 引用計數（用于內存管理）void *ptr;             // 指向實際數據的指針
} robj;

字段說明：

• type：表示數據的類型，例如字符串（REDIS_STRING）、列表（REDIS_LIST）、哈希（REDIS_HASH）等。
• encoding：表示數據的編碼方式，例如原始字符串（REDIS_ENCODING_RAW）、整數（REDIS_ENCODING_INT）、壓縮列表（REDIS_ENCODING_ZIPLIST）等。
• lru：用于記錄對象的訪問時間，支持 LRU 或 LFU 淘汰策略。
• refcount：引用計數，用于內存管理和共享對象。當這個屬性為0的時候，這個對象就會被回收。相同對象可以共享，減少內存使用。redis在初始化的時候會創建一萬個字符串，值為0～9999的對象用于共享，類似于java的Integer包裝類。
• ptr：指向實際數據的指針，數據的具體存儲方式由 encoding 決定。

一個存儲字符串的redisObject示意圖：

具體編碼方式有哪些以及存儲結構可以參考：redis對象

redis中所有的鍵都是字符串對象，而值可以是下面的五種類型中的任意一個。所以說的列表鍵其實是指的值是列表類型。同樣，命令TYPE返回的也是值的類型。

所有的編碼方式encoding【可以通過OBJECT ENCODING可以查看鍵值對的值的編碼方式】：

數據類型	編碼方式	底層實現	切換條件
String	RAW	簡單動態字符串（SDS）	當字符串的長度大于32字節，始終使用 SDS。
	EMBSTR	簡單動態字符串（SDS）	當字符串的長度小于等于32字節，使用 embstr 編碼。
	INT	整數	當存儲的值可以表示為 64 位有符號整數時，使用 INT 編碼。
List	ZIPLIST	壓縮列表（Ziplist）	元素數量 < list-max-ziplist-entries（默認 512）且每個元素大小 < list-max-ziplist-value（默認 64 字節）。
	LINKEDLIST	雙向鏈表	不滿足上述條件時，切換為雙向鏈表。
Hash	ZIPLIST	壓縮列表（Ziplist）	字段數量 < hash-max-ziplist-entries（默認 512）且每個字段大小 < hash-max-ziplist-value（默認 64 字節）。
	HASHTABLE	哈希表	不滿足上述條件時，切換為哈希表。
Set	INTSET	整數集合（IntSet）	元素數量 < set-max-intset-entries（默認 512）且所有元素為整數時，使用 IntSet。
	HASHTABLE	哈希表	不滿足上述條件時，切換為哈希表。
ZSet	ZIPLIST	壓縮列表（Ziplist）	元素數量 < zset-max-ziplist-entries（默認 128）且每個成員大小 < zset-max-ziplist-value（默認 64 字節）。
	SKIPLIST	跳躍表 + 字典	不滿足上述條件時，切換為跳躍表和字典。

接下來直接講各種數據結構，即Redis的ptr指針指向的那一部分。

2、簡單動態字符串

2.1 SDS定義

redis中的字符串都是簡單動態字符串（SDS）的形式存在的。不止是set key value的鍵和字符串值value，連其他數據結構中存儲的字符串也是以SDS形式存儲，如rpush fruits "apple " “banana”，隊列保存的中的"apple " "banana"兩個字符串元素也是SDS存儲。

SDS除了保存字符串以外，還用在緩沖區：AOF緩沖區、客戶端輸入輸出緩沖區。

SDS的數據結構：

struct sdshdr {int len;       // 字符串的長度（已使用的字節數）int free;      // 未使用的字節數（空閑空間）char buf[];    // 實際存儲字符串內容的字符數組
};

字段說明：

• len：表示字符串的實際長度（不包括終止符 \0）。允許 O(1) 時間復雜度獲取字符串長度。
• free：表示緩沖區中未使用的字節數。用于優化內存分配和減少頻繁的內存重新分配。
• buf：存儲實際的字符串內容，以 \0 結尾（兼容 C 字符串）。

針對于hello字符串對應的SDS：

len：等于5，因為hello字符串占用了5個字節，\0空字符并不單獨算一個字符，即len、free都不會將其算入在內，\0是SDS函數自動添加的，對用戶是透明的，為了能夠使用c語言的一些函數。
free：等于3，表示buf申請的緩沖區中還有3個字節未使用。

2.2 SDS與C語言的區別

1. 獲取字符串的長度時間復雜度
   因為SDS存儲了字符串的長度，所以時間復雜度為O(1)；而C語言只存儲了字符串本身，所以需要變量整個字符串才知道字符串的長度，時間復雜度為O(N)

2. 杜絕緩沖區溢出
   例如，字符串拼接函數strcat(s1, s2)將字符串s2拼接到s1后面，但是在拼接的時候沒有檢測s1的內存，s1沒有足夠的內存【s1后面存在其他有用的數據s3】，那么拼接就會導致s2會把s3的部分數據給修改了。而SDS空間分配策略就杜絕了這個問題出現。SDS API首先會檢測空間是否滿足，如果不滿足自動的空間擴展。

3. 減少修改字符串導致的重分配次數
   C語言針對于一個長度為N的字符串底層是一個N+1的字符數組，每次修改字符串都需要進行內存重分配。增加字符需要擴展內存【否則，出現內存溢出問題】，減少字符需要釋放內存【否則，出現內存泄漏問題】。執行內存重分配就需要系統調用，比較耗時，而Redis作為存儲設備，字符串變更更是家常便飯。
   Redis通過未使用空間解耦了字符串長度和底層數據之間的綁定關系，通過未使用空間就實現了空間預分配和惰性空間釋放。

4. 二進制安全
   C語言字符串必須符合某種編碼，而且除了字符串的末尾為空字符之外，其他地方不允許有空字符，否則字符串就會提前結束。這就導致C語言只能存儲文本數據，不能保存像圖片、視頻、音頻等二進制數據。而SDS是根據len屬性的長度確定結束，所以沒有上述問題。

5. 兼容部分C語言函數
   雖然SDS是二進制安全的，但是在內存分配和數據存儲的時候都會自動的多分配一個字節用來存儲空字符，這就是為了能直接兼容C語言的部分<string.h>庫上的字符串函數。當然針對于中間有空字符的就不能使用C語言函數。

2.3 SDS的空間分配策略

2.3.1 空間預分配

字符串在增加的時候，SDS API就檢測未使用空間是否滿足，即free >= 待插入字符串的長度，如果滿足，則直接插入；否則出現如下空間預分配策略：

• 如果對字符串修改之后¹ ，SDS的長度【len屬性】小于1M，則程序也會分配同樣大小的未使用內存；
• 如果對字符串修改之后 ，SDS的長度【len屬性】大于1M，則程序針對未使用的內存也只會申請1M的大小

上述分配策略衡量了占用內存和性能，因為字符串都大于1M，再申請一倍的未使用內存，就會占用太多內存。

2.3.2 惰性空間釋放

針對于字符串縮減的時候，SDS并不會將縮減完空余的空間立刻釋放掉，而是會增加free屬性，防止為了以后再增加還需要進行內存重分配。當然，SDS 也提供了能夠釋放未使用空間的API，不會出現內存泄漏問題。

2.4 SDS的API

以下是常見的 SDS API 函數及其功能說明。【插入：一下內容通過AI生成。本人先去百度搜索沒有找到相關內容，并且找到的也不太方便截圖。于是直接使用AI生成，按照符合的語法生成直接負責即可。點贊AI】
1. 創建與銷毀

函數名稱	功能描述	示例代碼
sdsnew	創建一個新的 SDS 字符串，并初始化為指定的 C 字符串。	sds s = sdsnew("hello");
sdsempty	創建一個空的 SDS 字符串。	sds s = sdsempty();
sdsfree	釋放一個 SDS 字符串，回收其占用的內存。	sdsfree(s);
sdsdup	復制一個 SDS 字符串，返回一個新的 SDS 實例。	sds copy = sdsdup(s);

2. 修改與擴展

函數名稱	功能描述	示例代碼
sdscat	將一個 C 字符串追加到 SDS 字符串的末尾。	s = sdscat(s, " world"); // 結果為 "hello world"
sdscatsds	將另一個 SDS 字符串追加到當前 SDS 字符串的末尾。	s = sdscatsds(s1, s2);
sdscpy	將一個 C 字符串復制到 SDS 字符串中，覆蓋原有內容。	s = sdscpy(s, "new string");
sdsgrowzero	擴展 SDS 字符串的長度到指定值，并用 \0 填充新增部分。	sdsgrowzero(s, 20);
sdsMakeRoomFor	為 SDS 字符串分配額外的空間，確保有足夠的緩沖區。	s = sdsMakeRoomFor(s, 100);
sdsRemoveFreeSpace	移除 SDS 字符串的空閑空間，使其占用的內存最小化。	s = sdsRemoveFreeSpace(s);
sdsIncrLen	調整 SDS 字符串的長度，增加或減少已使用的字節數。	sdsIncrLen(s, 5); // 長度增加 5
sdsupdatelen	更新 SDS 字符串的長度字段，通常在手動修改 buf 后調用。	sdsupdatelen(s);

3. 查詢與統計

函數名稱	功能描述	示例代碼
sdslen	返回 SDS 字符串的長度（已使用的字節數）。	size_t len = sdslen(s);
sdsavail	返回 SDS 字符串的空閑空間大小（未使用的字節數）。	size_t avail = sdsavail(s);
sdscmp	比較兩個 SDS 字符串，類似于 C 的 strcmp 函數。	int cmp = sdscmp(s1, s2);

4. 截取與分割

函數名稱	功能描述	示例代碼
sdsrange	截取 SDS 字符串的一部分，范圍為 [start, end]。	sdsrange(s, 0, 4); // 截取前 5 個字符
sdssplitlen	根據指定的分隔符將 SDS 字符串拆分為多個子字符串，返回一個數組。	sds* tokens = sdssplitlen(s, sdslen(s), " ", 1, &count);
sdsjoinsds	將多個 SDS 字符串連接成一個新的 SDS 字符串，使用指定的分隔符。	sds joined = sdsjoinsds(tokens, count, ", ", 2);

5. 其他操作

函數名稱	功能描述	示例代碼
sdsclear	清空 SDS 字符串的內容，將其長度設置為 0，但保留緩沖區。	sdsclear(s);
sdsmapchars	替換 SDS 字符串中的某些字符為其他字符。	sdsmapchars(s, "aeiou", "AEIOU", 5); // 將元音替換為大寫

3、鏈表

由于C語言沒有鏈表數據結構，所以Redis進行自己構建了鏈表。鏈表在Redis中的使用還是很廣的，例如列表的底層就是鏈表【排出壓縮列表的情況】、Redis服務端存儲的客戶端狀態、客戶端的輸出緩沖區、發布訂閱等都用到了鏈表。

3.1 鏈表的定義

鏈表是由一個個鏈表節點串聯組合而成的雙向鏈表，先看下鏈表節點的數據結構：

typedef struct listNode {struct listNode *prev;  // 指向前一個節點，如果當前節點是鏈表的頭節點，則 prev 為 NULL。struct listNode *next;  // 指向下一個節點，如果當前節點是鏈表的尾節點，則 next 為 NULL。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;

針對于列表中的三個函數指針進行詳細介紹，可以自定義下面的函數：

• dup：用于復制鏈表節點的值。
  當需要復制鏈表時（例如深拷貝），Redis 會調用 dup 函數來復制每個節點的值。
  默認行為：如果未設置 dup 函數，則 Redis 不會對節點值進行復制，直接將指針賦值給新節點
• free：用于釋放鏈表節點值占用的內存。
  當刪除鏈表節點或釋放整個鏈表時，Redis 會調用 free 函數來釋放節點值。
  默認行為：如果未設置 free 函數，則 Redis 不會釋放節點值，可能導致內存泄漏。
• 用于比較兩個節點值是否相等。
  當需要查找鏈表中的某個節點時，Redis 會調用 match 函數來比較節點值與目標值。
  默認行為：如果未設置 match 函數，則 Redis 使用指針比較（即比較兩個指針是否相同）。

redis刪除策略【區別于過期策略（惰性策略和定期策略）和淘汰策略（內存不足的時候）】：

• 如果一個key開始指向一個字符串，然后更新一個字符串，會怎么辦？因為字符串底層數據結構是SDS，所以會復用前一個字符串的SDS。
• 如果一個key開始指向一個復雜的數據結構，如列表、哈希，然后更新一個新的，會怎么辦？redis會先遞歸刪除原來的數據，然后講新的賦值給這個key。

以鏈表存儲字符串為例的結構圖：

鏈表的特點：

• 鏈表獲取長度的時間復雜度為O(1)
• 鏈表獲取鏈表頭和尾的時間復雜度為O(1)
• 鏈表獲取前一個節點和后一個節點的時間復雜度為O(1)
• 鏈表不存在環的問題，因為頭節點的head為null，后節點的next也為null
• 多態：鏈表提供了復制dup、刪除free、比較match函數，可以自定義這些函數，所以再復雜的數據結構也OK

3.2 鏈表的API

1. 創建與銷毀

函數名稱	功能描述	示例代碼
listCreate	創建一個新的空鏈表。	list *myList = listCreate();
listRelease	釋放整個鏈表及其所有節點。	listRelease(myList);

2. 添加節點

函數名稱	功能描述	示例代碼
listAddNodeHead	在鏈表頭部添加一個新節點。	listAddNodeHead(myList, "value");
listAddNodeTail	在鏈表尾部添加一個新節點。	listAddNodeTail(myList, "value");
listInsertNode	在指定節點之前或之后插入一個新節點。	listInsertNode(myList, oldNode, "value", 1); // 1 表示在 oldNode 之后插入

3. 刪除節點

函數名稱	功能描述	示例代碼
listDelNode	刪除鏈表中的指定節點。	listDelNode(myList, node);

4. 查找節點

函數名稱	功能描述	示例代碼
listSearchKey	在鏈表中查找值為指定鍵的節點。	listNode *node = listSearchKey(myList, "key");

5. 遍歷鏈表

函數名稱	功能描述	示例代碼
listGetIterator	獲取鏈表的迭代器，支持從頭到尾或從尾到頭遍歷。	listIter *iter = listGetIterator(myList, AL_START_HEAD);
listNext	獲取迭代器指向的下一個節點。	listNode *node = listNext(iter);
listReleaseIterator	釋放鏈表迭代器。	listReleaseIterator(iter);

6. 自定義函數

函數名稱	功能描述	示例代碼
dup	自定義的節點值復制函數，用于深拷貝節點值。	void *myDupFunction(void *ptr) { return strdup((char *)ptr); }
free	自定義的節點值釋放函數，用于釋放節點值占用的內存。	void myFreeFunction(void *ptr) { free(ptr); }
match	自定義的節點值匹配函數，用于比較兩個節點值是否相等。	int myMatchFunction(void *ptr, void *key) { return strcmp((char *)ptr, (char *)key); }

4、字典

4.1 字典的定義

字典和鏈表一樣C語言沒有內置相關數據結構，都是redis自己構建實現的。字典是redis的全局哈希和哈希類型的底層實現。

哈希表的結構定義：

typedef struct dict {dictType *type;          // 類型特定函數，例如鍵、值等的復制、刪除、對比函數或者是計算哈希值的函數void *privdata;          // 私有數據。保存類型特定函數的可選參數dictht ht[2];            // 兩個哈希表（用于漸進式 rehash）。平時一直都是使用ht[0]，只有在哈希表進行擴縮容的時候才會使用ht[1]long rehashidx;          // 當前 rehash 的索引（-1 表示未進行 rehash）unsigned long iterators; // 正在運行的迭代器數量
} dict;typedef struct dictht {dictEntry **table;       // 哈希表數組unsigned long size;      // 哈希表大小unsigned long sizemask;  // 掩碼，用于計算索引。始終是sizemask=size-1，主要是用于計算一個鍵的hash索引unsigned long used;      // 已使用的、存在的鍵值對數量
} dictht;typedef struct dictEntry {void *key;               // 鍵union {void *val;uint64_t u64;int64_t s64;} v;                      // 值，這個值可以是對象或者是uint64_t整數或者是int64_t整數struct dictEntry *next;   // 指向下一個節點（解決沖突），形成鏈表
} dictEntry;

• dict：哈希表的頂層結構，包含兩個哈希表（ht[0] 和 ht[1]），用于支持漸進式 rehash。
• dictht：單個哈希表的結構，包含數組、大小、掩碼和已使用節點數。
• dictEntry：哈希表中的單個節點，包含鍵、值和指向下一個節點的指針。

字典整體的數據結構：

4.2 哈希算法

插入數據的大致流程：

• 通過字典中設置的哈希函數，計算鍵key的哈希值：hash = dict.type.hashFunction(key);
• 計算該鍵值對需要插入的數組索引：index = hash & sizemask;
• 如果table數組的該索引處存在鍵值對，則插入到鏈表的頭部，即頭插法。

redis默認使用的哈希函數是Murmurhash2算法，并且出現沖突、哈希碰撞則使用鏈地址法解決沖突問題。

4.3 哈希表的擴縮

雖然程序的不斷運行，哈希表中的數據會實時的變化，不斷的增加或者減少。為了能過依然保持哈希表的性能和空間優化，會對哈希表進行擴縮，使得負載因子【load factor = used/size】保持在合理返回。

4.3.1 哈希表擴縮的判斷依據

哈希表擴展的情況：

• 當redis正在執行bgsave【rdb持久化】或者bgwriteaof【aof重寫】命令的時候，負載因子大于等于5
• 當redis沒有執行bgsave【rdb持久化】或者bgwriteaof【aof重寫】命令的時候，負載因子大于等于1

哈希表收縮的情況：

• 當負載因子小于0.1

4.3.2 哈希表rehash

• 根據當前ht[0]中鍵值對數量為字典的ht[1]分配空間：

  • 當哈希表進行擴容的時候， ht[1]分配的空間大小為：第一個大于等于的ht[0].used*2的2ⁿ;
  • 當哈希表進行擴容的時候， ht[1]分配的空間大小為：第一個大于等于的ht[0].used的2ⁿ;

• 將ht[0]上的值漸近式的rehash到ht[1]上

• 等ht[0]上的所有鍵值對都遷移到ht[1]上之后，釋放ht[0]，將ht[1]上的哈希表賦值給ht[0]，然后ht[1]創建一個新的哈希表

4.3.2 漸進式rehash

當哈希表需要擴縮容的時候，不可能等到完全將ht[0]中的數據全部遷移到ht[1]之后再對外提供服務，尤其是哈希表中存儲了大量的數據。因為這會導致服務一段時間的不可用，所以使用的是漸進式的、分批次的rehash。

當創建完ht[1]哈希表之后，rehashidx就設置為0。每當redis執行增刪改查的時候，就會將ht[0]哈希表對應的rehashidx索引處的所有鍵值對都遷移rehash到ht[1]上，然后rehashidx加一。直到ht[0]哈希表所有的鍵值對都rehash完成，則rehashidx=-1。

當前在進行rehash期間，redis所有的增刪改查操作會在ht[0]和ht[1]兩個表上進行。例如：查詢是否存在某個鍵的時候，會首先在ht[0]上進行查找，如果ht[0]沒有，還會在ht[1]哈希表上查詢；插入操作則是直接插入到ht[1]上，不會在再ht[0]上進行任何的插入操作。

4.4 字典的API

1. 創建與銷毀

函數名稱	功能描述	示例代碼
dictCreate	創建一個新的空字典。	dict *myDict = dictCreate(&type, NULL);
dictRelease	釋放字典及其所有節點。	dictRelease(myDict);

2. 插入與更新

函數名稱	功能描述	示例代碼
dictAdd	向字典中添加一個新鍵值對。如果鍵已存在，則返回錯誤。	dictAdd(myDict, "key", "value");
dictReplace	向字典中添加或更新一個鍵值對。如果鍵已存在，則更新值；否則插入新鍵值對。	dictReplace(myDict, "key", "new_value");
dictSet	設置字典中的鍵值對（類似于 dictReplace）。	dictSet(myDict, "key", "value");

3. 刪除

函數名稱	功能描述	示例代碼
dictDelete	從字典中刪除指定鍵的鍵值對。	dictDelete(myDict, "key");
dictDeleteNoFree	從字典中刪除指定鍵的鍵值對，但不釋放鍵和值的內存。	dictDeleteNoFree(myDict, "key");

4. 查找

函數名稱	功能描述	示例代碼
dictFind	在字典中查找指定鍵的節點。	dictEntry *entry = dictFind(myDict, "key");
dictFetchValue	獲取指定鍵對應的值。	void *value = dictFetchValue(myDict, "key");

5. 遍歷

函數名稱	功能描述	示例代碼
dictGetIterator	獲取字典的迭代器，用于遍歷所有鍵值對。	dictIterator *iter = dictGetIterator(myDict);
dictNext	獲取迭代器指向的下一個節點。	dictEntry *entry = dictNext(iter);
dictReleaseIterator	釋放字典迭代器。	dictReleaseIterator(iter);

6. 其他操作

函數名稱	功能描述	示例代碼
dictExpand	擴展字典的大小（通常用于優化性能）。	dictExpand(myDict, new_size);
dictRehash	手動觸發 rehash 操作（將舊哈希表遷移到新哈希表）。	dictRehash(myDict, n); // 遷移 n 個桶
dictGetHashTableSize	獲取字典當前哈希表的大小。	unsigned long size = dictGetHashTableSize(myDict);
dictGetHashKey	獲取字典節點的鍵。	void *key = dictGetHashKey(entry);
dictGetHashVal	獲取字典節點的值。	void *value = dictGetHashVal(entry);

5、跳躍表

跳躍表是一個有序的數據結構，大部分情況下可以與平衡樹相媲美，卻比平衡數簡單。那么為什么mysql不使用跳躍表呢？【跳躍表一般層級比較深相比于平衡樹，對于磁盤讀取影響比較大，而內存無關緊要】。跳躍表是有序集合的底層實現。

5.1 跳躍表的實現

跳躍表節點的數據結構：

typedef struct zskiplistNode {sds o;                      // 元素值（字符串）double score;                 // 分值，用于排序struct zskiplistNode *backward; // 指向前一個節點（僅在第一層有效）struct zskiplistLevel {struct zskiplistNode *forward; // 指向同一層的下一個節點unsigned long span;           // 到下一個節點的跨度（跨越的節點數），這樣在便利得到某個元素的時候就可以通過span之后得到排名。例如o2的排名等于1+1} level[];                     // 多層索引
} zskiplistNode;

跳躍表的數據結構：

typedef struct zskiplist {struct zskiplistNode *header; // 跳躍表頭節點struct zskiplistNode *tail;   // 跳躍表尾節點unsigned long length;         // 跳躍表中節點的數量int level;                    // 跳躍表的最大層數，表頭的層數不算
} zskiplist;

圖形化：

5.2 跳躍表的API

1. 創建與銷毀

函數名稱	功能描述	示例代碼
zslCreate	創建一個新的空跳躍表。	zskiplist *zsl = zslCreate();
zslFree	釋放跳躍表及其所有節點。	zslFree(zsl);

2. 插入

函數名稱	功能描述	示例代碼
zslInsert	向跳躍表中插入一個新節點，按照分值排序。	c zskiplistNode *node = zslInsert(zsl, score, ele);

3. 刪除

函數名稱	功能描述	示例代碼
zslDelete	從跳躍表中刪除指定分值和元素值的節點。	int deleted = zslDelete(zsl, score, ele, &node);
zslDeleteRangeByScore	刪除分值范圍內的所有節點。	zslDeleteRangeByScore(zsl, min, max, dict);
zslDeleteRangeByRank	刪除排名范圍內的所有節點。	zslDeleteRangeByRank(zsl, start, end, dict);

4. 查找

函數名稱	功能描述	示例代碼
zslGetElementByRank	根據排名查找節點。	zskiplistNode *node = zslGetElementByRank(zsl, rank);
zslIsInRange	檢查分值是否在跳躍表的范圍內。	int inRange = zslIsInRange(zsl, range);
zslFirstInRange	返回分值范圍內的第一個節點。	zskiplistNode *node = zslFirstInRange(zsl, range);
zslLastInRange	返回分值范圍內的最后一個節點。	zskiplistNode *node = zslLastInRange(zsl, range);

5. 遍歷

函數名稱	功能描述	示例代碼
zslGetRank	獲取指定分值和元素值的節點的排名（從 1 開始）。	unsigned long rank = zslGetRank(zsl, score, ele);

6. 輔助函數

函數名稱	功能描述	示例代碼
zslRandomLevel	隨機生成節點的層數。	int level = zslRandomLevel();

6、整數集合

整數集合是集合的底層實現之一。當集合中元素都為整數并且數量不多的時候就會使用整數集合。

6.1 整數集合定義

數據結構定義：

typedef struct intset {uint32_t encoding;  // 編碼方式，決定存儲的整數類型uint32_t length;    // 集合中元素的數量int8_t contents[]; // 動態數組，用于存儲整數
} intset;

• encoding 字段：表示當前整數集合使用的編碼方式，決定了每個元素占用的字節數：
  • INTSET_ENC_INT16：每個元素占用 2 字節（int16_t）。
  • INTSET_ENC_INT32：每個元素占用 4 字節（int32_t）。
  • INTSET_ENC_INT64：每個元素占用 8 字節（int64_t）。
    當插入一個超出當前編碼范圍的整數時，Redis 會升級編碼方式（例如從 INTSET_ENC_INT16 升級到 INTSET_ENC_INT32），并重新分配內存。
• length 字段：表示當前集合中元素的數量。
• contents 數組：存儲集合中的所有整數，按從小到大的順序排列。
  由于整數集合是有序的，查找操作可以通過二分查找實現，時間復雜度為 O(log N)。
  

每次插入數據或者刪除數據都會根據二分法進行查找，找到合適位置插入或者找到值進行刪除，后續元素向前填充。

數組擴容情況：

• 申請的數組也是動態的，即開始有個初始容量，當數組不足以繼續插入的時候就會擴容，以二倍速度進行擴容。
• 編碼升級，例如當前編碼為INTSET_ENC_INT16類型，但是插入了一個超過這個容量的數據，則會升級為合適的類型，重新分配內存進行遷移。這個擴容是不可逆的

整數數組只能進行升級不能進行降級。例如整數數組開始都是INTSET_ENC_INT16，增加了一個INTSET_ENC_INT32類型的整數，這個時候整個數組都會升級為INTSET_ENC_INT32類型，即已經存在的原本為INTSET_ENC_INT16類型的整數也轉換為INTSET_ENC_INT32類型。當新增的INTSET_ENC_INT32的那個整數刪除，其余原本為INTSET_ENC_INT16類型的整數升級之后也不能降級。

6.2 整數集合API

功能分類	API 名稱	功能描述	示例代碼
創建與初始化	intsetNew	創建一個新的空整數集合。	iintsetNew();
插入操作	intsetAdd	向整數集合中插入一個新元素。	intsetAdd(is, 100, &success);
刪除操作	intsetRemove	從整數集合中刪除一個指定的元素。	intsetRemove(is, 100, &success);
查找操作	intsetFind	檢查整數集合中是否存在指定的元素。	intsetFind(is, 100)
獲取元素	intsetGet	獲取整數集合中指定位置的元素。	intsetGet(is, 0, &value))
集合長度	intsetLen	獲取整數集合中元素的數量。	intsetLen(is);
內存大小	intsetBlobLen	獲取整數集合占用的內存大小（字節數）。	intsetBlobLen(is);
編碼相關	intsetGetEncoding	獲取整數集合當前使用的編碼方式。	intsetGetEncoding(is);
其他操作	intsetResize	調整整數集合的容量。	（通常由 Redis 內部調用，用戶一般不需要直接使用）
其他操作	intsetUpgradeAndAdd	升級整數集合的編碼方式并插入新元素。	（通常由 Redis 內部調用，用戶一般不需要直接使用）
銷毀操作	intsetDestroy	釋放整數集合占用的內存。	intsetDestroy(is);

7、壓縮列表

壓縮列表是列表、有序集合、哈希的底層實現，前提是滿足數量不太多并且單個元素不大的情況下。

7.1 壓縮列表定義

Ziplist 是一個連續的字節數組，其結構如下：

<zlbytes> <zltail> <zllen> <entry1> <entry2> ... <entryN> <zlend>

字段名	長度（字節）	描述
zlbytes	4	整個 Ziplist 占用的字節數（包括自身）。
zltail	4	指向最后一個元素的偏移量（從 Ziplist 起始位置開始計算），用于快速定位尾部元素。
zllen	2	Ziplist 中的元素數量。如果元素數量超過 2^16-1，則需要遍歷整個 Ziplist 來計算實際數量。
entry	X	可變 實際存儲的元素，每個元素由元數據和數據組成。
zlend	1	標志 Ziplist 結束的特殊字節，固定為 0xFF。

每個Entry的數據結構：

<prevlen> <encoding> <data>

字段名	描述
prevlen	前一個元素的長度（用于反向遍歷）。如果前一個元素長度小于 254 字節，則占 1 字節。 如果前一個元素長度大于等于 254 字節，則占 5 字節（第 1 字節為 0xFE，后 4 字節存儲實際長度）。
encoding	數據的編碼方式，表示當前元素的類型和長度。小整數或短字符串可以直接嵌入到編碼中。較長的字符串或大整數需要額外的長度描述。
data	實際存儲的數據內容，可能是字符串或整數。

連鎖更新：
壓縮列表是連續的內存，所以每次插入元素都會重新分配內存，然后數據遷移。通過上面prevlen字段的說明，根據前一個長度的大小決定這個字段的長度。例如目前所有元素大小都是253，當新增一個元素插入在第一個位置，大小大于254。那么第二個元素大小就會超過254【因為第二個元素的prevlen字段從占用1個字節變成占用5個字節】，同樣也會導致第三個元素超過254，以此類推下去。

哈希類型滿足一定條件也可以存儲為壓縮列表，可是哈希是鍵值對的形式存在的，是怎么存儲到壓縮列表中的呢？哈希鍵值對按照k1 v1 k2 v2順序存儲到壓縮列表，每個key、每個value都是一個獨立的entry，當進行讀取數據的時候，每次會讀取兩個壓縮節點。

7.2 壓縮列表的API

以下是 Redis 中壓縮列表（Ziplist）相關的 API，以 Markdown 表格形式排版。

功能分類	API 名稱	功能描述	示例代碼
創建與初始化	ziplistNew	創建一個新的空壓縮列表。	ziplistNew();
插入操作	ziplistPush	向壓縮列表的頭部或尾部插入一個新元素。	ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_TAIL);
刪除操作	ziplistDelete	刪除壓縮列表中指定位置的元素。	unsigned char *p = ziplistIndex(zl, 0); zl = ziplistDelete(zl, &p);
查找操作	ziplistFind	在壓縮列表中查找指定的值。	ziplistFind(zl, ziplistIndex(zl, 0), (unsigned char*)"hello", 5, 0);
獲取元素	ziplistIndex	獲取壓縮列表中指定索引位置的元素。	ziplistIndex(zl, 0);
遍歷元素	ziplistNext	獲取當前元素的下一個元素。	ziplistNext(zl, p);
遍歷元素	ziplistPrev	獲取當前元素的上一個元素。	ziplistPrev(zl, p);
獲取值	ziplistGet	獲取壓縮列表中指定位置的值。	unsigned char *sval; unsigned int slen; long lval; ziplistGet(p, &sval, &slen, &lval);
集合長度	ziplistLen	獲取壓縮列表中元素的數量。	ziplistLen(zl);
內存大小	ziplistBlobLen	獲取壓縮列表占用的內存大小（字節數）。	ziplistBlobLen(zl);
銷毀操作	ziplistDeleteRange	刪除壓縮列表中指定范圍的元素。	ziplistDeleteRange(zl, 0, 2);
其他操作	ziplistCompare	比較壓縮列表中指定位置的值是否等于給定值。	iziplistCompare(p, (unsigned char*)"hello", 5))
其他操作	ziplistIncrRefCount	增加壓縮列表的引用計數（用于共享壓縮列表）。	（通常由 Redis 內部調用，用戶一般不需要直接使用）
其他操作	ziplistRelease	釋放壓縮列表占用的內存。	ziplistRelease(zl);

---

1. 為什么強調對字符串修改之后的長度呢，為了防止原來字符串長度為1K，但是一下子拼接一個2M的字符串而導致的頻繁申請內存。 ??