建站
咨詢
售后
建站咨詢
新聞中心
深入淺出：Redis 跳表的實現(xiàn)原理
創(chuàng)新互聯(lián)是一家專業(yè)從事成都網(wǎng)站設(shè)計、成都做網(wǎng)站、網(wǎng)頁設(shè)計的品牌網(wǎng)絡(luò)公司。如今是成都地區(qū)具影響力的網(wǎng)站設(shè)計公司,作為專業(yè)的成都網(wǎng)站建設(shè)公司,創(chuàng)新互聯(lián)依托強大的技術(shù)實力、以及多年的網(wǎng)站運營經(jīng)驗,為您提供專業(yè)的成都網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)及網(wǎng)站設(shè)計開發(fā)服務(wù)！
Redis 是一款高性能的開源內(nèi)存數(shù)據(jù)存儲系統(tǒng)。在 Redis 中，跳表（Skip List）被廣泛應(yīng)用于有序集合的實現(xiàn)中。今天，我們將深入淺出地了解 Redis 跳表的實現(xiàn)原理，幫助更好地理解 Redis 底層數(shù)據(jù)結(jié)構(gòu)。
跳表的定義
跳表是一種可以支持快速查找、插入、刪除的有序數(shù)據(jù)結(jié)構(gòu)。跳表由于具有高效的查找性能、容易實現(xiàn)等優(yōu)點，成為了 Redis 內(nèi)部實現(xiàn)有序集合的一種常用數(shù)據(jù)結(jié)構(gòu)。
跳表的結(jié)構(gòu)
跳表的整體結(jié)構(gòu)是一個多層的鏈表，每一層都是一個有序序列，每個節(jié)點除了記錄本節(jié)點的值和指向下一個節(jié)點的指針外，還會記錄該節(jié)點在高層鏈表中的指針。以下是一個三層跳表的示意圖：
跳表的節(jié)點定義如下：
“`c
typedef struct skipListNode {
int score;
struct skipListNode *forward[1];
}skipListNode;
參數(shù)說明：
score：節(jié)點的分值，用于排序；
forward：前向指針數(shù)組，在每一層都指向下一個節(jié)點，共計 n 層，數(shù)組大小為 forward[0] 至 forward[n]；
跳表查詢
當(dāng)跳表中存在 n 個節(jié)點時，對其中分值為 x 的節(jié)點進行查詢，遍歷的次數(shù)不超過 logn 代價最低。 執(zhí)行跳表查詢?nèi)缦拢?br>
1.初始化指針
從最高層開始，將指針指向?qū)?yīng)節(jié)點。
2.開始查找
從最高層開始，如果下一個節(jié)點的分值比目標分值小，就繼續(xù)遍歷下一個節(jié)點，直到找到查詢的分值或者下一個節(jié)點的分值比目標分值大。
3.下移指針
如果下一個節(jié)點的分值比目標分值大，就將指針下移一層，并重新執(zhí)行步驟2。
跳表插入
在跳表中插入一個新節(jié)點時，需要找到插入位置并插入節(jié)點。插入節(jié)點有 50% 的概率會在某一層被插入，而在下一級序列不出現(xiàn)。執(zhí)行跳表插入的步驟如下：
1. 通過查詢找到待插入節(jié)點的位置，并預(yù)先設(shè)置層數(shù)。
在插入節(jié)點之前，先從頭開始查找要插入的位置，預(yù)先確定插入節(jié)點的所在層數(shù)。
2. 更新層信息
插入新節(jié)點后，須更新跳表每層中指向相鄰節(jié)點的指針，同時確定插入節(jié)點的層數(shù)。
3. 完成插入操作
跳表刪除
在跳表已知的刪除節(jié)點后，需要找到刪除節(jié)點的前后節(jié)點。為了保持跳表整體的有序性，必須依次刪除該節(jié)點在各個層中的指針，并將前后節(jié)點的指針互相連接。執(zhí)行跳表刪除的步驟如下：
1. 從最高層開始遍歷找到要被刪除的節(jié)點，并記錄其所有前繼節(jié)點。
2. 遍歷所有前繼節(jié)點，并更新掉該節(jié)點在上一層的指針，如下圖所示，刪除節(jié)點 16 后需要重建節(jié)點 14 在上一層的指針，直至跳表的最低層。
3. 刪除指定的節(jié)點。
跳表的實現(xiàn)
以下是一個基于C語言實現(xiàn)的跳表操作的代碼：
```c
#include
#include
#include
// 跳表結(jié)構(gòu)體
typedef struct skipListNode {
int score;
struct skipListNode *forward[1];
}skipListNode;
// 跳表結(jié)構(gòu)體
typedef struct skipList {
struct skipListNode *head;
struct skipListNode *tl;
int level; // 當(dāng)前跳表最高級別
}skipList;
// 創(chuàng)建新的節(jié)點
skipListNode* newNode(int level, int score) {
skipListNode *node = (skipListNode*) malloc(sizeof(skipListNode) + level*sizeof(skipListNode*));
node->score = score;
return node;
}
// 創(chuàng)建新的跳表
skipList* createSkipList() {
int i;
skipList *list = (skipList*) malloc(sizeof(skipList));
skipListNode *head = newNode(32, 0);
list->head = head;
for(i = 0; i
head->forward[i] = NULL;
}
list->tl = NULL;
list->level = 1;
srand(time(0));
return list;
}
// 插入節(jié)點
void insert(skipList *list, int score) {
skipListNode *update[32];
skipListNode *CURRENT;
int i, level;
current = list->head;
for(i = list->level-1; i >= 0; i--) {
while(current->forward[i] && current->forward[i]->score
current = current->forward[i];
}
update[i] = current;
}
if(current->forward[0] && current->forward[0]->score == score) {
return;
}
level = rand()%32 + 1;
if(level > list->level ) {
for(i=list->level; i
update[i] = list->head;
}
list->level = level;
}
current = newNode(level, score);
for(i = 0; i
current->forward[i] = update[i]->forward[i];
update[i]->forward[i] = current;
}
}
// 刪除節(jié)點
void delete(skipList *list, int score) {
skipListNode *update[32];
skipListNode *current;
int i;
current = list->head;
for(i = list->level-1; i >= 0; i--) {
while(current->forward[i] && current->forward[i]->score
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0];
if(current && current->score == score) {
for(i = 0; i level; i++) {
if(update[i]->forward[i] == current) {
update[i]->forward[i] = current->forward[i];
}
}
free(current);
while(list->level > 1 && list->head->forward[list->level-1] == NULL) {
list->level--;
}
}
}
// 查找節(jié)點
skipListNode* find(skipList *list, int score) {
skipListNode *current;
int i;
current = list->head;
for(i = list->level-1; i >= 0; i--) {
while(current->forward[i] && current->forward[i]->score
current = current->forward[i];
}
}
if(current->forward[0] && current->forward[0]->score == score) {
return current->forward[0];
} else {
return NULL;
}
}
在以上代碼中，我們使用鏈表實現(xiàn)了跳表的添加節(jié)點、刪除節(jié)點和查詢節(jié)點的功能。
結(jié)語
跳表是一種高效的數(shù)據(jù)結(jié)構(gòu)，其底層實現(xiàn)被廣泛應(yīng)用于 Redis 內(nèi)部有序集合的實現(xiàn)中。跳表通過增加多個等級來實現(xiàn)高效的查找、插入和刪除。希望今天的文章能夠讓你更好地理解 Redis 跳表的實現(xiàn)原理。
成都網(wǎng)站營銷推廣找創(chuàng)新互聯(lián)，全國分站站群網(wǎng)站搭建更好做SEO營銷。
創(chuàng)新互聯(lián)（www.cdcxhl.com）四川成都IDC基礎(chǔ)服務(wù)商，價格厚道。提供成都服務(wù)器托管租用、綿陽服務(wù)器租用托管、重慶服務(wù)器托管租用、貴陽服務(wù)器機房服務(wù)器托管租用。
本文名稱：深入淺出Redis 跳表的實現(xiàn)原理（redis的跳表實現(xiàn)原理）
鏈接分享：http://fisionsoft.com.cn/article/djjjhed.html
