集合對(duì)象

集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable，intset編碼的集合對(duì)象使用整數(shù)集合作為底層實(shí)現(xiàn)，集合對(duì)象包含的所有元素都被保存在整數(shù)集合里面。舉個(gè)栗子，以下代碼將創(chuàng)建一個(gè)圖1-12所示的intset編碼集合對(duì)象：

127.0.0.1:6379> SADD numbers 1 3 5 (integer) 3 127.0.0.1:6379> OBJECT ENCODING numbers "intset"

　　　　

圖1-12? ?inset編碼的numbers集合對(duì)象

?

另一方面，hashtable編碼的集合對(duì)象使用字典作為底層實(shí)現(xiàn)，字典的每個(gè)鍵都是一個(gè)字符串對(duì)象，每個(gè)字符串對(duì)象包含了一個(gè)集合元素，而字典的值則全部被設(shè)置為NULL，以下的示例，將創(chuàng)建一個(gè)如圖1-13所示的hashtable編碼集合對(duì)象：?

127.0.0.1:6379> SADD fruits "apple" "banana" "cherry" (integer) 3 127.0.0.1:6379> OBJECT ENCODING fruits "hashtable"

　　

圖1-13? ?hashtable編碼的fruits集合對(duì)象

編碼的轉(zhuǎn)換

當(dāng)集合對(duì)象可以同時(shí)滿(mǎn)足以下兩個(gè)條件時(shí)，對(duì)象使用intset編碼：

• 集合對(duì)象保存的所有元素都是整數(shù)值
• 集合對(duì)象保存的元素?cái)?shù)量不超過(guò)512個(gè)

不能滿(mǎn)足以上兩個(gè)條件對(duì)的集合對(duì)象需要使用hashtable編碼，注意，第一個(gè)條件是無(wú)法修改的，但第二個(gè)條件的上限值可以修改，具體請(qǐng)看配置文件中關(guān)于set-max-intset-entries選項(xiàng)的說(shuō)明

對(duì)于使用intset編碼的集合對(duì)象來(lái)說(shuō)，當(dāng)使用intset編碼所需的兩個(gè)條件的任意一個(gè)不能被滿(mǎn)足時(shí)，就會(huì)執(zhí)行對(duì)象的編碼轉(zhuǎn)換操作，原本保存在整數(shù)集合中的所有元素都會(huì)被轉(zhuǎn)移并保存到字典里面，并且對(duì)象的編碼也會(huì)從intset變?yōu)閔ashtable

舉個(gè)栗子，以下代碼創(chuàng)建一個(gè)只包含整數(shù)元素的集合對(duì)象，該對(duì)象原來(lái)的編碼為intset，但我們只要添加一個(gè)字符串元素，集合對(duì)象的編碼轉(zhuǎn)移操作就會(huì)被執(zhí)行

127.0.0.1:6379> SADD numbers 1 3 5 (integer) 3 127.0.0.1:6379> OBJECT ENCODING numbers "intset" 127.0.0.1:6379> SADD numbers "seven" (integer) 1 127.0.0.1:6379> OBJECT ENCODING numbers "hashtable"

　　

除此之外，如果我們創(chuàng)建一個(gè)包含512個(gè)整數(shù)元素的集合對(duì)象，那么對(duì)象的編碼應(yīng)該是intset。但是，只要我們?cè)偻咸砑右粋€(gè)整數(shù)元素，使得這個(gè)集合的元素變?yōu)?13，那么對(duì)象的編碼轉(zhuǎn)換操作就會(huì)被執(zhí)行：

127.0.0.1:6379> EVAL "for i=1, 512 do redis.call('SADD', KEYS[1], i) end" 1 integers (nil) 127.0.0.1:6379> SCARD integers (integer) 512 127.0.0.1:6379> OBJECT ENCODING integers "intset" 127.0.0.1:6379> SADD integers 10086 (integer) 1 127.0.0.1:6379> SCARD integers (integer) 513 127.0.0.1:6379> OBJECT ENCODING integers "hashtable"

　　

集合命令的實(shí)現(xiàn)

因?yàn)榧湘I的值為集合對(duì)象，所以用于集合鍵的所有命令都是針對(duì)集合對(duì)象來(lái)操作的，表1-10列出了其中一部分集合鍵的命令，以及這些命令在不同編碼的集合對(duì)象下的實(shí)現(xiàn)方法

表8-10集合命令的實(shí)現(xiàn)方法

命令	intset編碼的實(shí)現(xiàn)方法	hashtable編碼的實(shí)現(xiàn)方法
SADD	調(diào)用intsetAdd函數(shù)，將所有新元素添加到整數(shù)集合里面	調(diào)用dictAdd，以新元素為鍵，NULL為值，將鍵值對(duì)添加到字典里面
SCARD	調(diào)用intsetLen函數(shù)，返回整數(shù)集合所包含的元素?cái)?shù)量，這個(gè)數(shù)量就是集合對(duì)象所包含的元素?cái)?shù)量	調(diào)用dictSize函數(shù)，返回字典所包含的鍵值對(duì)數(shù)量，這個(gè)數(shù)量就是集合對(duì)象所包含的元素?cái)?shù)量
SISMEMBER	調(diào)用intsetFind函數(shù)，在整數(shù)集合中查找給定的元素，如果找到了說(shuō)明元素存在于集合，沒(méi)找到則說(shuō)明元素不存在于集合	調(diào)用dictFind 函數(shù)，在字典的鍵中查找給定的元素，如果找到了說(shuō)明元素存在于集合，沒(méi)找到則說(shuō)明元素不存在于集合
SMEMBERS	遍歷整個(gè)整數(shù)集合，使用intsetGet函數(shù)返回集合元素	遍歷整個(gè)字典，使用dictGetKey函數(shù)返回字典的鍵作為集合元素
SRANDMEMBER	調(diào)用intsetRandom函數(shù)，從整數(shù)集合中隨機(jī)返回一個(gè)元素	調(diào)用dictGetRandomKey函數(shù)，從字典中隨機(jī)返回一個(gè)字典鍵
SPOP	調(diào)用intsetRandom函數(shù)，從整數(shù)集合中隨機(jī)取出一個(gè)元素，在將這個(gè)隨機(jī)元素返回給客戶(hù)端之后，調(diào)用intsetRemove函數(shù)， 將隨機(jī)元素從整數(shù)集合中刪除掉	調(diào)用dictGetRandomKey函數(shù)，從字典中隨機(jī)取出一個(gè)字典鍵，在將這個(gè)隨機(jī)字典鍵的值返回給客戶(hù)端之后，調(diào)用 dictDelete函數(shù)，從字典中刪除隨機(jī)字典鍵所對(duì)應(yīng)的鍵值對(duì)
SREM	調(diào)用intsetRemove函數(shù)，從整數(shù)集合中刪除所有給定的元素	調(diào)用dictDelete函數(shù)，從字典中刪除所有鍵為給定元素的鍵值對(duì)

?

有序集合對(duì)象

有序集合的編碼可以是ziplist或者skiplist，ziplist編碼的壓縮列表中，每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表節(jié)點(diǎn)來(lái)保存，第一個(gè)節(jié)點(diǎn)保存元素的成員（member），而第二個(gè)元素保存元素的分值（score）。壓縮列表內(nèi)的集合元素按分值從小到大進(jìn)行排序，分值較小的元素被放置在靠近表頭的方向，而分值較大的元素則被放置在靠近表尾的方向

舉個(gè)栗子，如果我們執(zhí)行以下ZADD命令，那么服務(wù)器將創(chuàng)建一個(gè)有序集合對(duì)象作為price鍵的值：

127.0.0.1:6379> ZADD price 8.5 apple 5.0 banana 6.0 cherry (integer) 3 127.0.0.1:6379> OBJECT ENCODING price "ziplist"

　　

price這個(gè)值對(duì)象如圖1-14所示，而對(duì)象所使用的的壓縮列表如圖1-15所示

圖1-14? ?ziplist編碼的有序集合對(duì)象

圖1-15? ?有序集合元素在壓縮列表中按分值從小到大排列

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

redis.h

typedef struct zset {dict *dict;zskiplist *zsl; } zset;typedef struct zskiplistNode {robj *obj;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[]; } zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level; } zskiplist;

　　

zset結(jié)構(gòu)中的的zsl跳躍表按分值從小到大保存了所有集合元素，每個(gè)跳躍表節(jié)點(diǎn)都保存了一個(gè)集合元素：跳躍表節(jié)點(diǎn)的obj屬性保存了元素的成員，而跳躍表節(jié)點(diǎn)的score屬性則保存了元素的分值。通過(guò)這個(gè)跳躍表，程序可以對(duì)有序集合進(jìn)行范圍型操作，比如ZRANK、ZRANGE等命令就是基于跳躍表API來(lái)實(shí)現(xiàn)的

除此之外，zset結(jié)構(gòu)中的dict字典為有序集合創(chuàng)建了一個(gè)從成員到分值的映射，字典中的每個(gè)鍵值對(duì)都保存了一個(gè)集合元素：字典的鍵保存了元素的成員，而字典的值則保存了元素的分值。通過(guò)這個(gè)字典，程序可以在O(1)的時(shí)間復(fù)雜度內(nèi)查找給定成員的分值，ZSCORE命令就是根據(jù)這一特性實(shí)現(xiàn)的，而很多其他有序集合命令都在實(shí)現(xiàn)的內(nèi)部用到了這一特性

有序集合中每個(gè)元素的成員都是一個(gè)字符串對(duì)象，而每個(gè)元素的分值都是一個(gè)double類(lèi)型的浮點(diǎn)數(shù)。值得一提的是，雖然zset結(jié)構(gòu)同時(shí)使用跳躍表和字典來(lái)保存有序集合元素，但這兩種數(shù)據(jù)結(jié)構(gòu)都會(huì)通過(guò)指針來(lái)共享相同元素的成員和分值，所以同時(shí)使用跳躍表和字典來(lái)保存集合元素不會(huì)產(chǎn)生任何重復(fù)成員或分值，也不會(huì)因?yàn)槔速M(fèi)額外的內(nèi)存

為什么有序集合需要同時(shí)使用跳躍表和字典來(lái)實(shí)現(xiàn)？在理論上，有序集合可以單獨(dú)使用字典或者跳躍表其中一種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，但無(wú)論使用字典還是跳躍表，在性能上比起同時(shí)使用字典和跳躍表都會(huì)有所降低。舉個(gè)例子，如果我們只是用字典來(lái)實(shí)現(xiàn)有序集合，那么雖然可以在O(1)的時(shí)間復(fù)雜度內(nèi)查找成員對(duì)應(yīng)的分值，但是，因?yàn)樽值湟詿o(wú)序的方式來(lái)保存集合元素，所以每次在執(zhí)行范圍型操作——比如：ZRANK、ZRANGE等命令時(shí)，程序都需要對(duì)字典的所有元素進(jìn)行排序，完成這種排序至少需要O(N logN)的時(shí)間復(fù)雜度，以及額外的O(N)內(nèi)存空間（因?yàn)橐獎(jiǎng)?chuàng)建一個(gè)數(shù)組來(lái)保存排序后的元素）

另一方面如果我們只使用跳躍表來(lái)實(shí)現(xiàn)有序集合，那么跳躍表執(zhí)行范圍型操作時(shí)的所有優(yōu)點(diǎn)都會(huì)被保留，但因?yàn)闆](méi)有了字典，所以根據(jù)成員查找分值這一操作的時(shí)間復(fù)雜度將從O(1)上升至O(logN)。因?yàn)橐陨显?#xff0c;為了讓有序集合的查找和范圍型操作都盡可能快地執(zhí)行，Redis選擇了同時(shí)使用字典和跳躍表兩種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)有序集合

舉個(gè)栗子，如果前面的price鍵創(chuàng)建的不是ziplist編碼的有序集合對(duì)象，而是skiplist編碼的有序集合對(duì)象，那么這個(gè)有序集合對(duì)象將會(huì)是圖1-16所示的樣子，而對(duì)象所使用的zset結(jié)構(gòu)將會(huì)是圖8-17所示的樣子

圖1-16? ?skiplist編碼的有序集合對(duì)象

?

圖1-17? ?有序集合元素同時(shí)被保存在字典和跳躍表中

編碼的轉(zhuǎn)換

當(dāng)有序集合對(duì)象可以同時(shí)滿(mǎn)足以下條件時(shí)，對(duì)象使用ziplist編碼：

• 有序集合保存的元素?cái)?shù)量小于128個(gè)
• 有序集合保存的所有元素的長(zhǎng)度小于64字節(jié)

不能滿(mǎn)足以上兩個(gè)條件的有序集合對(duì)象將使用skiplist編碼

# 對(duì)象包含了 128 個(gè)元素 127.0.0.1:6379> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 numbers (nil) 127.0.0.1:6379> ZCARD numbers (integer) 128 127.0.0.1:6379> OBJECT ENCODING numbers "ziplist" # 再添加一個(gè)新元素 127.0.0.1:6379> ZADD numbers 3.14 pi (integer) 1 # 對(duì)象包含的元素?cái)?shù)量變?yōu)?129 個(gè) 127.0.0.1:6379> ZCARD numbers (integer) 129 # 編碼已改變 127.0.0.1:6379> OBJECT ENCODING numbers "skiplist"

　　

以下代碼則展示了有序集合對(duì)象因?yàn)樵氐某蓡T過(guò)長(zhǎng)而引發(fā)編碼轉(zhuǎn)換的情況：

# 向有序集合添加一個(gè)成員只有三字節(jié)長(zhǎng)的元素 127.0.0.1:6379> ZADD blah 1.0 www (integer) 1 127.0.0.1:6379> OBJECT ENCODING blah "ziplist" # 向有序集合添加一個(gè)成員為 66 字節(jié)長(zhǎng)的元素 127.0.0.1:6379> ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo (integer) 1 # 編碼已改變 127.0.0.1:6379> OBJECT ENCODING blah "skiplist"

　　

有序集合命令的實(shí)現(xiàn)

因?yàn)橛行蚣湘I的值為哈希值，所以用于有序集合鍵的所有命令都是針對(duì)哈希對(duì)象來(lái)構(gòu)建的，表1-11列出了其中一部分有序集合鍵命令，以及這些命令在不同編碼的哈希對(duì)象下的實(shí)現(xiàn)方法

表? ?8-11有序集合命令的實(shí)現(xiàn)方法

命令	ziplist編碼的實(shí)現(xiàn)方法	zset編碼的實(shí)現(xiàn)方法
ZADD	調(diào)用ziplistInsert函數(shù)， 將成員和分值作為兩個(gè)節(jié)點(diǎn)分別插入到壓縮列表	先調(diào)用zslInsert函數(shù)，將新元素添加到跳躍表，然后調(diào)用dictAdd 函數(shù)，將新元素關(guān)聯(lián)到字典
ZCARD	調(diào)用ziplistLen函數(shù)，獲得壓縮列表包含節(jié)點(diǎn)的數(shù)量，將這個(gè)數(shù)量除以2得出集合元素的數(shù)量	訪(fǎng)問(wèn)跳躍表數(shù)據(jù)結(jié)構(gòu)的length屬性， 直接返回集合元素的數(shù)量
ZCOUNT	遍歷壓縮列表，統(tǒng)計(jì)分值在給定范圍內(nèi)的節(jié)點(diǎn)的數(shù)量	遍歷跳躍表，統(tǒng)計(jì)分值在給定范圍內(nèi)的節(jié)點(diǎn)的數(shù)量
ZRANGE	從表頭向表尾遍歷壓縮列表，返回給定索引范圍內(nèi)的所有元素	從表頭向表尾遍歷跳躍表，返回給定索引范圍內(nèi)的所有元素
ZREVRANGE	從表尾向表頭遍歷壓縮列表，返回給定索引范圍內(nèi)的所有元素	從表尾向表頭遍歷跳躍表，返回給定索引范圍內(nèi)的所有元素
ZRANK	從表頭向表尾遍歷壓縮列表，查找給定的成員，沿途記錄經(jīng)過(guò)節(jié)點(diǎn)的數(shù)量，當(dāng)找到給定成員之后，途經(jīng)節(jié)點(diǎn)的數(shù)量就是該成員所對(duì)應(yīng)元素的排名	從表頭向表尾遍歷跳躍表，查找給定的成員，沿途記錄經(jīng)過(guò)節(jié)點(diǎn)的數(shù)量，當(dāng)找到給定成員之后，途經(jīng)節(jié)點(diǎn)的數(shù)量就是該成員所對(duì)應(yīng)元素的排名
ZREVRANK	從表尾向表頭遍歷壓縮列表，查找給定的成員，沿途記錄經(jīng)過(guò)節(jié)點(diǎn)的數(shù)量，當(dāng)找到給定成員之后， 途經(jīng)節(jié)點(diǎn)的數(shù)量就是該成員所對(duì)應(yīng)元素的排名	從表尾向表頭遍歷跳躍表，查找給定的成員，沿途記錄經(jīng)過(guò)節(jié)點(diǎn)的數(shù)量，當(dāng)找到給定成員之后， 途經(jīng)節(jié)點(diǎn)的數(shù)量就是該成員所對(duì)應(yīng)元素的排名
ZREM	遍歷壓縮列表，刪除所有包含給定成員的節(jié)點(diǎn)，以及被刪除成員節(jié)點(diǎn)旁邊的分值節(jié)點(diǎn)	遍歷跳躍表，刪除所有包含了給定成員的跳躍表節(jié)點(diǎn)。 并在字典中解除被刪除元素的成員和分值的關(guān)聯(lián)
ZSCORE	遍歷壓縮列表，查找包含了給定成員的節(jié)點(diǎn)，然后取出成員節(jié)點(diǎn)旁邊的分值節(jié)點(diǎn)保存的元素分值	直接從字典中取出給定成員的分值

轉(zhuǎn)載于:https://www.cnblogs.com/beiluowuzheng/p/9737243.html

總結(jié)

以上是生活随笔為你收集整理的Redis实现之对象（三）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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