點擊上方?好好學(xué)java?，選擇?星標(biāo)?公眾號

重磅資訊、干貨，第一時間送達(dá)

今日推薦：硬剛一周，3W字總結(jié)，一年的經(jīng)驗告訴你如何準(zhǔn)備校招！

個人原創(chuàng)100W+訪問量博客：點擊前往，查看更多

轉(zhuǎn)自：伍陸七，

鏈接：cnblogs.com/chentianming/p/13838347.html

Redis 是一個基于內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)存儲系統(tǒng)，可以用作數(shù)據(jù)庫、緩存和消息中間件。Redis 支持五種常見對象類型：字符串（String）、哈希（Hash）、列表（List）、集合（Set）以及有序集合（Zset），我們在日常工作中也會經(jīng)常使用它們。知其然，更要知其所以然，本文將會帶你讀懂這五種常見對象類型的底層數(shù)據(jù)結(jié)構(gòu)。

本文主要內(nèi)容參考自《Redis設(shè)計與實現(xiàn)》

1. 對象類型和編碼

Redis 使用對象來存儲鍵和值的，在Redis中，每個對象都由 redisObject 結(jié)構(gòu)表示。redisObject 結(jié)構(gòu)主要包含三個屬性：type、encoding 和 ptr。

typedef struct redisObject {// 類型unsigned type:4;// 編碼unsigned encoding:4;// 底層數(shù)據(jù)結(jié)構(gòu)的指針void *ptr; } robj;

其中 type 屬性記錄了對象的類型。對于 Redis 來說，鍵對象總是字符串類型，值對象可以是任意支持的類型。因此，當(dāng)我們說 Redis 鍵采用哪種對象類型的時候，指的是對應(yīng)的值采用哪種對象類型。

*ptr 屬性指向了對象的底層數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)由 encoding 屬性決定。

之所以由 encoding 屬性來決定對象的底層數(shù)據(jù)結(jié)構(gòu)，是為了實現(xiàn)同一對象類型，支持不同的底層實現(xiàn)。這樣就能在不同場景下，使用不同的底層數(shù)據(jù)結(jié)構(gòu)，進(jìn)而極大提升Redis的靈活性和效率。

底層數(shù)據(jù)結(jié)構(gòu)后面會詳細(xì)講解，這里簡單看一下即可。

2. 字符串對象

字符串是我們?nèi)粘９ぷ髦杏玫米疃嗟膶ο箢愋?#xff0c;它對應(yīng)的編碼可以是 int、raw 和 embstr。字符串對象相關(guān)命令可參考：Redis命令-Strings。

如果一個字符串對象保存的是不超過 long 類型的整數(shù)值，此時編碼類型即為 int，其底層數(shù)據(jù)結(jié)構(gòu)直接就是 long 類型。例如執(zhí)行 set number 10086，就會創(chuàng)建 int 編碼的字符串對象作為 number 鍵的值。

如果字符串對象保存的是一個長度大于 39 字節(jié)的字符串，此時編碼類型即為 raw，其底層數(shù)據(jù)結(jié)構(gòu)是簡單動態(tài)字符串（SDS）；如果長度小于等于 39 個字節(jié)，編碼類型則為 embstr，底層數(shù)據(jù)結(jié)構(gòu)就是 embstr 編碼 SDS。下面，我們詳細(xì)理解下什么是簡單動態(tài)字符串。

2.1 簡單動態(tài)字符串

SDS 定義

在 Redis 中，使用 sdshdr 數(shù)據(jù)結(jié)構(gòu)表示 SDS：

struct sdshdr {// 字符串長度int len;// buf數(shù)組中未使用的字節(jié)數(shù)int free;// 字節(jié)數(shù)組，用于保存字符串char buf[]; };

SDS 遵循了 C 字符串以空字符結(jié)尾的慣例，保存空字符的 1 字節(jié)不會計算在 len 屬性里面。例如，Redis 這個字符串在 SDS 里面的數(shù)據(jù)可能是如下形式：

SDS 與 C 字符串的區(qū)別

C 語言使用長度為 N+1 的字符數(shù)組來表示長度為N的字符串，并且字符串的最后一個元素是空字符 \0。Redis 采用 SDS 相對于 C 字符串有如下幾個優(yōu)勢：

常數(shù)復(fù)雜度獲取字符串長度；

杜絕緩沖區(qū)溢出；

減少修改字符串時帶來的內(nèi)存重分配次數(shù)；

二進(jìn)制安全。

常數(shù)復(fù)雜度獲取字符串長度

因為 C 字符串并不記錄自身的長度信息，所以為了獲取字符串的長度，必須遍歷整個字符串，時間復(fù)雜度是 O(N)。而 SDS 使用 len 屬性記錄了字符串的長度，因此獲取 SDS字符串長度的時間復(fù)雜度是 O(1)。

杜絕緩沖區(qū)溢出

C 字符串不記錄自身長度帶來的另一個問題是，很容易造成緩存區(qū)溢出。比如使用字符串拼接函數(shù)（stract）的時候，很容易覆蓋掉字符數(shù)組原有的數(shù)據(jù)。

與 C 字符串不同，SDS 的空間分配策略完全杜絕了發(fā)生緩存區(qū)溢出的可能性。當(dāng) SDS 進(jìn)行字符串?dāng)U充時，首先會檢查當(dāng)前的字節(jié)數(shù)組的長度是否足夠。如果不夠的話，會先進(jìn)行自動擴容，然后再進(jìn)行字符串操作。

減少修改字符串時帶來的內(nèi)存重分配次數(shù)

因為 C 字符串的長度和底層數(shù)據(jù)是緊密關(guān)聯(lián)的，所以每次增長或者縮短一個字符串，程序都要對這個數(shù)組進(jìn)行一次內(nèi)存重分配：

• 如果是增長字符串操作，需要先通過內(nèi)存重分配來擴展底層數(shù)組空間大小，不這么做就導(dǎo)致緩存區(qū)溢出；

• 如果是縮短字符串操作，需要先通過內(nèi)存重分配來來回收不再使用的空間，不這么做就導(dǎo)致內(nèi)存泄漏。

因為內(nèi)存重分配涉及復(fù)雜的算法，并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以通常是個比較耗時的操作。對于 Redis 來說，字符串修改是一個十分頻繁的操作。如果每次都像 C 字符串那樣進(jìn)行內(nèi)存重分配，對性能影響太大了，顯然是無法接受的。

SDS 通過空閑空間解除了字符串長度和底層數(shù)據(jù)之間的關(guān)聯(lián)。在 SDS 中，數(shù)組中可以包含未使用的字節(jié)，這些字節(jié)數(shù)量由 free 屬性記錄。通過空閑空間，SDS 實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

1. 空間預(yù)分配

空間預(yù)分配是用于優(yōu)化 SDS 字符串增長操作的，簡單來說就是當(dāng)字節(jié)數(shù)組空間不足觸發(fā)重分配的時候，總是會預(yù)留一部分空閑空間。這樣的話，就能減少連續(xù)執(zhí)行字符串增長操作時的內(nèi)存重分配次數(shù)。

有兩種預(yù)分配的策略：

• len 小于 1MB 時：每次重分配時會多分配同樣大小的空閑空間；
  

• len 大于等于 1MB 時：每次重分配時會多分配 1MB 大小的空閑空間。
  

2. 惰性空間釋放

惰性空間釋放是用于優(yōu)化 SDS 字符串縮短操作的。簡單來說就是當(dāng)字符串縮短時，并不立即使用內(nèi)存重分配來回收多出來的字節(jié)，而是用 free 屬性記錄，等待將來使用。SDS 也提供直接釋放未使用空間的 API，在需要的時候，也能真正的釋放掉多余的空間。

二進(jìn)制安全

C 字符串中的字符必須符合某種編碼，并且除了字符串末尾之外，其它位置不允許出現(xiàn)空字符。這些限制使得 C 字符串只能保存文本數(shù)據(jù)。

但是對于 Redis 來說，不僅僅需要保存文本，還要支持保存二進(jìn)制數(shù)據(jù)。為了實現(xiàn)這一目標(biāo)，SDS 的 API 全部做到了二進(jìn)制安全（binary-safe）。

2.2 raw 和 embstr 編碼的 SDS 區(qū)別

我們在前面講過，長度大于 39 字節(jié)的字符串，編碼類型為 raw，底層數(shù)據(jù)結(jié)構(gòu)是簡單動態(tài)字符串（SDS）。這個很好理解，比如當(dāng)我們執(zhí)行 set story "Long, long, long ago there lived a king ..."（長度大于39）之后，Redis 就會創(chuàng)建一個 raw 編碼的 String 對象。

數(shù)據(jù)結(jié)構(gòu)如下：

長度小于等于 39 個字節(jié)的字符串，編碼類型為 embstr，底層數(shù)據(jù)結(jié)構(gòu)則是 embstr 編碼 SDS。embstr 編碼是專門用來保存短字符串的，它和 raw 編碼最大的不同在于：raw 編碼會調(diào)用兩次內(nèi)存分配分別創(chuàng)建 redisObject 結(jié)構(gòu)和 sdshdr 結(jié)構(gòu)；而 embstr 編碼則是只調(diào)用一次內(nèi)存分配，在一塊連續(xù)的空間上同時包含 redisObject 結(jié)構(gòu)和 sdshdr 結(jié)構(gòu)。

2.3 編碼轉(zhuǎn)換

int 編碼和 embstr 編碼的字符串對象在條件滿足的情況下會自動轉(zhuǎn)換為 raw 編碼的字符串對象。

對于 int 編碼來說，當(dāng)我們修改這個字符串為不再是整數(shù)值的時候，此時字符串對象的編碼就會從 int 變?yōu)?raw。

對于 embstr 編碼來說，只要我們修改了字符串的值，此時字符串對象的編碼就會從 embstr 變?yōu)?raw。

embstr 編碼的字符串對象可以認(rèn)為是只讀的，因為 Redis 為其編寫任何修改程序。當(dāng)我們要修改 embstr 編碼字符串時，都是先將轉(zhuǎn)換為 raw 編碼，然后再進(jìn)行修改。

3. 列表對象

列表對象的編碼可以是 linkedlist 或者 ziplist，對應(yīng)的底層數(shù)據(jù)結(jié)構(gòu)是鏈表和壓縮列表。列表對象相關(guān)命令可參考：Redis 命令-List。

默認(rèn)情況下，當(dāng)列表對象保存的所有字符串元素的長度都小于 64 字節(jié)，且元素個數(shù)小于 512 個時，列表對象采用的是 ziplist 編碼，否則使用 linkedlist 編碼。

可以通過配置文件修改該上限值。

3.1 鏈表

鏈表是一種非常常見的數(shù)據(jù)結(jié)構(gòu)，提供了高效的節(jié)點重排能力以及順序性的節(jié)點訪問方式。在 Redis 中，每個鏈表節(jié)點使用 listNode 結(jié)構(gòu)表示：

typedef struct listNode {// 前置節(jié)點struct listNode *prev;// 后置節(jié)點struct listNode *next;// 節(jié)點值void *value; } listNode

多個 listNode 通過 prev 和 next 指針組成雙端鏈表，如下圖所示：

為了操作起來比較方便，Redis 使用了 list 結(jié)構(gòu)持有鏈表。

typedef struct list {// 表頭節(jié)點listNode *head;// 表尾節(jié)點listNode *tail;// 鏈表包含的節(jié)點數(shù)量unsigned long len;// 節(jié)點復(fù)制函數(shù)void *(*dup)(void *ptr);// 節(jié)點釋放函數(shù)void (*free)(void *ptr);// 節(jié)點對比函數(shù)int (*match)(void *ptr, void *key); } list;

list 結(jié)構(gòu)為鏈表提供了表頭指針 head、表尾指針 tail，以及鏈表長度計數(shù)器 len，而 dup、free 和 match 成員則是實現(xiàn)多態(tài)鏈表所需類型的特定函數(shù)。

Redis 鏈表實現(xiàn)的特征總結(jié)如下：

雙端：鏈表節(jié)點帶有 prev 和 next 指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復(fù)雜度都是 O(n)；

無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為終點；

帶表頭指針和表尾指針：通過 list 結(jié)構(gòu)的 head 指針和 tail 指針，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復(fù)雜度為 O(1)；

帶鏈表長度計數(shù)器：程序使用 list 結(jié)構(gòu)的 len 屬性來對 list 持有的節(jié)點進(jìn)行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的復(fù)雜度為 O(1)；

多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，可以保存各種不同類型的值。

3.2 壓縮列表

壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現(xiàn)之一。壓縮列表主要目的是為了節(jié)約內(nèi)存，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個壓縮列表可以包含任意多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。

如上圖所示，壓縮列表記錄了各組成部分的類型、長度以及用途。

4. 哈希對象

哈希對象的編碼可以是 ziplist 或者 hashtable。

4.1 hash-ziplist

ziplist 底層使用的是壓縮列表實現(xiàn)，上文已經(jīng)詳細(xì)介紹了壓縮列表的實現(xiàn)原理。每當(dāng)有新的鍵值對要加入哈希對象時，先把保存了鍵的節(jié)點推入壓縮列表表尾，然后再將保存了值的節(jié)點推入壓縮列表表尾。比如，我們執(zhí)行如下三條 HSET 命令：

HSET profile name "tom" HSET profile age 25 HSET profile career "Programmer"

如果此時使用 ziplist 編碼，那么該 Hash 對象在內(nèi)存中的結(jié)構(gòu)如下：

3.2 hash-hashtable

hashtable 編碼的哈希對象使用字典作為底層實現(xiàn)。字典是一種用于保存鍵值對的數(shù)據(jù)結(jié)構(gòu)，Redis 的字典使用哈希表作為底層實現(xiàn)，一個哈希表里面可以有多個哈希表節(jié)點，每個哈希表節(jié)點保存的就是一個鍵值對。

3.3 哈希表

Redis 使用的哈希表由 dictht 結(jié)構(gòu)定義：

typedef struct dictht{// 哈希表數(shù)組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計算索引值// 總是等于 size-1unsigned long sizemask;// 該哈希表已有節(jié)點數(shù)量unsigned long used; } dictht

table 屬性是一個數(shù)組，數(shù)組中的每個元素都是一個指向 dictEntry 結(jié)構(gòu)的指針，每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對。

size 屬性記錄了哈希表的大小，即 table 數(shù)組的大小。used 屬性記錄了哈希表目前已有節(jié)點數(shù)量。sizemask 總是等于 size-1，這個值主要用于數(shù)組索引。

比如下圖展示了一個大小為 4 的空哈希表。

哈希表節(jié)點

哈希表節(jié)點使用 dictEntry 結(jié)構(gòu)表示，每個 dictEntry 結(jié)構(gòu)都保存著一個鍵值對：

typedef struct dictEntry {// 鍵void *key;// 值union {void *val;unit64_t u64;nit64_t s64;} v;// 指向下一個哈希表節(jié)點，形成鏈表struct dictEntry *next; } dictEntry;

key 屬性保存著鍵值對中的鍵，而 v 屬性則保存了鍵值對中的值。值可以是一個指針，一個 uint64_t 整數(shù)或者是 int64_t 整數(shù)。next 屬性指向了另一個 dictEntry 節(jié)點，在數(shù)組桶位相同的情況下，將多個 dictEntry 節(jié)點串聯(lián)成一個鏈表，以此來解決鍵沖突問題（鏈地址法）。

3.4 字典

Redis 字典由 dict 結(jié)構(gòu)表示：

typedef?struct?dict?{// 類型特定函數(shù)dictType *type;// 私有數(shù)據(jù)void *privdata;// 哈希表dictht ht[2];//rehash索引// 當(dāng)rehash不在進(jìn)行時，值為-1int rehashidx; }

ht 是大小為 2，且每個元素都指向 dictht 哈希表。一般情況下，字典只會使用 ht[0] 哈希表，ht[1] 哈希表只會在對 ht[0] 哈希表進(jìn)行 rehash 時使用。rehashidx 記錄了 rehash 的進(jìn)度，如果目前沒有進(jìn)行 rehash，值為 -1。

rehash

為了使 hash 表的負(fù)載因子 (ht[0]).used/ht[0]).size) 維持在一個合理范圍，當(dāng)哈希表保存的元素過多或者過少時，程序需要對 hash 表進(jìn)行相應(yīng)的擴展和收縮。

rehash（重新散列）操作就是用來完成 hash 表的擴展和收縮的。

rehash 的步驟如下：

1. 為 ht [1] 哈希表分配空間；

• 如果是擴展操作，那么 ht[1] 的大小為第一個大于 ht[0].used*2的2n。比如ht[0].used=5，那么此時 ht[1] 的大小就為 16（大于 10 的第一個 2n 的值是 16）；
  

• 如果是收縮操作，那么 ht[1] 的大小為第一個大于 ht[0].used 的 2n。比如ht[0].used=5，那么此時 ht[1] 的大小就為 8（大于 5 的第一個 2n 的值是 8）。
  

2. 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 中；

3. 遷移完成之后，釋放掉 ht[0]，并將現(xiàn)在的 ht[1] 設(shè)置為 ht[0]，在 ht[1] 新創(chuàng)建一個空白哈希表，為下一次 rehash 做準(zhǔn)備。

哈希表的擴展和收縮時機

• 當(dāng)服務(wù)器沒有執(zhí)行 BGSAVE 或者 BGREWRITEAOF 命令時，負(fù)載因子大于等于 1 觸發(fā)哈希表的擴展操作；

• 當(dāng)服務(wù)器在執(zhí)行 BGSAVE 或者 BGREWRITEAOF 命令，負(fù)載因子大于等于 5 觸發(fā)哈希表的擴展操作；

• 當(dāng)哈希表負(fù)載因子小于 0.1，觸發(fā)哈希表的收縮操作。

漸進(jìn)式 rehash

前面講過，擴展或者收縮需要將 ht[0] 里面的元素全部 rehash 到 ht[1] 中，如果 ht[0] 元素很多，顯然一次性 rehash 成本會很大，從影響到 Redis 性能。

為了解決上述問題，Redis 使用了漸進(jìn)式 rehash 技術(shù)，具體來說就是分多次，漸進(jìn)式地將 ht[0] 里面的元素慢慢地 rehash 到 ht[1] 中。

下面是漸進(jìn)式 rehash 的詳細(xì)步驟：

為 ht[1] 分配空間；

在字典中維持一個索引計數(shù)器變量 rehashidx，并將它的值設(shè)置為 0，表示 rehash 正式開始；

在 rehash 進(jìn)行期間，每次對字典執(zhí)行添加、刪除、查找或者更新時，除了會執(zhí)行相應(yīng)的操作之外，還會順帶將 ht[0] 在 rehashidx 索引位上的所有鍵值對 rehash 到 ht[1] 中，rehash 完成之后，rehashidx 值加 1；

隨著字典操作的不斷進(jìn)行，最終會在啊某個時刻遷移完成，此時將 rehashidx 值置為 -1，表示 rehash 結(jié)束。

漸進(jìn)式 rehash 一次遷移一個桶上所有的數(shù)據(jù)。設(shè)計上采用分而治之的思想，將原本集中式的操作分散到每個添加、刪除、查找和更新操作上，從而避免集中式 rehash 帶來的龐大計算。

因為在漸進(jìn)式 rehash 時，字典會同時使用 ht[0] 和 ht[1] 兩張表，所以此時對字典的刪除、查找和更新操作都可能會在兩個哈希表進(jìn)行。比如，如果要查找某個鍵時，先在 ht[0] 中查找，如果沒找到，則繼續(xù)到 ht[1] 中查找。

hash 對象中的 hashtable

HSET profile name "tom" HSET profile age 25 HSET profile career "Programmer"

還是上述三條命令，保存數(shù)據(jù)到 Redis 的哈希對象中，如果采用 hashtable 編碼保存的話，那么該 Hash 對象在內(nèi)存中的結(jié)構(gòu)如下：

當(dāng)哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于 64 個字節(jié)，并且數(shù)量小于 512 個時，使用 ziplist 編碼，否則使用 hashtable 編碼。

可以通過配置文件修改該上限值。

4. 集合對象

集合對象的編碼可以是 intset 或者 hashtable。當(dāng)集合對象保存的元素都是整數(shù)，并且個數(shù)不超過 512 個時，使用 intset 編碼，否則使用 hashtable 編碼。

4.1 set-intset

intset 編碼的集合對象底層使用整數(shù)集合實現(xiàn)。

整數(shù)集合（intset）是 Redis 用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，它可以保存類型為 int16_t、int32_t 或者 int64_t 的整數(shù)值，并且保證集合中的數(shù)據(jù)不會重復(fù)。Redis 使用 intset 結(jié)構(gòu)表示一個整數(shù)集合。

typedef struct intset {// 編碼方式uint32_t encoding;// 集合包含的元素數(shù)量uint32_t length;// 保存元素的數(shù)組int8_t contents[]; } intset;

contents 數(shù)組是整數(shù)集合的底層實現(xiàn)：整數(shù)集合的每個元素都是 contents 數(shù)組的一個數(shù)組項，各個項在數(shù)組中按值大小從小到大有序排列，并且數(shù)組中不包含重復(fù)項。

雖然 contents 屬性聲明為 int8_t 類型的數(shù)組，但實際上，contents 數(shù)組不保存任何 int8_t 類型的值，數(shù)組中真正保存的值類型取決于 encoding。

如果 encoding 屬性值為 INTSET_ENC_INT16，那么 contents 數(shù)組就是 int16_t 類型的數(shù)組，以此類推。

當(dāng)新插入元素的類型比整數(shù)集合現(xiàn)有類型元素的類型大時，整數(shù)集合必須先升級，然后才能將新元素添加進(jìn)來。這個過程分以下三步進(jìn)行：

根據(jù)新元素類型，擴展整數(shù)集合底層數(shù)組空間大小；

將底層數(shù)組現(xiàn)有所有元素都轉(zhuǎn)換為與新元素相同的類型，并且維持底層數(shù)組的有序性；

將新元素添加到底層數(shù)組里面。

還有一點需要注意的是，整數(shù)集合不支持降級。一旦對數(shù)組進(jìn)行了升級，編碼就會一直保持升級后的狀態(tài)。

舉個例子，當(dāng)執(zhí)行 SADD numbers 1 3 5 向集合對象插入數(shù)據(jù)時，該集合對象在內(nèi)存的結(jié)構(gòu)如下：

4.2 set-hashtable

hashtable 編碼的集合對象使用字典作為底層實現(xiàn)。字典的每個鍵都是一個字符串對象，每個字符串對象對應(yīng)一個集合元素，字典的值都是 NULL。

當(dāng)我們執(zhí)行 SADD fruits "apple" "banana" "cherry" 向集合對象插入數(shù)據(jù)時，該集合對象在內(nèi)存的結(jié)構(gòu)如下：

5. 有序集合對象

有序集合的編碼可以是 ziplist 或者 skiplist。當(dāng)有序集合保存的元素個數(shù)小于 128 個，且所有元素成員長度都小于 64 字節(jié)時，使用 ziplist 編碼，否則使用 skiplist 編碼。

5.1 zset-ziplist

ziplist 編碼的有序集合使用壓縮列表作為底層實現(xiàn)。每個集合元素使用兩個緊挨著一起的兩個壓縮列表節(jié)點表示，第一個節(jié)點保存元素的成員（member），第二個節(jié)點保存元素的分值（score）。

壓縮列表內(nèi)的集合元素按照分值從小到大排列。如果我們執(zhí)行 ZADD price 8.5 apple 5.0 banana 6.0 cherry 命令向有序集合插入元素，該有序集合在內(nèi)存中的結(jié)構(gòu)如下：

5.2 zset-skiplist

skiplist 編碼的有序集合對象使用 zset 結(jié)構(gòu)作為底層實現(xiàn)，一個 zset 結(jié)構(gòu)同時包含一個字典和一個跳躍表。

typedef struct zset {zskiplist *zs1;dict *dict; }

繼續(xù)介紹之前，我們先了解一下什么是跳躍表。

跳躍表

跳躍表（skiplist）是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。

Redis 的跳躍表由 zskiplistNode 和 zskiplist 兩個結(jié)構(gòu)定義。zskiplistNode 結(jié)構(gòu)表示跳躍表節(jié)點，zskiplist 保存跳躍表節(jié)點相關(guān)信息，比如節(jié)點的數(shù)量，以及指向表頭和表尾節(jié)點的指針等。

跳躍表節(jié)點 zskiplistNode

跳躍表節(jié)點 zskiplistNode 結(jié)構(gòu)定義如下：

typedef struct zskiplistNode {// 后退指針struct zskiplistNode *backward;// 分值double score;// 成員對象robj *obj;// 層struct zskiplistLevel {// 前進(jìn)指針struct zskiplistNode *forward;// 跨度unsigned int span;} level[]; } zskiplistNode;

下圖是一個層高為 5，包含 4 個跳躍表節(jié)點（1 個表頭節(jié)點和 3 個數(shù)據(jù)節(jié)點）組成的跳躍表：

有序集合對象的 skiplist 實現(xiàn)

前面講過，skiplist 編碼的有序集合對象使用 zset 結(jié)構(gòu)作為底層實現(xiàn)。一個 zset 結(jié)構(gòu)同時包含一個字典和一個跳躍表。

typedef struct zset {zskiplist *zs1;dict *dict; }

zset 結(jié)構(gòu)中的 zs1 跳躍表按分值從小到大保存了所有集合元素，每個跳躍表節(jié)點都保存了一個集合元素。

通過跳躍表，可以對有序集合進(jìn)行基于 score 的快速范圍查找。zset 結(jié)構(gòu)中的 dict 字典為有序集合創(chuàng)建了從成員到分值的映射，字典的鍵保存了成員，字典的值保存了分值。通過字典，可以用 O(1) 復(fù)雜度查找給定成員的分值。

假如還是執(zhí)行 ZADD price 8.5 apple 5.0 banana 6.0 cherry 命令向 zset 保存數(shù)據(jù)，如果采用 skiplist 編碼方式的話，該有序集合在內(nèi)存中的結(jié)構(gòu)如下：

6. 總結(jié)

總的來說，Redis 底層數(shù)據(jù)結(jié)構(gòu)主要包括簡單動態(tài)字符串（SDS）、鏈表、字典、跳躍表、整數(shù)集合和壓縮列表六種類型。并且基于這些基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了字符串對象、列表對象、哈希對象、集合對象以及有序集合對象五種常見的對象類型。每一種對象類型都至少采用了 2 種數(shù)據(jù)編碼，不同的編碼使用的底層數(shù)據(jù)結(jié)構(gòu)也不同。

商城源碼下載

商城管理后端演示圖

源碼地址獲取方法,老規(guī)矩啦！

識別下方二維碼，關(guān)注后回復(fù)【A107】

即可獲取下載鏈接

總結(jié)

以上是生活随笔為你收集整理的一文读懂Redis常见对象类型的底层数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。