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