Redis常見(jiàn)數(shù)據(jù)結(jié)構(gòu)以及使用場(chǎng)景分別是什么?
哈希表typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼,用于計(jì)算索引值
// 總是等于size-1
unsigned long sizemark;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dichht;
哈希算法
當(dāng)字典被用作數(shù)據(jù)庫(kù)的底層實(shí)現(xiàn),或者哈希鍵的底層實(shí)現(xiàn)時(shí),Redis使用MurmurHash算法。這種算法的優(yōu)點(diǎn)在于即使輸入的鍵是規(guī)律的,算法仍能給出一個(gè)個(gè)很好的隨機(jī)分布性,并且算法的計(jì)算速度非?臁
哈希沖突的解決方式
Redis的哈希表使用鏈地址法來(lái)解決鍵沖突,每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next指針,多個(gè)哈希表節(jié)點(diǎn)可以用這個(gè)單向鏈表連接起來(lái),這就解決了鍵沖突的問(wèn)題。
特性字典被廣泛用于實(shí)現(xiàn)Redis的各種功能,其中包括數(shù)據(jù)庫(kù)和哈希鍵。Redis中的字典使用哈希表作為底層結(jié)構(gòu)實(shí)現(xiàn),每個(gè)字典帶有兩個(gè)哈希表,一個(gè)平時(shí)使用,另一個(gè)僅在進(jìn)行rehash時(shí)使用。Redis使用MurmurHash2算法來(lái)計(jì)算鍵的哈希值。哈希表使用鏈地址法來(lái)解決鍵沖突。跳躍表
先看這樣一張圖:
如上圖,我們要查找一個(gè)元素,就需要從頭節(jié)點(diǎn)開(kāi)始遍歷,直到找到對(duì)應(yīng)的節(jié)點(diǎn)或者是第一個(gè)大于要查找的元素的節(jié)點(diǎn)(沒(méi)找到)。時(shí)間復(fù)雜度為O(N)。
這個(gè)查找效率是比較低的,但如果我們把列表的某些節(jié)點(diǎn)拔高一層,如下圖,例如把每?jī)蓚(gè)節(jié)點(diǎn)中有一個(gè)節(jié)點(diǎn)變成兩層。那么第二層的節(jié)點(diǎn)只有第一層的一半,查找效率也就會(huì)提高。
查找的步驟是從頭節(jié)點(diǎn)的頂層開(kāi)始,查到第一個(gè)大于指定元素的節(jié)點(diǎn)時(shí),退回上一節(jié)點(diǎn),在下一層繼續(xù)查找。
比如我們要查找16:
從頭節(jié)點(diǎn)的最頂層開(kāi)始,先到節(jié)點(diǎn)7。7的下一個(gè)節(jié)點(diǎn)是39,大于16,因此我們退回到7從7開(kāi)始,在下一層繼續(xù)查找,就可以找到16。
這個(gè)例子中遍歷的節(jié)點(diǎn)不比一維列表少,但是當(dāng)節(jié)點(diǎn)更多,查找的數(shù)字更大時(shí),這種做法的優(yōu)勢(shì)就體現(xiàn)出來(lái)了。還是上面的例子,如果我們要查找的是39,那么只需要訪問(wèn)兩個(gè)節(jié)點(diǎn)(7、39)就可以找到了。這比一維列表要減少一半的數(shù)量。
為了避免插入操作的時(shí)間復(fù)雜度是O(N),skiplist每層的數(shù)量不會(huì)嚴(yán)格按照2:1的比例,而是對(duì)每個(gè)要插入的元素隨機(jī)一個(gè)層數(shù)。
隨機(jī)層數(shù)的計(jì)算過(guò)程如下:
每個(gè)節(jié)點(diǎn)都有第一層那么它有第二層的概率是p,有第三層的概率是p*p不能超過(guò)最大層數(shù)zskiplistNodetypedef struct zskiplistNode {
// 后退指針
struct zskiplistNode *backward;
// 分值 權(quán)重
double score;
// 成員對(duì)象
robj *obj;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} leval[];
} zskiplistNode;
一般來(lái)說(shuō),層的數(shù)量越多,訪問(wèn)其他節(jié)點(diǎn)的速度越快。
zskipListtypedef struct zskiplist {
// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
struct zskiplistNode *header, *tail;
// 表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
// 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int leval;
} zskiplist;
特性跳躍表是有序集合的底層實(shí)現(xiàn)之一Redis的跳躍表實(shí)現(xiàn)由zskiplist和zskiplistNode兩個(gè)結(jié)構(gòu)組成,其中zskiplist用于保存跳躍表信息(比如表頭節(jié)點(diǎn)、表尾節(jié)點(diǎn)、長(zhǎng)度),而zskiplistNode則用于表示跳躍表節(jié)點(diǎn)每個(gè)跳躍表節(jié)點(diǎn)的層高都是1至32之間的隨機(jī)數(shù)在同一個(gè)跳躍表中,多個(gè)節(jié)點(diǎn)可以包含相同的分值,但每個(gè)節(jié)點(diǎn)的成員對(duì)象必須是唯一的。跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序,當(dāng)分值相同時(shí),節(jié)點(diǎn)按照成員對(duì)象的大小進(jìn)行排序。跳表是一種實(shí)現(xiàn)起來(lái)很簡(jiǎn)單,單層多指針的鏈表,它查找效率很高,堪比優(yōu)化過(guò)的二叉平衡樹(shù),且比平衡樹(shù)的實(shí)現(xiàn)。壓縮列表“
壓縮列表(ziplist)是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng),并且每個(gè)列表項(xiàng)要么就是小整數(shù)值,要么就是長(zhǎng)度比較短的字符串,那么Redis就會(huì)使用壓縮列表來(lái)做列表鍵的底層實(shí)現(xiàn)。
特性
看他的名字就能看出來(lái),是為了節(jié)省內(nèi)存造的列表結(jié)構(gòu)。
3、Redis常見(jiàn)數(shù)據(jù)結(jié)構(gòu)以及使用場(chǎng)景分別是什么?
String
String數(shù)據(jù)結(jié)構(gòu)是簡(jiǎn)單的key-value類(lèi)型,value其實(shí)不僅可以是String,也可以是數(shù)字。常規(guī)key-value緩存應(yīng)用;常規(guī)計(jì)數(shù):微博數(shù),粉絲數(shù)等。
Hash
Hash 是一個(gè) string 類(lèi)型的 ?eld 和 value 的映射表,hash 特別適合用于存儲(chǔ)對(duì)象,后續(xù)操作的時(shí)候,你可以直接僅 僅修改這個(gè)對(duì)象中的某個(gè)字段的值。比如我們可以Hash數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)用戶(hù)信息,商品信息等。
List
list 就是鏈表,Redis list 的應(yīng)用場(chǎng)景非常多,也是Redis最重要的數(shù)據(jù)結(jié)構(gòu)之一,比如微博的關(guān)注列表,粉絲列表, 消息列表等功能都可以用Redis的 list 結(jié)構(gòu)來(lái)實(shí)現(xiàn)。
Redis list 的實(shí)現(xiàn)為一個(gè)雙向鏈表,即可以支持反向查找和遍歷,更方便操作,不過(guò)帶來(lái)了部分額外的內(nèi)存開(kāi)銷(xiāo)。
另外可以通過(guò) lrange 命令,就是從某個(gè)元素開(kāi)始讀取多少個(gè)元素,可以基于 list 實(shí)現(xiàn)分頁(yè)查詢(xún),這個(gè)很棒的一個(gè)功 能,基于 Redis 實(shí)現(xiàn)簡(jiǎn)單的高性能分頁(yè),可以做類(lèi)似微博那種下拉不斷分頁(yè)的東西(一頁(yè)一頁(yè)的往下走),性能高。
Set
set 對(duì)外提供的功能與list類(lèi)似是一個(gè)列表的功能,特殊之處在于 set 是可以自動(dòng)排重的。
當(dāng)你需要存儲(chǔ)一個(gè)列表數(shù)據(jù),又不希望出現(xiàn)重復(fù)數(shù)據(jù)時(shí),set是一個(gè)很好的選擇,并且set提供了判斷某個(gè)成員是否在 一個(gè)set集合內(nèi)的重要接口,這個(gè)也是list所不能提供的。可以基于 set 輕易實(shí)現(xiàn)交集、并集、差集的操作。
比如:在微博應(yīng)用中,可以將一個(gè)用戶(hù)所有的關(guān)注人存在一個(gè)集合中,將其所有粉絲存在一個(gè)集合。Redis可以非常 方便的實(shí)現(xiàn)如共同關(guān)注、共同粉絲、共同喜好等功能。這個(gè)過(guò)程也就是求交集的過(guò)程,具體命令如下:sinterstore key1 key2 key3將交集存在key1內(nèi)。
Sorted Set
和set相比,sorted set增加了一個(gè)權(quán)重參數(shù)score,使得集合中的元素能夠按score進(jìn)行有序排列。
舉例:在直播系統(tǒng)中,實(shí)時(shí)排行信息包含直播間在線用戶(hù)列表,各種禮物排行榜,彈幕消息(可以理解為按消息維 度的消息排行榜)等信息,適合使用 Redis 中的 SortedSet 結(jié)構(gòu)進(jìn)行存儲(chǔ)。
發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
即日-10.29立即報(bào)名>> 2024德州儀器嵌入式技術(shù)創(chuàng)新發(fā)展研討會(huì)
-
10月31日立即下載>> 【限時(shí)免費(fèi)下載】TE暖通空調(diào)系統(tǒng)高效可靠的組件解決方案
-
即日-11.13立即報(bào)名>>> 【在線會(huì)議】多物理場(chǎng)仿真助跑新能源汽車(chē)
-
11月14日立即報(bào)名>> 2024工程師系列—工業(yè)電子技術(shù)在線會(huì)議
-
12月19日立即報(bào)名>> 【線下會(huì)議】OFweek 2024(第九屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會(huì)
-
即日-12.26火熱報(bào)名中>> OFweek2024中國(guó)智造CIO在線峰會(huì)
推薦專(zhuān)題
- 1 Intel宣布40年來(lái)最重大轉(zhuǎn)型:年底前裁員15000人、拋掉2/3房產(chǎn)
- 2 因美封殺TikTok,字節(jié)股價(jià)骨折!估值僅Meta1/5
- 3 宏山激光重磅發(fā)布行業(yè)解決方案,助力智能制造產(chǎn)業(yè)新飛躍
- 4 國(guó)產(chǎn)AI芯片公司破產(chǎn)!白菜價(jià)拍賣(mài)
- 5 具身智能火了,但規(guī)模落地還需時(shí)間
- 6 三次錯(cuò)失風(fēng)口!OpenAI前員工殺回AI編程賽道,老東家捧金相助
- 7 國(guó)產(chǎn)英偉達(dá)們,抓緊沖刺A股
- 8 英特爾賦能智慧醫(yī)療,共創(chuàng)數(shù)字化未來(lái)
- 9 英偉達(dá)的麻煩在后頭?
- 10 將“網(wǎng)紅”變成“商品”,AI“爆改”實(shí)力拉滿(mǎn)
- 高級(jí)軟件工程師 廣東省/深圳市
- 自動(dòng)化高級(jí)工程師 廣東省/深圳市
- 光器件研發(fā)工程師 福建省/福州市
- 銷(xiāo)售總監(jiān)(光器件) 北京市/海淀區(qū)
- 激光器高級(jí)銷(xiāo)售經(jīng)理 上海市/虹口區(qū)
- 光器件物理工程師 北京市/海淀區(qū)
- 激光研發(fā)工程師 北京市/昌平區(qū)
- 技術(shù)專(zhuān)家 廣東省/江門(mén)市
- 封裝工程師 北京市/海淀區(qū)
- 結(jié)構(gòu)工程師 廣東省/深圳市