Redis五種數(shù)據(jù)類(lèi)型詳解
什么是 Redis
Redis 是基于內(nèi)存的 K-V 數(shù)據(jù)庫(kù),常用于緩存、消息隊(duì)列,分布式鎖等場(chǎng)景,并且提供了常見(jiàn)的數(shù)據(jù)結(jié)構(gòu):字符串、哈希、列表、集合、帶排序的集合
Redis 數(shù)據(jù)類(lèi)型詳解
前置知識(shí)
Redis中的任意數(shù)據(jù)類(lèi)型的鍵和值都會(huì)被封裝為一個(gè) RedisObject
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr; } robj;
type
:指具體的對(duì)象類(lèi)型
encoding
:底層編碼方式
lru
:記錄最后一次被訪問(wèn)的時(shí)間
refcount
:對(duì)象引用計(jì)數(shù)器,計(jì)數(shù)器為 0 時(shí)表示沒(méi)有被引用,可以回收
ptr
:實(shí)際存儲(chǔ)的值
五種數(shù)據(jù)結(jié)構(gòu)
Redis中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類(lèi)型不同,選擇不同的編碼方式。每種數(shù)據(jù)類(lèi)型的使用的編碼方式如下:
數(shù)據(jù)類(lèi)型 | 編碼方式 |
---|---|
OBJ_STRING | int、embstr、raw |
OBJ_LIST | LinkedList和ZipList(3.2以前)、QuickList(3.2以后) |
OBJ_SET | intset、HT |
OBJ_ZSET | ZipList、HT、SkipList |
OBJ_HASH | ZipList、HT |
Redis 的編碼方式
Redis 中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類(lèi)型不同,選擇不同的編碼方式,共包含 11 種不同類(lèi)型:
編號(hào) | 編碼方式 | 說(shuō)明 |
---|---|---|
0 | OBJ_ENCODING_RAW | raw編碼動(dòng)態(tài)字符串 |
1 | OBJ_ENCODING_INT | long類(lèi)型的整數(shù)的字符串 |
2 | OBJ_ENCODING_HT | hash表(字典dict) |
3 | OBJ_ENCODING_ZIPMAP | 已廢棄 |
4 | OBJ_ENCODING_LINKEDLIST | 雙端鏈表 |
5 | OBJ_ENCODING_ZIPLIST | 壓縮列表 |
6 | OBJ_ENCODING_INTSET | 整數(shù)集合 |
7 | OBJ_ENCODING_SKIPLIST | 跳表 |
8 | OBJ_ENCODING_EMBSTR | embstr的動(dòng)態(tài)字符串 |
9 | OBJ_ENCODING_QUICKLIST | 快速列表 |
10 | OBJ_ENCODING_STREAM | Stream流 |
String
介紹
字符串 (string) 其實(shí)是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu),不僅可以存儲(chǔ)字符串,還可以存儲(chǔ)整數(shù)、浮點(diǎn)數(shù)、二進(jìn)制數(shù)據(jù)等;
常用命令
set key value
:添加一個(gè) string 類(lèi)型的鍵值對(duì)
get key
:獲取 key 對(duì)應(yīng)的 value
mset
:批量設(shè)置對(duì)個(gè)鍵值對(duì)
mget
:批量獲取多個(gè)鍵值對(duì)
incr
:讓一個(gè)整形自增 1
setnx
:添加一個(gè) string 類(lèi)型的字符串,前提是這個(gè) key 不存在
使用場(chǎng)景
緩存對(duì)象
直接緩存整個(gè) json 字符串對(duì)象 SET user:1 '{"name":"ezreal", "age":18}'
緩存更新策略
- 使用 redis 的內(nèi)存淘汰機(jī)制;
- 超時(shí)剔除,給數(shù)據(jù)添加 TTL 過(guò)期時(shí)間;
- 客戶(hù)端主動(dòng)更新緩存;
分布式鎖
使用 setnx 指令可以實(shí)現(xiàn)分布式鎖,若設(shè)置值成功則表示獲取鎖成功,設(shè)置失敗則獲取鎖失敗,注意要設(shè)置該 key 的過(guò)期時(shí)間,防止一直搶占該鎖
常規(guī)計(jì)數(shù)
可以通過(guò) incr
指令來(lái)統(tǒng)計(jì)數(shù)量,前提設(shè)置的 value 需要是整形
共享 session
我們可以把多臺(tái)服務(wù)器上的 session 統(tǒng)一放到 redis 中,無(wú)論向集群哪臺(tái)服務(wù)器發(fā)送消息,都保證去 redis 中獲取 session 的信息
底層實(shí)現(xiàn)
redis 的底層實(shí)現(xiàn)是 SDS 字符串
SDS 結(jié)構(gòu)體
struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* buf已保存的字符串字節(jié)數(shù),不包含結(jié)束標(biāo)示 */ uint8_t alloc; /* buf申請(qǐng)的總的字節(jié)數(shù),不包含結(jié)束標(biāo)示 */ unsigned char flags; /* 不同的SDS頭類(lèi)型 */ char buf[]; };
len
:該字符串的 長(zhǎng)度
alloc
:buf 申請(qǐng)的 總字節(jié)數(shù)
buf
:實(shí)際存儲(chǔ)數(shù)據(jù)的位置
flag
:SDS 頭類(lèi)型,用來(lái)控制SDS頭大小 :SDS_TYPE_5
,SDS_TYPE_8
,SDS_TYPE_16
,SDS_TYPE_32
,SDS_TYPE_64
整形的存儲(chǔ)
如果存儲(chǔ)的是一個(gè)整形,則則直接存儲(chǔ)在 RedisObject 中即可;
SDS 動(dòng)態(tài)擴(kuò)容
假如現(xiàn)在在 name 字符串后加入 ezreal,形成新的字符串 'nameezreal'
- 若新字符串的長(zhǎng)度小于 1M,則新的內(nèi)存空間為 新字符串 的長(zhǎng)度的兩倍 + 1;
- 若新字符串的長(zhǎng)度大于 1M,則新的內(nèi)存空間為 新字符串 的長(zhǎng)度 + 1M + 1,稱(chēng)為內(nèi)存預(yù)分配;
List
介紹
列表是一個(gè)有序的字符串集合,可以通過(guò)下標(biāo)索引來(lái)訪問(wèn)指定位置的字符串,還可以在列表頭部或者尾部來(lái)添加或刪除元素
常用命令
LPUSH KEY
:向列表左側(cè)插入元素
RPUSH KEY
:向列表右側(cè)插入元素
LPOP KEY
:向列表左側(cè)彈出元素
RPOP KEY
:向列表右側(cè)彈出元素
LRANGE KEY star end
:獲取指定范圍內(nèi)的 key
BLPOP / BRPOP
:與 LPOP / RPOP 類(lèi)似,只不過(guò)在沒(méi)有元素時(shí)會(huì)等待
使用場(chǎng)景
消息隊(duì)列
消息隊(duì)列實(shí)現(xiàn)的三大要素:消息保序,處理重復(fù)的消息,保證消息的可靠性
- 消息保序
我們可以基于 LPUSH / RPOP 的方法來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列,消息先進(jìn)先出,保證消息的順序;
當(dāng)有一個(gè)缺點(diǎn),消費(fèi)者只能不斷的輪詢(xún)?cè)撽?duì)列是否有消息,因?yàn)橄M(fèi)者新增一條消息后是不能通知消費(fèi)者的,所以消費(fèi)者要不斷輪詢(xún) while(1)
,不斷的占用 CPU。我們可以使用 BRPOP
來(lái)優(yōu)化,消費(fèi)者沒(méi)有獲取到消息時(shí),會(huì)自動(dòng)阻塞,直到生產(chǎn)者放入新的消息。
- 處理重復(fù)的消息
我們可以為每個(gè)消息生成一個(gè) 唯一 的消息 ID,每次消費(fèi)消息時(shí),從數(shù)據(jù)庫(kù)中判斷該消息是否已經(jīng)被處理了,防止消息的重復(fù)消息。
- 保證消息可靠性
當(dāng)消息被消費(fèi)者獲取后,沒(méi)有處理完消息,機(jī)器就宕機(jī)了,這樣不僅消息沒(méi)有完全被消費(fèi),List 中的消息也丟失了,從而導(dǎo)致這個(gè)任務(wù)永遠(yuǎn)丟失了;
我們可以使用 Redis 中的BRPOPLPUSH
命令,作用是把該消息從 List 中拿出來(lái),同時(shí)還會(huì)把該消息放到另一個(gè) List 中作留存。
底層實(shí)現(xiàn)
在 Redis 3.2 之前,List 的底層實(shí)現(xiàn)是壓縮列表 ( ZipList
) 或 雙向鏈表
在 Redis 3.2 之后,List 的底層實(shí)現(xiàn)是 QuickList
ZipList
ZipList 又叫壓縮列表,類(lèi)似 "雙向鏈表",但其不是鏈表。它由一段連續(xù)的內(nèi)存塊組成,可以在列表頭部或者尾部添加或者刪除元素。
zlbytes
:整個(gè) ZipList 的 內(nèi)存字節(jié)數(shù),占用 4 字節(jié)
zltail
:從 ZipList 的起始地址到最后一個(gè) entry 的內(nèi)存字節(jié)數(shù),占用 4 字節(jié)
zllen
:ZipList 中 entry 的個(gè)數(shù),占用 2 字節(jié)
zlend
:結(jié)束標(biāo)識(shí) 0xff
,占用 1 字節(jié)
ZipEntry結(jié)構(gòu)
previous_entry_length
:上一個(gè) entry 的長(zhǎng)度,占用 1個(gè) 或 5個(gè)字節(jié)
- 若上一個(gè) entry 的長(zhǎng)度小于 256 字節(jié),則 encoding 使用 1 個(gè)字節(jié)來(lái)存儲(chǔ)
- 若上一個(gè) entry 的長(zhǎng)度大于 256 字節(jié),則 encoding 使用 5 個(gè)字節(jié)來(lái)存儲(chǔ)
encoding
:記錄 content 的類(lèi)型 [ 整形 or 字符串 ] 和長(zhǎng)度,占用 1個(gè),2個(gè) 或者 5個(gè)字節(jié)
content
:實(shí)際的內(nèi)容
Encoding 編碼
Entry 中的 encoding 編碼分為字符串和整數(shù)兩種:
字符串:如果 encoding 是以“00”“01”或者“10”開(kāi)頭,則證明 content 是字符串
整數(shù):如果encoding是以“11”開(kāi)始,則證明content是整數(shù),且encoding固定只占用1個(gè)字節(jié)
編碼 | 編碼長(zhǎng)度 | 整數(shù)類(lèi)型 |
---|---|---|
11000000 | 1 | int16_t(2 bytes) |
11010000 | 1 | int32_t(4 bytes) |
11100000 | 1 | int64_t(8 bytes) |
11110000 | 1 | 24位有符整數(shù)(3 bytes) |
11111110 | 1 | 8位有符整數(shù)(1 bytes) |
1111xxxx | 1 | 直接在xxxx位置保存數(shù)值,范圍從0001~1101,減1后結(jié)果為實(shí)際值 |
可見(jiàn),ZipList 通過(guò)記錄上一個(gè)entry 的長(zhǎng)度 和 自身entry 的長(zhǎng)度(length + encoding + content),從而可以快速得到上一個(gè) entry 和下一個(gè) entry ,從而實(shí)現(xiàn)從頭到尾 或 從尾到頭的遍歷。
QuickList
QuickList 是一個(gè)雙向鏈表,它的每一個(gè)節(jié)點(diǎn)都是 ZipList
為了避免 QuickList 中的每個(gè) ZipList 中 entry 過(guò)多,Redis 提供了一個(gè)配置項(xiàng):list-max-ziplist-size
來(lái)限制。
如果值為正,則代表 ZipList 的允許的 entry 個(gè)數(shù)的最大值;
如果值為負(fù),則代表ZipList的最大內(nèi)存大小,分5種情況:
- -1:每個(gè) ZipList 的內(nèi)存占用不能超過(guò) 4kb
- -2:每個(gè) ZipList 的內(nèi)存占用不能超過(guò) 8kb
- -3:每個(gè) ZipList 的內(nèi)存占用不能超過(guò) 16kb
- -4:每個(gè) ZipList 的內(nèi)存占用不能超過(guò) 32kb
- -5:每個(gè) ZipList 的內(nèi)存占用不能超過(guò) 64kb
其默認(rèn)值為 -2:
以下是 QuickList 的和 QuickListNode 的結(jié)構(gòu)源碼:
QuickList
typedef struct quicklist { quicklistNode *head; // 頭結(jié)點(diǎn)指針 quicklistNode *tail; // 尾結(jié)點(diǎn)指針 unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[]; } quicklist;
QuickListNode
typedef struct quicklistNode { struct quicklistNode *prev; // 前一個(gè)指針 struct quicklistNode *next; // 后一個(gè)指針 unsigned char *zl; // 當(dāng)前結(jié)點(diǎn)的ziplist指針 unsigned int sz; /* ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int extra : 10; /* more bits to steal for future usage */ } quicklistNode;
整體結(jié)構(gòu)
Hash
介紹
Hash 是一個(gè)鍵值對(duì)的集合,形如:key:{field1: value1,field1: value1}
,非常適合存儲(chǔ)一個(gè)對(duì)象
常用命令
# 存儲(chǔ)一個(gè)哈希表key的鍵值 HSET key field value # 獲取哈希表key對(duì)應(yīng)的field鍵值 HGET key field # 在一個(gè)哈希表key中存儲(chǔ)多個(gè)鍵值對(duì) HMSET key field value [field value...] # 批量獲取哈希表key中多個(gè)field鍵值 HMGET key field [field ...] # 刪除哈希表key中的field鍵值 HDEL key field [field ...] # 返回哈希表key中field的數(shù)量 HLEN key # 返回哈希表key中所有的鍵值 HGETALL key # 為哈希表key中field鍵的值加上增量n HINCRBY key field n
使用場(chǎng)景
緩存對(duì)象
例如下圖,對(duì)于使用 string + json
還是用 hash
來(lái)存儲(chǔ),建議優(yōu)先選擇 string + json
,對(duì)于某些字段經(jīng)常改變的話(huà),可以考慮使用 hash
購(gòu)物車(chē)
以用戶(hù) id 為 key,商品 id 為 field,商品數(shù)量為 value,恰好構(gòu)成了購(gòu)物車(chē)的 3 個(gè)要素,如下圖所示。
涉及的命令如下:
- 添加商品:HSET cart:{用戶(hù)id} {商品id} 1
- 添加數(shù)量:HINCRBY cart:{用戶(hù)id} {商品id} 1
- 商品總數(shù):HLEN cart:{用戶(hù)id}
- 刪除商品:HDEL cart:{用戶(hù)id} {商品id}
- 獲取購(gòu)物車(chē)所有商品:HGETALL cart:{用戶(hù)id}
當(dāng)前僅僅是將商品 ID 存儲(chǔ)到了 Redis 中,在回顯商品具體信息的時(shí)候,還需要拿著商品 id 查詢(xún)一次數(shù)據(jù)庫(kù),獲取完整的商品的信息。
底層實(shí)現(xiàn)
Hash 的底層實(shí)現(xiàn)可以是 ZipList 或者 Dict
- Hash結(jié)構(gòu)默認(rèn)采用
ZipList
編碼,用以節(jié)省內(nèi)存。ZipList
中相鄰的兩個(gè)entry
分別保存field
和value
- 當(dāng) ZipList 的元素個(gè)數(shù)小于 512(默認(rèn))且每個(gè) Entry 的大小小于 64 字節(jié)(默認(rèn)),則會(huì)使用 ZipList 來(lái)作為 Hash 的底層實(shí)現(xiàn),否則則使用 Dict
Dict
Dict 中維護(hù)一個(gè) 哈希表 DitHashTable
,里面有一個(gè) DictEntry 數(shù)組,用來(lái)存儲(chǔ)實(shí)際的 key-value
,每個(gè)槽位下的 DictEntry 都會(huì)形成一個(gè)鏈表,處理哈希沖突
向 Dict 插入一個(gè)元素時(shí),先會(huì)根據(jù) key 計(jì)算出一個(gè)哈希值 h,然后計(jì)算 h & sizemask 得到數(shù)組下標(biāo),最后加入該 DictEntry 即可
數(shù)據(jù)結(jié)構(gòu)體
字典(Dict)
typedef struct dict { dictType *type; // dict 類(lèi)型,不同的哈希函數(shù) void *privdata; // 私有數(shù)據(jù),做特殊hash的時(shí)候用 dictht ht[2]; // 包含兩個(gè)hash表,一個(gè)是當(dāng)前數(shù)據(jù),另個(gè)為空,rehash的時(shí)候用 long rehashidx; // rehash的進(jìn)度 int16_t pauserehash; // rehash是否暫停 } dict;
哈希表(DictHashTable)
typedef struct dictht { dictEntry **table; // 指向entry 的數(shù)組 unsigned long size; // 哈希表大小 unsigned long sizemask; // 掩碼:size - 1 unsigned long used; // entry 的個(gè)數(shù) } dictht;
哈希節(jié)點(diǎn)(DictEntry)
typedef struct dictEntry { void *key; // 鍵 union { void *val; uint64_t u64; int64_t s64; double d; } v;// 值 struct dictEntry *next;// 下一個(gè)結(jié)點(diǎn) } dictEntry;
Dict 的 rehash
不管是擴(kuò)容還是收縮,必定會(huì)創(chuàng)建新的哈希表,導(dǎo)致哈希表的 size 和 sizemask 變化,而 key 的查詢(xún)與 sizemask 有關(guān)。因此必須對(duì)哈希表中的每一個(gè) key 重新計(jì)算索引,插入新的哈希表,這個(gè)過(guò)程稱(chēng)為 rehash。過(guò)程是這樣的:
- 計(jì)算新hash表的realeSize,值取決于當(dāng)前要做的是擴(kuò)容還是收縮:
- 如果是擴(kuò)容,則新size為第一個(gè)大于等于
dict.ht[0].used + 1
的2^n - 如果是收縮,則新size為第一個(gè)大于等于
dict.ht[0].used
的2^n (不得小于4)
- 如果是擴(kuò)容,則新size為第一個(gè)大于等于
- 按照新的 realeSize 申請(qǐng)內(nèi)存空間,創(chuàng)建 dictht,并賦值給 dict.ht[1]
- 設(shè)置 dict.rehashidx = 0,標(biāo)示開(kāi)始 rehash
- 將 dict.ht[0] 中的每一個(gè) dictEntry 都 rehash 到 dict.ht[1]
- 將 dict.ht[1] 賦值給 dict.ht[0],給 dict.ht[1] 初始化為空哈希表,釋放原來(lái)的dict.ht[0]的內(nèi)存
- 將 rehashidx 賦值為 -1,代表 rehash 結(jié)束
- 在rehash過(guò)程中,新增操作,則直接寫(xiě)入ht[1] ,查詢(xún)、修改和刪除則會(huì)在dict.ht[0]和dict.ht[1]依次查找并執(zhí)行。這樣可以確保 ht[0] 的數(shù)據(jù)只減不增,隨著 rehash 最終為空
Set
介紹
Set 是 Redis 中的無(wú)序集合,可以保證元素的唯一性,但不一定保證元素的有序性,可以對(duì) set 取交集,并集等操作
常用命令
Set 常用操作
# 往集合key中存入元素,元素存在則忽略,若key不存在則新建 SADD key member [member ...] # 從集合key中刪除元素 SREM key member [member ...] # 獲取集合key中所有元素 SMEMBERS key # 獲取集合key中的元素個(gè)數(shù) SCARD key # 判斷member元素是否存在于集合key中 SISMEMBER key member # 從集合key中隨機(jī)選出count個(gè)元素,元素不從key中刪除 SRANDMEMBER key [count] # 從集合key中隨機(jī)選出count個(gè)元素,元素從key中刪除 SPOP key [count]
Set 集合操作
# 交集運(yùn)算 SINTER key [key ...] # 將交集結(jié)果存入新集合destination中 SINTERSTORE destination key [key ...] # 并集運(yùn)算 SUNION key [key ...] # 將并集結(jié)果存入新集合destination中 SUNIONSTORE destination key [key ...] # 差集運(yùn)算 SDIFF key [key ...] # 將差集結(jié)果存入新集合destination中 SDIFFSTORE destination key [key ...]
使用場(chǎng)景
點(diǎn)贊
使用 set 集合來(lái)存儲(chǔ),key 為文章 id,value為 用戶(hù) id 即可,獲取該文章的點(diǎn)贊數(shù)量取該 set 中 id 的總數(shù)即可
關(guān)注
使用 set 集合來(lái)存儲(chǔ),key 為用戶(hù) id,value 為該用戶(hù)關(guān)注的用戶(hù)的 id,可以對(duì)兩個(gè) set 取并集,就可以找出它們的共同關(guān)注
抽獎(jiǎng)
使用 set 集合來(lái)存儲(chǔ),key 為活動(dòng) id,value 為參見(jiàn)該活動(dòng)的用戶(hù)
- 若不可重復(fù)抽獎(jiǎng),則使用
SPOP key [count]
來(lái)隨機(jī)獲取count
個(gè)用戶(hù),并從 set 中移除 - 若可以重復(fù)抽獎(jiǎng),則使用
SRANDMEMBER key [count]
來(lái)隨機(jī)獲取 count 個(gè)用戶(hù),但不會(huì)從 set 中移除
底層實(shí)現(xiàn)
Set 底層是通過(guò) IntSet(整數(shù)集合)或者 Dict 來(lái)實(shí)現(xiàn)的
- 用 Dict 來(lái)存儲(chǔ)實(shí)際上和 Hash 的結(jié)構(gòu)一樣,只不過(guò)把 value 值統(tǒng)一存儲(chǔ)為 null 即可
- 當(dāng)數(shù)據(jù)都是整數(shù)時(shí),且數(shù)據(jù)的數(shù)量不超過(guò)
set-max-intset-entries
時(shí),會(huì)使用intset
來(lái)存儲(chǔ)數(shù)據(jù) - 否則則使用
Dict
來(lái)存儲(chǔ)
Intset
Intset 是 Redis 中的一種實(shí)現(xiàn)模式,基于整數(shù)數(shù)組來(lái)實(shí)現(xiàn),具備長(zhǎng)度可變,有序的特征
結(jié)構(gòu)體
typedef struct intset { uint32_t encoding; // 編碼方式 uint32_t length; // 長(zhǎng)度 int8_t contents[]; // 存儲(chǔ)位置 } intset;
encoding
:表示存儲(chǔ)整數(shù)的大小
/* Note that these encodings are ordered, so: * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */ #define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))
length
:數(shù)組的長(zhǎng)度
contents
:存儲(chǔ)實(shí)際的內(nèi)容
encoding
:4字節(jié)
length
:4字節(jié)
contents
:2字節(jié) * 3 = 6 字節(jié)
擴(kuò)容過(guò)程
我們向該其中添加一個(gè)數(shù)字:50000,這個(gè)數(shù)字超出了 int16_t 的范圍,intset 會(huì)自動(dòng)升級(jí)編碼方式到合適的大小。
以當(dāng)前案例來(lái)說(shuō)流程如下:
- 升級(jí)編碼為
INTSET_ENC_INT32
, 每個(gè)整數(shù)占 4 字節(jié),并按照新的編碼方式及元素個(gè)數(shù)擴(kuò)容數(shù)組 - 倒序依次將數(shù)組中的元素拷貝到擴(kuò)容后的正確位置
- 將待添加的元素放入數(shù)組末尾
- 最后,將 inset 的 encoding 屬性改為
INTSET_ENC_INT32
,將length
屬性改為 4
小結(jié):
- intset 可以保證 contents 的整數(shù)有序,唯一
- 因?yàn)?contents 數(shù)組有序,所以可以使用 二分查找 來(lái)快速找到目標(biāo)值
- 具備類(lèi)型升級(jí)機(jī)制,可以節(jié)省內(nèi)存空間
ZSet
介紹
ZSet 是一個(gè)有序集合類(lèi)型,比 Set 多出了一個(gè) score 字段,該字段用來(lái)對(duì) value 值進(jìn)行排序,保證 ZSet 中的值是有序的
所以每一個(gè)元素都有兩個(gè)值,一個(gè) score,用來(lái)排序,一個(gè) value 存儲(chǔ)實(shí)際的值
常用命令
ZSet 常用操作
# 往有序集合key中加入帶分值元素 ZADD key score member [[score member]...] # 往有序集合key中刪除元素 ZREM key member [member...] # 返回有序集合key中元素member的分值 ZSCORE key member # 返回有序集合key中元素個(gè)數(shù) ZCARD key # 為有序集合key中元素member的分值加上increment ZINCRBY key increment member # 正序獲取有序集合key從start下標(biāo)到stop下標(biāo)的元素 ZRANGE key start stop [WITHSCORES] # 倒序獲取有序集合key從start下標(biāo)到stop下標(biāo)的元素 ZREVRANGE key start stop [WITHSCORES] # 返回有序集合中指定分?jǐn)?shù)區(qū)間內(nèi)的成員,分?jǐn)?shù)由低到高排序。 ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count] # 返回指定成員區(qū)間內(nèi)的成員,按字典正序排列, 分?jǐn)?shù)必須相同。 ZRANGEBYLEX key min max [LIMIT offset count] # 返回指定成員區(qū)間內(nèi)的成員,按字典倒序排列, 分?jǐn)?shù)必須相同 ZREVRANGEBYLEX key max min [LIMIT offset count]
ZSet 運(yùn)算操作
# 并集計(jì)算(相同元素分值相加),numberkeys一共多少個(gè)key,WEIGHTS每個(gè)key對(duì)應(yīng)的分值乘積 ZUNIONSTORE destkey numberkeys key [key...] # 交集計(jì)算(相同元素分值相加),numberkeys一共多少個(gè)key,WEIGHTS每個(gè)key對(duì)應(yīng)的分值乘積 ZINTERSTORE destkey numberkeys key [key...]
使用場(chǎng)景
排行榜
以文章排行榜為例子,使用 article:rank 作為 key,點(diǎn)贊數(shù)量作為 score,文章的 id 作為 value 即可,根據(jù) score 從大到小進(jìn)行排序,則可以得到一個(gè) 文章熱度的排行榜。
底層實(shí)現(xiàn)
ZSet 使用 壓縮列表 或者 跳表 + 字典來(lái)實(shí)現(xiàn)
- 可以根據(jù) key 找到 value;
- 保證 value 是唯一的;
- 可以根據(jù) value 查找分?jǐn)?shù);
Ziplist 本身是沒(méi)有排序功能的,而且沒(méi)有鍵值對(duì)的概念,需要通過(guò)編碼來(lái)實(shí)現(xiàn):
- ziplist 是連續(xù)內(nèi)存,score 和 value 是相互依靠的兩個(gè) entry;
- ziplist 本身不能排序,所以只能通過(guò) score 來(lái)對(duì) entry 從小到大排序;
當(dāng)同時(shí)滿(mǎn)足一下條件時(shí),會(huì)選擇使用 Ziplist
- 元素的數(shù)量小于
zset_max_ziplist_entries
,默認(rèn)是 256 - 每個(gè)元素的內(nèi)存大小小于
zset_max_ziplist_value
字節(jié),默認(rèn)是 64 KB
否則使用 跳表 +Dict
使用 Dict 存儲(chǔ) value 和 score 的映射關(guān)系;
使用 跳表 來(lái)有序的存儲(chǔ) score 和 value 值,便于范圍查找
SkipList
跳表是一個(gè)并聯(lián)多個(gè)有序鏈表的數(shù)據(jù)結(jié)構(gòu),它可以在 O(logn) 的時(shí)間復(fù)雜度內(nèi)完成插入、刪除、增加的操作;
特點(diǎn)
- 跳表是一個(gè)雙向鏈表,每個(gè)節(jié)點(diǎn)包含 score 和 element 值
- 節(jié)點(diǎn)按 score 進(jìn)行排序
- 每個(gè)節(jié)點(diǎn)都可以包含多層指針,層數(shù)是 1 到 32 之間的隨機(jī)數(shù)
- 不同層指針到下一個(gè)節(jié)點(diǎn)的跨度不同,層級(jí)越高,跨度越大
- 增刪改查效率與紅黑樹(shù)基本一致,實(shí)現(xiàn)卻更簡(jiǎn)單
跳表代碼
public class SkipList { private final int MAX_LEVEL = 32; private final double factor = 0.25; private int level = 1; /** * 頭結(jié)點(diǎn) */ private final Node head = new Node(null, MAX_LEVEL); static class Node { Integer value; Node[] next; int size; public Node(Integer value, int size) { this.value = value; this.size = size; this.next = new Node[size]; } } public boolean search(int value) { Node p = head; for (int i = level - 1; i >= 0; i--) { while (p.next[i] != null && p.next[i].value <= value) { if (p.next[i].value == value) { return true; } p = p.next[i]; } } return false; } public void insert(int value) { int randomLevel = randomLevel(); Node newNode = new Node(value, randomLevel); Node p = head; for (int i = level - 1; i >= 0; i--) { while (p.next[i] != null && p.next[i].value <= value) { p = p.next[i]; } if (p.next[i] == null) { p.next[i] = newNode; } else { newNode.next[i] = p.next[i]; p.next[i] = newNode; } } if (randomLevel > level) { for (int i = level ; i < randomLevel ; i++) { head.next[i] = newNode; } level = randomLevel; } } public boolean delete(int value) { boolean contain = search(value); Node p = head; Node h = null; if (contain) { for (int i = level - 1; i >= 0; i--) { while (p.next[i] != null && p.next[i].value <= value) { h = p; p = p.next[i]; } h.next[i] = p.next[i]; } } return contain; } private int randomLevel() { int level = 1; Random random = new Random(); while (random.nextDouble() <= factor && level <= MAX_LEVEL) { level++; } return level; } }
以上就是Redis五種數(shù)據(jù)類(lèi)型詳解的詳細(xì)內(nèi)容,更多關(guān)于Redis數(shù)據(jù)類(lèi)型的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Redis中有序集合的內(nèi)部實(shí)現(xiàn)方式的詳細(xì)介紹
本文主要介紹了Redis中有序集合的內(nèi)部實(shí)現(xiàn)方式的詳細(xì)介紹,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03redis使用Lua腳本解決多線(xiàn)程下的超賣(mài)問(wèn)題及原因解析
這篇文章主要介紹了redis使用Lua腳本解決多線(xiàn)程下的超賣(mài)問(wèn)題,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-05-05Redis?Lua腳本實(shí)現(xiàn)ip限流示例
這篇文章主要介紹了Redis?Lua腳本實(shí)現(xiàn)ip限流示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-07-07