在 Redis 中，有一種數(shù)據(jù)類型，當(dāng)在存儲(chǔ)的時(shí)候會(huì)同時(shí)采用兩種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行分別存儲(chǔ)，那么 Redis 為什么要這么做呢？這么做會(huì)造成同一份數(shù)據(jù)占用兩倍空間嗎？

五種基本類型之集合對(duì)象

Redis 中的集合對(duì)象是一個(gè)包含字符串類型元素的無序集合，集合中元素唯一不可重復(fù)。

集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)有兩種：intset 和 hashtable。內(nèi)部通過編碼來進(jìn)行區(qū)分：

intset 編碼

intset（整數(shù)集合）可以保存類型為 int16_t，int32_t，int64_t的整數(shù)值，并且保證集合中沒有重復(fù)元素。intset 數(shù)據(jù)結(jié)構(gòu)定義如下（源碼 inset.h內(nèi)）：

下圖就是一個(gè) intset 的集合對(duì)象存儲(chǔ)簡(jiǎn)圖：

encoding

在 intset 內(nèi)部的 encoding 記錄了當(dāng)前整數(shù)集合的數(shù)據(jù)存儲(chǔ)類型，主要有三種：

INTSET_ENC_INT16

此時(shí)contents[]內(nèi)的每個(gè)元素都是一個(gè) int16_t 類型的整數(shù)值，范圍是：-32768 ~ 32767（-2 的 15 次方 ~ 2 的 15 次方 - 1）。

INTSET_ENC_INT32

此時(shí)contents[]內(nèi)的每個(gè)元素都是一個(gè) int32_t 類型的整數(shù)值，范圍是：-2147483648 ~ 2147483647（-2 的 31 次方 ~ 2 的 31 次方 - 1）。

INTSET_ENC_INT64

此時(shí)contents[]內(nèi)的每個(gè)元素都是一個(gè) int64_t 類型的整數(shù)值，范圍是：-9223372036854775808 ~ 9223372036854775807（-2 的 63 次方 ~ 2 的 63 次方 - 1）。

contents[]

contents[]雖然結(jié)構(gòu)的定義上寫的是 int8_t 類型，但是實(shí)際存儲(chǔ)類型是由上面的 encoding 來決定的。

整數(shù)集合的升級(jí)

假如一開始整數(shù)集合中的元素都是 16 位的，采用 int16_t 類型來存儲(chǔ)，此時(shí)需要再存儲(chǔ)一個(gè) 32 位的整數(shù)，那么就需要對(duì)原先的整數(shù)集合進(jìn)行升級(jí)，升級(jí)之后才能將 32 位的整數(shù)存儲(chǔ)到整數(shù)集合內(nèi)。這就涉及到了整數(shù)集合的類型升級(jí)，升級(jí)過程主要有 4 個(gè)步驟：

根據(jù)新添加元素的類型來擴(kuò)展底層數(shù)組空間的大小，按照升級(jí)后現(xiàn)有元素的位數(shù)來分配新的空間。

將現(xiàn)有的元素進(jìn)行類型轉(zhuǎn)換，并將轉(zhuǎn)換類型后的元素從后到前逐個(gè)重新放回到數(shù)組內(nèi)。

將新元素放到數(shù)組的頭部或者尾部（因?yàn)橛|發(fā)升級(jí)的條件就是當(dāng)前數(shù)組的整數(shù)類型無法存儲(chǔ)新元素，所以新元素要么比現(xiàn)有元素都大，要么就比現(xiàn)有元素都?。?。

將 encoding 屬性修改為最新的編碼，并且同步修改 length 屬性。

PS：和字符串對(duì)象的編碼一樣，整數(shù)集合的類型一旦發(fā)生升級(jí)，將會(huì)保持編碼，無法降級(jí)。

升級(jí)示例

1.假如我們有一個(gè)集合存儲(chǔ)的 encoding 是int16_t，內(nèi)部存儲(chǔ)了 3 個(gè)元素：

2.這時(shí)候需要插入一個(gè)整數(shù) 50000，發(fā)現(xiàn)存儲(chǔ)不下去，而 50000 是一個(gè)int32_t類型整數(shù)，所以需要申請(qǐng)新空間，申請(qǐng)空間大小為4 * 32 - 48=80。

3.現(xiàn)在新的數(shù)組內(nèi)要放置 4 個(gè)元素，原來的數(shù)組排在第 3，所以需要將升級(jí)后的 3 移動(dòng)到 64-95 位。

4.繼續(xù)將升級(jí)后的 2 移動(dòng)到 32-63 位。

5.繼續(xù)將升級(jí)后的 1 移動(dòng)到 0-31 位。

6.然后會(huì)將 50000 放到 96-127 位。

7.最后會(huì)修改 encoding 和 length 屬性，修改之后就完成了本次的升級(jí)。

hashtable 編碼

hashtable 結(jié)構(gòu)在前面講述哈希對(duì)象的時(shí)候進(jìn)行過詳細(xì)分析

intset 和 hashtable 編碼轉(zhuǎn)換

當(dāng)一個(gè)集合滿足以下兩個(gè)條件時(shí)，Redis 會(huì)選擇使用 intset 編碼：

集合對(duì)象保存的所有元素都是整數(shù)值。

集合對(duì)象保存的元素?cái)?shù)量小于等于 512 個(gè)（這個(gè)閾值可以通過配置文件set-max-intset-entries來控制）。

一旦集合中的元素不滿足上面兩個(gè)條件，則會(huì)選擇使用 hashtable 編碼。

集合對(duì)象常用命令

sadd key member1 member2：將一個(gè)或多個(gè)元素 member 加入到集合 key 當(dāng)中，并返回添加成功的數(shù)目，如果元素已存在則被忽略。

sismember key member：判斷元素 member 是否存在集合 key 中。

srem key member1 member2：移除集合 key 中的元素，不存在的元素會(huì)被忽略。

smove source dest member：將元素 member 從集合 source 中移動(dòng)到 dest 中，如果 member 不存在，則不執(zhí)行任何操作。

smembers key：返回集合 key 中所有元素。

了解了操作集合對(duì)象的常用命令，我們就可以來驗(yàn)證下前面提到的哈希對(duì)象的類型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。依次執(zhí)行如下命令：

得到如下效果：

可以看到，當(dāng)設(shè)置的元素里面只有整數(shù)時(shí)，集合使用的就是 intset 編碼，當(dāng)設(shè)置的元素中含有非整數(shù)時(shí)，使用的就是 hashtable 編碼。

五種基本類型之有序集合對(duì)象

Redis 中的有序集合和集合的區(qū)別是有序集合中的每個(gè)元素都會(huì)關(guān)聯(lián)一個(gè) double 類型的分?jǐn)?shù)，然后按照分?jǐn)?shù)從小到大的順序進(jìn)行排列。換句話說，有序集合的順序是由我們自己設(shè)值的時(shí)候通過分?jǐn)?shù)來確定的。有序集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)有兩種：skiplist 和 ziplist。內(nèi)部同樣是通過編碼來進(jìn)行區(qū)分：

skiplist 編碼

skiplist 即跳躍表，有時(shí)候也簡(jiǎn)稱為跳表。使用 skiplist 編碼的有序集合對(duì)象使用了 zset 結(jié)構(gòu)來作為底層實(shí)現(xiàn)，而zset 中同時(shí)包含了一個(gè)字典和一個(gè)跳躍表。

跳躍表

跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu)，其主要特點(diǎn)是通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。大部分情況下，跳躍表的效率可以等同于平衡樹，但是跳躍表的實(shí)現(xiàn)卻遠(yuǎn)遠(yuǎn)比平衡樹的實(shí)現(xiàn)簡(jiǎn)單，所以 Redis 選擇了使用跳躍表來實(shí)現(xiàn)有序集合。下圖是一個(gè)普通的有序鏈表，我們?nèi)绻胍业?35 這個(gè)元素，只能從頭開始遍歷到尾（鏈表中元素不支持隨機(jī)訪問，所以不能用二分查找，而數(shù)組中可以通過下標(biāo)隨機(jī)訪問，所以二分查找一般適用于有序數(shù)組），時(shí)間復(fù)雜度是O(n)。

那么假如我們可以直接跳到鏈表的中間，那就可以節(jié)省很多資源了，這就是跳表的原理，如下圖所示就是一個(gè)跳表的數(shù)據(jù)結(jié)構(gòu)示例：

上圖中 level1，level2，level3 就是跳表的層級(jí)，每一個(gè) level 層級(jí)都有一個(gè)指向下一個(gè)相同 level 層級(jí)元素的指針，比如上圖我們遍歷尋找元素 35 的時(shí)候就有三種方案：

第 1 種就是執(zhí)行 level1 層級(jí)的指針，需要遍歷 7 次（1->8->9->12->15->20->35）才能找到元素 35。

第 2 種就是執(zhí)行 level2 層級(jí)的指針，只需要遍歷 5 次（1->9->12->15->35）就能找到元素 35。

第 3 種就是執(zhí)行 level3 層級(jí)的元素，這時(shí)候只需要遍歷 3 次（1->12->35）就能找到元素 35 了，大大提升了效率。

skiplist 的存儲(chǔ)結(jié)構(gòu)

跳躍表中的每個(gè)節(jié)點(diǎn)是一個(gè) zskiplistNode節(jié)點(diǎn)（源碼 server.h內(nèi)）：

level（層）

level 即跳躍表中的層，其是一個(gè)數(shù)組，也就是說一個(gè)節(jié)點(diǎn)的元素可以擁有多個(gè)層，即多個(gè)指向其他節(jié)點(diǎn)的指針，程序可以通過不同層級(jí)的指針來選擇最快捷的路徑提升訪問速度。

level 是在每次創(chuàng)建新節(jié)點(diǎn)的時(shí)候根據(jù)冪次定律（power law）隨機(jī)生成的一個(gè)介于 1~32 之間的數(shù)字。

forward（前進(jìn)指針）

每個(gè)層都會(huì)有一個(gè)指向鏈表尾部方向元素的指針，遍歷元素的時(shí)候需要使用到前進(jìn)指針。

span（跨度）

跨度記錄了兩個(gè)節(jié)點(diǎn)之間的距離,需要注意的是，如果指向了 NULL 的話，則跨度為 0。

backward（后退指針）

和前進(jìn)指針不一樣的是后退指針只有一個(gè)，所以每次只能后退至前一個(gè)節(jié)點(diǎn)（上圖中沒有畫出后退指針）。

ele（元素）

跳躍表中元素是一個(gè) sds 對(duì)象（早期版本使用的是 redisObject 對(duì)象），元素必須唯一不能重復(fù)。

score（分值）

節(jié)點(diǎn)的分值是一個(gè) double 類型的浮點(diǎn)數(shù)，跳躍表中會(huì)將節(jié)點(diǎn)按照分值按照從小到大的順序排列，不同節(jié)點(diǎn)的分值可以重復(fù)。

上面介紹的只是跳躍表中的一個(gè)節(jié)點(diǎn)，多個(gè) zskiplistNode 節(jié)點(diǎn)組成了一個(gè) zskiplist 對(duì)象：

到這里你可能以為有序集合就是用這個(gè) zskiplist 來實(shí)現(xiàn)的，然而實(shí)際上 Redis 并沒有直接使用 zskiplist 來實(shí)現(xiàn)，而是用 zset 對(duì)象再次進(jìn)行了一層包裝。

所以最終，一個(gè)有序集合如果使用了 skiplist 編碼，其數(shù)據(jù)結(jié)構(gòu)如下圖所示：

上圖中上面一部分中的字典中的 key 就是對(duì)應(yīng)了有序集合中的元素（member），value 就對(duì)應(yīng)了分值（score）。上圖中下面一部分中跳躍表整數(shù) 1,8,9,12 也是對(duì)應(yīng)了元素（member），最后一排的 double 型數(shù)字就是分值（score）。

也就是說字典和跳躍表中的數(shù)據(jù)都指向了我們存儲(chǔ)的元素（兩種數(shù)據(jù)結(jié)構(gòu)最終指向的是同一個(gè)地址，所以數(shù)據(jù)并不會(huì)出現(xiàn)冗余存儲(chǔ)），Redis 為什么要這么做呢？

為什么同時(shí)選擇使用字典和跳躍表

有序集合直接使用跳躍表或者單獨(dú)使用字典完全可以獨(dú)自實(shí)現(xiàn)，但是我們想一下，如果單獨(dú)使用跳躍表來實(shí)現(xiàn)，那么雖然可以使用跨度大的指針去遍歷元素來找到我們需要的數(shù)據(jù)，但是其復(fù)雜度仍然達(dá)到了 O(logN)，而字典中獲取一個(gè)元素的復(fù)雜度是 O(1)，而如果單獨(dú)使用字典雖然獲取元素很快，但是字典是無序的，所以如果要范圍查找就需要對(duì)其進(jìn)行排序，這又是一個(gè)耗時(shí)的操作，所以 Redis 綜合了兩種數(shù)據(jù)結(jié)構(gòu)來最大程度的提升性能，這也是 Redis 設(shè)計(jì)的精妙之處。

ziplist 編碼

壓縮列表在列表對(duì)象和哈希對(duì)象都有使用到，想詳細(xì)了解的可以點(diǎn)擊這里。

https://blog.csdn.net/zwx900102/article/details/112651435

ziplist 和 skiplist 編碼轉(zhuǎn)換

當(dāng)有序集合對(duì)象同時(shí)滿足以下兩個(gè)條件時(shí)，會(huì)使用 ziplist 編碼進(jìn)行存儲(chǔ)：

有序集合對(duì)象中保存的元素個(gè)數(shù)小于 128 個(gè)（可以通過配置zset-max-ziplist-entries修改）。

有序集合對(duì)象中保存的所有元素的總長(zhǎng)度小于 64 字節(jié)（可以通過配置zset-max-ziplist-value修改）。

有序集合對(duì)象常用命令

zadd key score1 member1 score2 member2：將一個(gè)或多個(gè)元素（member）及其 score 添加到有序集合 key 中。

zscore key member：返回有序集合 key 中 member 成員的 score。

zincrby key num member：將有序集合 key 中的 member 加上 num，num 可以為負(fù)數(shù)。

zcount key min max：返回有序集合 key 中 score 值在 [min,max] 區(qū)間的 member 數(shù)量。

zrange key start stop：返回有序集合 key 中 score 從小到大排列后在 [start,stop] 區(qū)間的所有 member。

zrevrange key start stop：返回有序集合 key 中 score 從大到小排列后在 [start,stop] 區(qū)間的所有 member。

zrangebyscore key min max：返回有序集合中按 score 從小到大排列后在 [min,max] 區(qū)間的所有元素。注意這里默認(rèn)是閉區(qū)間，但是可以在 max 和 min 的數(shù)值前面加上(或者[來控制開閉區(qū)間。

zrevrangebyscore key max min：返回有序集合中按 score 從大到小排列后在 [min,max] 區(qū)間的所有元素。注意這里默認(rèn)是閉區(qū)間，但是可以在 max 和 min 的數(shù)值前面加上(或者[來控制開閉區(qū)間。

zrank key member：返回有序集合中 member 中元素排名（從小到大），返回的結(jié)果從 0 開始計(jì)算。

zrevrank key member：返回有序集合中 member 中元素排名（從大到?。祷氐慕Y(jié)果從 0 開始計(jì)算。

zlexcount key min max：返回有序集合中 min 和 max 之間的 member 數(shù)量。注意這個(gè)命令中的 min 和 max 前面必須加(或者[來控制開閉區(qū)間，特殊值 - 和 + 分別表示負(fù)無窮和正無窮。

了解了操作有序集合對(duì)象的常用命令，我們就可以來驗(yàn)證下前面提到的哈希對(duì)象的類型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。在執(zhí)行命令之前，我們先把配置文件中的參數(shù)

zset-max-ziplist-entries

修改為 2，然后重啟 Redis 服務(wù)。重啟完成之后依次執(zhí)行如下命令：

得到如下效果：

總結(jié)

本文主要分析了集合對(duì)象和有序集合對(duì)象的底層存儲(chǔ)結(jié)構(gòu) intset 和 skiplist 的實(shí)現(xiàn)原理，并且重點(diǎn)分析了有序集合如何實(shí)現(xiàn)排序以及為何同時(shí)使用兩種數(shù)據(jù)結(jié)構(gòu)（字典和跳表）同時(shí)進(jìn)行進(jìn)行存儲(chǔ)數(shù)據(jù)的原因。



審核編輯：劉清