建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
Redis: 從跳躍表的源碼分析
創(chuàng)新互聯(lián)建站于2013年成立，先為秀峰等服務(wù)建站，秀峰等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢(xún)服務(wù)。為秀峰企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
Redis是一個(gè)高效的內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)，其內(nèi)部數(shù)據(jù)結(jié)構(gòu)扮演了非常重要的角色。其中，跳躍表(Skiplist)就是Redis內(nèi)部用于實(shí)現(xiàn)有序集合的重要數(shù)據(jù)結(jié)構(gòu)。本文將會(huì)從Redis中跳躍表的源碼分析入手，詳細(xì)探究其實(shí)現(xiàn)原理。
1. 跳躍表的定義和特點(diǎn)
跳躍表是一種有序數(shù)據(jù)結(jié)構(gòu)，由多個(gè)層次(級(jí)別)組成，每個(gè)級(jí)別都是一個(gè)簡(jiǎn)單的有序鏈表。可以把它看做是并行的多個(gè)鏈表，其中低層鏈表作為頂層鏈表的基礎(chǔ)，在頂層鏈表上形成了“躍遷”的效果，以此提高查詢(xún)效率。跳躍表最大的優(yōu)勢(shì)是在平均時(shí)間復(fù)雜度O(logN)的情況下，提供了近似于二分查找的性能，并具有快速的插入和刪除操作的特點(diǎn)。
Redis跳躍表結(jié)構(gòu)體定義如下：
typedef struct zskiplistNode {
sds ele; // 成員對(duì)象
double score; // 分值
struct zskiplistNode *backward; // 后退指針
struct zskiplistlevel {
struct zskiplistNode *forward; // 前進(jìn)指針
unsigned int span; // 跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tl;
unsigned long length;
int level;
} zskiplist;
其中，zskiplistNode表示一個(gè)跳躍表的節(jié)點(diǎn)，它包含了節(jié)點(diǎn)的成員對(duì)象(sds ele)和分值(double score)，以及用于指示節(jié)點(diǎn)位置的前進(jìn)指針和后退指針。zskiplist則是跳躍表對(duì)象，包含了指向頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的指針，跳躍表中節(jié)點(diǎn)的數(shù)量和跳躍表的節(jié)點(diǎn)層數(shù)。
2. 跳躍表的實(shí)現(xiàn)原理
跳躍表的插入操作
在Redis跳躍表中，插入操作的基本流程如下：
1. 查找插入位置：從頂層鏈表開(kāi)始，依次向下遍歷每一層鏈表，找到插入位置。過(guò)程中記錄查找路徑上每個(gè)節(jié)點(diǎn)到下一級(jí)節(jié)點(diǎn)的距離（即跨度），以便構(gòu)建新節(jié)點(diǎn)的跨度表。
2. 添加新節(jié)點(diǎn)：創(chuàng)建新節(jié)點(diǎn)z，把在上一步中記錄的跨度信息中的所有節(jié)點(diǎn)都更新，確保它們都能指向新節(jié)點(diǎn)z，并使新節(jié)點(diǎn)z指向相應(yīng)跨度表的下一個(gè)節(jié)點(diǎn)。
3. 更新相鄰節(jié)點(diǎn)跨度信息：從插入位置出發(fā)，依次修改所有相鄰節(jié)點(diǎn)的跨度信息（在新節(jié)點(diǎn)z被插入之后的相鄰節(jié)點(diǎn)），并把它們更新到跨度表中。
代碼實(shí)現(xiàn)如下：
zskiplistNode *zsl-Insert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i–) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele)
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
/* we assume the element is not already inside, since we allow duplicated
* scores, reinserting the same element should never happen since the
* caller of zslInsert() should test in the hash table if the element is
* already inside or not. */
level = zslRandomLevel();
if (level > zsl->level) {
for (i = zsl->level; i
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level,score,ele);
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 x;
}
該函數(shù)首先定義了一個(gè)記錄已處理的跳躍表節(jié)點(diǎn)、當(dāng)前插入節(jié)點(diǎn)位置和插入節(jié)點(diǎn)信息的變量，并遍歷所有層的鏈表找到插入點(diǎn)。隨后，它更新跳躍表中所有相鄰節(jié)點(diǎn)的跨度信息，并更新新節(jié)點(diǎn)的前進(jìn)指針和后退指針，完成插入操作。
跳躍表的刪除操作
跳躍表中節(jié)點(diǎn)的刪除操作，需要涉及到跳躍表節(jié)點(diǎn)間的鏈接關(guān)系的更新?；玖鞒倘缦拢?/p>
1. 查找刪除節(jié)點(diǎn)：從頂層鏈表開(kāi)始，依次向下遍歷每一層鏈表，找到要?jiǎng)h除的節(jié)點(diǎn)。過(guò)程中記錄查找路徑上每個(gè)節(jié)點(diǎn)到下一級(jí)節(jié)點(diǎn)的距離和需要?jiǎng)h除的節(jié)點(diǎn)的層數(shù)，以便修改相關(guān)節(jié)點(diǎn)的跨度表。
2. 修改相鄰節(jié)點(diǎn)的跨度信息：當(dāng)找到待刪除節(jié)點(diǎn)時(shí)，依次修改該節(jié)點(diǎn)和其前一個(gè)節(jié)點(diǎn)的跨度信息，把它們更新到跨度表中。
代碼實(shí)現(xià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 -= 1;
}
}
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–;
return;
}
該函數(shù)首先遍歷所有層的鏈表，找到待刪除節(jié)點(diǎn)，并記錄查找路徑上每個(gè)節(jié)點(diǎn)到下一級(jí)節(jié)點(diǎn)的距離以及需要?jiǎng)h除的節(jié)點(diǎn)的層數(shù)，便于刪除節(jié)點(diǎn)。隨后，它處理待刪除節(jié)點(diǎn)和跳躍表中相鄰節(jié)點(diǎn)的跨度，以便反映節(jié)點(diǎn)間的新鏈接關(guān)系。函數(shù)減少跳躍表中節(jié)點(diǎn)的數(shù)量，并返回。
3. 跳躍表的查詢(xún)操作
跳躍表在查找過(guò)程中以O(shè)(logN)的時(shí)間復(fù)雜度，快速找到節(jié)點(diǎn)。查找基本流程如下：
1. 從頂層鏈表開(kāi)始遍歷，高層查找時(shí)，若節(jié)點(diǎn)x的后退指針不為空，則向后退指
創(chuàng)新互聯(lián)成都網(wǎng)站建設(shè)公司提供專(zhuān)業(yè)的建站服務(wù)，為您量身定制，歡迎來(lái)電（028-86922220）為您打造專(zhuān)屬于企業(yè)本身的網(wǎng)絡(luò)品牌形象。
成都創(chuàng)新互聯(lián)品牌官網(wǎng)提供專(zhuān)業(yè)的網(wǎng)站建設(shè)、設(shè)計(jì)、制作等服務(wù)，是一家以網(wǎng)站建設(shè)為主要業(yè)務(wù)的公司，在網(wǎng)站建設(shè)、設(shè)計(jì)和制作領(lǐng)域具有豐富的經(jīng)驗(yàn)。
名稱(chēng)欄目：Redis從跳躍表的源碼分析（redis源碼跳躍表）
網(wǎng)站網(wǎng)址：http://www.dlmjj.cn/article/dhehehp.html
