建站
咨詢
售后
建站咨詢
新聞中心
Redis跳表（Skip List）是一種基于鏈表的隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，可用于快速地實(shí)現(xiàn)有序集合（sorted sets）和有序映射（sorted maps）。跳表最先由William Pugh在1990年提出，Redis將其作為有序集合的底層實(shí)現(xiàn)方式之一，并對(duì)其做出了一些改進(jìn)。
跳表的基本思想是在原始的有序鏈表上增加多級(jí)索引，這樣可以快速地實(shí)現(xiàn)查找操作，同時(shí)由于隨機(jī)化技術(shù)的應(yīng)用，每個(gè)節(jié)點(diǎn)的索引層數(shù)也具有一定的隨機(jī)性，從而保證了整個(gè)數(shù)據(jù)結(jié)構(gòu)的平衡性和穩(wěn)定性。跳表的時(shí)間復(fù)雜度為O(log N)，與平衡二叉樹相當(dāng)，但由于跳表的實(shí)現(xiàn)較為簡(jiǎn)單，可以避免復(fù)雜的旋轉(zhuǎn)操作和節(jié)點(diǎn)調(diào)整，因此實(shí)際使用起來(lái)更加便利和高效。
Redis跳表的實(shí)現(xiàn)結(jié)構(gòu)主要包括：
1. 節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
Redis的跳表節(jié)點(diǎn)共有三個(gè)成員：Score（分值，用于排序）、Object（對(duì)象指針，指向?qū)嶋H存儲(chǔ)的數(shù)據(jù)對(duì)象）、level（跳表層數(shù)，即節(jié)點(diǎn)的索引數(shù)）。節(jié)點(diǎn)的層數(shù)在插入操作時(shí)會(huì)根據(jù)隨機(jī)數(shù)重新生成，最多不超過(guò)32層。
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
2. 跳表數(shù)據(jù)結(jié)構(gòu)
Redis的跳表結(jié)構(gòu)包括頭節(jié)點(diǎn)、尾節(jié)點(diǎn)和兩個(gè)指針（指向第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)）。跳表還可以有多個(gè)層級(jí)，每個(gè)層級(jí)鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)會(huì)被記錄下來(lái)，以支持快速向前或向后遍歷。
typedef struct zskiplist {
struct zskiplistNode *header, *tl;
unsigned long length;
int level;
} zskiplist;
3. 插入操作
Redis跳表的插入操作需要分為兩部分：首先為新節(jié)點(diǎn)生成隨機(jī)層數(shù)，然后從上至下遍歷每一層鏈表，找到應(yīng)該插入的位置，將新節(jié)點(diǎn)插入，并更新該節(jié)點(diǎn)到表尾之間的所有跨度值（span），同時(shí)更新整個(gè)跳表的長(zhǎng)度和索引。
int zsl-Insert(zskiplist *zsl, double score, robj *obj) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
/* 生成隨機(jī)層數(shù) */
level = zslRandomLevel();
/* 遍歷每一層鏈表，找到應(yīng)該插入的位置 */
x = zsl->header;
for (i = level-1; i >= 0; i–) {
rank[i] = i == (level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj)
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
/* 創(chuàng)建新節(jié)點(diǎn) */
level = level > zsl->level ? zsl->level+1 : level;
x = zslCreateNode(level,score,obj);
/* 更新每一層鏈表 */
for (i = 0; i
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span –
(rank[0] – rank[i]);
update[i]->level[i].span = (rank[0] – rank[i]) + 1;
}
for (i = level; i level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tl = x;
/* 更新跳表信息 */
zsl->length++;
return 1;
}
4. 刪除操作
Redis跳表的刪除操作比較簡(jiǎn)單，只需要遍歷鏈表找到待刪除節(jié)點(diǎn)，然后從上至下刪除該節(jié)點(diǎn)，并更新整個(gè)跳表的長(zhǎng)度和索引。
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
/* 更新每一層鏈表 */
for (i = 0; i level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span – 1;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span–;
}
}
/* 更新后繼節(jié)點(diǎn)的 backward 指針 */
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
} else {
zsl->tl = x->backward;
}
/* 更新跳表信息 */
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level–;
zsl->length–;
}
5. 查詢操作
Redis跳表的查詢操作也比較簡(jiǎn)單，只需要從上至下遍歷每一層鏈表，找到第一個(gè)score值大于或等于給定的score值的節(jié)點(diǎn)，即可實(shí)現(xiàn)分值范圍查詢。
zskiplistNode *zslFirstInRange(zskiplist *zsl, double min, double max) {
zskiplistNode *x;
int i;
/* 從最高層開始查找 */
x = zsl->header;
for (i = zsl->level-1; i >= 0; i–) {
while (x->level[i].forward && x->level[i].forward->score
x = x->level[i].forward;
}
/* 返回第一個(gè) score 值大于等于 min 的節(jié)點(diǎn) */
x = x->level[0].forward;
if (x == NULL || x->score > max)
return NULL;
return x;
}
本文介紹了Redis跳表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)原理和代碼，希望能對(duì)Redis開發(fā)和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)有所幫助。實(shí)際使用時(shí)，還需要根據(jù)具體業(yè)務(wù)場(chǎng)景不斷優(yōu)化和改進(jìn)跳表的實(shí)現(xiàn)方式，以達(dá)到更高效、更可靠的數(shù)據(jù)存儲(chǔ)和查詢。
成都服務(wù)器托管選創(chuàng)新互聯(lián)，先上架開通再付費(fèi)。
創(chuàng)新互聯(lián)（www.cdcxhl.com）專業(yè)-網(wǎng)站建設(shè),軟件開發(fā)老牌服務(wù)商！微信小程序開發(fā),APP開發(fā),網(wǎng)站制作，網(wǎng)站營(yíng)銷推廣服務(wù)眾多企業(yè)。電話：028-86922220
網(wǎng)站欄目：研究Redis跳表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)（redis的跳表實(shí)現(xiàn)）
分享鏈接：http://www.dlmjj.cn/article/dhpggcj.html
