redis中跳表zset的具體使用
跳表的基本思想
Skip List(跳躍列表)這種隨機(jī)的數(shù)據(jù)結(jié)構(gòu)，可以看做是一個(gè)二叉樹的變種，它在性能上與紅黑樹、AVL樹很相近；但是Skip List(跳躍列表)的實(shí)現(xiàn)相比前兩者要簡(jiǎn)單很多，目前Redis的zset實(shí)現(xiàn)采用了Skip List(跳躍列表)。
特點(diǎn)
1、分層，每層由有序鏈表構(gòu)成
2、頭節(jié)點(diǎn)在每層出現(xiàn)
3、某個(gè)節(jié)點(diǎn)如果在上層出現(xiàn)，那在下層也出現(xiàn)
4、節(jié)點(diǎn)的層數(shù)是隨機(jī)的
節(jié)點(diǎn)與結(jié)構(gòu)
跳躍表節(jié)點(diǎn)zskiplistNode
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
屬性
- ele：存儲(chǔ)字符串?dāng)?shù)據(jù)
- score：存儲(chǔ)排序分值
- *backward：指針，指向當(dāng)前節(jié)點(diǎn)最底層的前一個(gè)節(jié)點(diǎn)
- level[]：柔性數(shù)組，隨機(jī)生成1-64的值
- forward：指向本層下一個(gè)節(jié)點(diǎn)
- span：本層下個(gè)節(jié)點(diǎn)到本節(jié)點(diǎn)的元素個(gè)數(shù)
跳躍表鏈表
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
屬性
- header，tail：頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
- length：跳躍表長(zhǎng)度（不包括頭節(jié)點(diǎn)）
- tail：跳躍表高度
跳表的設(shè)計(jì)思想和優(yōu)勢(shì)
1、能夠同時(shí)擁有鏈表和數(shù)優(yōu)勢(shì)的數(shù)據(jù)結(jié)構(gòu)，既有鏈表插入快的特點(diǎn)又有數(shù)組查詢快的特點(diǎn)
2、隨機(jī)跨越層數(shù)
3、最底層的鏈表是雙向鏈表，包含所有元素
4、對(duì)于有序鏈表查詢優(yōu)化，相比較于平衡數(shù)來說，更好實(shí)現(xiàn)
5、內(nèi)存占用上來看，相比較于平衡數(shù)會(huì)更少
API解析
Tip：以下的zsl為zskiplist
zslCreate（創(chuàng)建跳躍表）
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
大致流程：
1、定義一個(gè)zsl，申請(qǐng)內(nèi)存，賦初始值
2、調(diào)用zslCreateNode創(chuàng)建出頭節(jié)點(diǎn)
3、每層頭節(jié)點(diǎn)賦初始值
4、尾節(jié)點(diǎn)賦null值
zslCreateNode（創(chuàng)建節(jié)點(diǎn)）
/* Create a skiplist node with the specified number of levels.
* The SDS string 'ele' is referenced by the node after the call. */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
大致流程：
1、申請(qǐng)內(nèi)存（節(jié)點(diǎn)內(nèi)存和柔性數(shù)組的內(nèi)存）
2、屬性賦值
zslGetRank（查找排位）
排位就是累積跨越的節(jié)點(diǎn)數(shù)量
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}
/* x might be equal to zsl->header, so test if obj is non-NULL */
if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}
大致流程：
1、從最上層開始遍歷節(jié)點(diǎn)并對(duì)比元素，對(duì)比score
2、如果當(dāng)前分值大雨下一個(gè)分值，則累加span（比對(duì)分值，如果分值一樣就比對(duì)ele）
3、指向本層的下一個(gè)節(jié)點(diǎn)
4、如果找到了，也就是ele相同，則返回
zslDelete（刪除節(jié)點(diǎn)）
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
/* We may have multiple elements with the same score, what we need
* is to find the element with both the right score and object. */
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!node)
zslFreeNode(x);
else
*node = x;
return 1;
}
return 0; /* not found */
}
大致流程：
1、遍歷跳表
2、比對(duì)分值，比對(duì)ele
3、如分值小于或等于當(dāng)前值，并且ele不相等，繼續(xù)下一個(gè)并記錄節(jié)點(diǎn)
4、如分值和ele都相同，調(diào)用zslDeleteNode刪除該節(jié)點(diǎn)
跳表是在很多排名以及分?jǐn)?shù)相關(guān)的場(chǎng)景中使用頻率極高的數(shù)據(jù)結(jié)構(gòu)，也是設(shè)計(jì)的極其巧妙的一種結(jié)構(gòu)，希望本篇文章能幫助各位更加深入的理解這種結(jié)構(gòu)。
到此這篇關(guān)于redis中跳表zset的具體使用的文章就介紹到這了,更多相關(guān)redis 跳表zset內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Redis進(jìn)行驗(yàn)證碼登錄的項(xiàng)目實(shí)踐
本文主要介紹了Redis進(jìn)行驗(yàn)證碼登錄的項(xiàng)目實(shí)踐,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-09-09
Redis主從復(fù)制與讀寫分離的實(shí)現(xiàn)
Redis在作為緩存的時(shí)候,隨著項(xiàng)目訪問量的增加,對(duì)Redis服務(wù)器的操作也越加頻繁,雖然Redis讀寫速度都很快,但是一定程度上也會(huì)造成一定的延時(shí),本文主要介紹了Redis主從復(fù)制與讀寫分離的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-12-12
當(dāng)Redis存儲(chǔ)一億key時(shí),使用keys指令可能因返回全部key導(dǎo)致服務(wù)器卡頓,而scan指令通過游標(biāo)分批獲取,避免阻塞,適合生產(chǎn)環(huán)境,需注意重復(fù)結(jié)果可用hashSet去重,count參數(shù)可調(diào)整返回?cái)?shù)量但非強(qiáng)制2025-07-07
Redis?存儲(chǔ)對(duì)象信息用?Hash?和String的區(qū)別
這篇文章主要介紹了Redis存儲(chǔ)對(duì)象信息用Hash和String的區(qū)別，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
超賣問題通常出現(xiàn)在多用戶并發(fā)操作的情況下,即多個(gè)用戶嘗試購買同一件商品,導(dǎo)致商品庫存不足或者超賣,本文就來介紹一下超賣問題,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了Redis 緩存刪除機(jī)制(源碼解析)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要介紹了redis++的編譯?安裝?使用方案的相關(guān)資料,需要的朋友可以參考下2023-03-03
這篇文章主要介紹了CentOS6.4 安裝Redis 教程詳解,需要的朋友可以參考下2017-05-05
Redis?RESP?協(xié)議實(shí)現(xiàn)實(shí)例詳解
這篇文章主要為大家介紹了Redis?RESP?協(xié)議實(shí)現(xiàn)實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
Linux系統(tǒng)下安裝Redis數(shù)據(jù)庫過程
大家好，本篇文章主要講的是Linux系統(tǒng)下安裝Redis數(shù)據(jù)庫過程，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12