Redis跳表（Skip List）是一種基于鏈表的隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，可用于快速地實(shí)現(xiàn)有序集合（sorted sets）和有序映射（sorted maps）。跳表最先由William Pugh在1990年提出，Redis將其作為有序集合的底層實(shí)現(xiàn)方式之一，并對其做出了一些改進(jìn)。

跳表的基本思想是在原始的有序鏈表上增加多級索引，這樣可以快速地實(shí)現(xiàn)查找操作，同時由于隨機(jī)化技術(shù)的應(yīng)用，每個節(jié)點(diǎn)的索引層數(shù)也具有一定的隨機(jī)性，從而保證了整個數(shù)據(jù)結(jié)構(gòu)的平衡性和穩(wěn)定性。跳表的時間復(fù)雜度為O(log N)，與平衡二叉樹相當(dāng)，但由于跳表的實(shí)現(xiàn)較為簡單，可以避免復(fù)雜的旋轉(zhuǎn)操作和節(jié)點(diǎn)調(diào)整，因此實(shí)際使用起來更加便利和高效。

Redis跳表的實(shí)現(xiàn)結(jié)構(gòu)主要包括：

1. 節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

Redis的跳表節(jié)點(diǎn)共有三個成員：Score（分值，用于排序）、Object（對象指針，指向?qū)嶋H存儲的數(shù)據(jù)對象）、level（跳表層數(shù)，即節(jié)點(diǎn)的索引數(shù)）。節(jié)點(diǎn)的層數(shù)在插入操作時會根據(jù)隨機(jī)數(shù)重新生成，最多不超過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)和兩個指針（指向第一個節(jié)點(diǎn)和最后一個節(jié)點(diǎn)）。跳表還可以有多個層級，每個層級鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)會被記錄下來，以支持快速向前或向后遍歷。

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），同時更新整個跳表的長度和索引。

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é)點(diǎn)，然后從上至下刪除該節(jié)點(diǎn)，并更新整個跳表的長度和索引。

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跳表的查詢操作也比較簡單，只需要從上至下遍歷每一層鏈表，找到第一個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;

}

/* 返回第一個 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)原理和代碼，希望能對Redis開發(fā)和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)有所幫助。實(shí)際使用時，還需要根據(jù)具體業(yè)務(wù)場景不斷優(yōu)化和改進(jìn)跳表的實(shí)現(xiàn)方式，以達(dá)到更高效、更可靠的數(shù)據(jù)存儲和查詢。

成都服務(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)站營銷推廣服務(wù)眾多企業(yè)。電話：028-86922220

標(biāo)題名稱：研究Redis跳表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)（redis的跳表實(shí)現(xiàn)）
新聞來源：http://uogjgqi.cn/article/dhpggcj.html