建站
咨詢
售后
建站咨詢
新聞中心
Redis是一個開源的、基于內(nèi)存的ykey-value存儲系統(tǒng)，由于它快速、高效、可擴展性高，所以被眾多開發(fā)人員普遍使用，尤其是移動和互聯(lián)網(wǎng)應(yīng)用。本文主要圍繞Redis跳表這一基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)展開，深入探討Redis跳表的源碼剖析與實現(xiàn)，幫助讀者更好的了解Redis。
Redis跳表（Skip List）是一種空間時間權(quán)衡的有序數(shù)據(jù)結(jié)構(gòu)，是以數(shù)據(jù)關(guān)鍵字的升序進行排序的，他擁有比red-black樹更好的查詢效率、擁有比hash更高的空間效率。算法插入、刪除和搜索復(fù)雜度都是O(log n)，此外，Redis跳表實現(xiàn)起來也非常簡單靈活。
Redis跳表的實現(xiàn)原理是，他建立了一個N個層級的有序鏈表，每一層的表項之間的關(guān)聯(lián)性取決于上一層的表項，同時每一層的表項也可以存儲任意的值，當(dāng)插入表項的時候，會首先在第一層生成一個新的表項，然后逐級往上提升，每一級的提升概率都是50％，當(dāng)超過指定的層級時停止提升，這樣就保證了隨機性。
此外，還有不少redis跳表源碼是值得一提的，比如在插入（insert）操作中，可以使用隨機值來實現(xiàn)一致性，不使用分布式鎖，從而提高效率。同時，還可以使用指針壓縮法來存儲每級鏈表的地址，以達到更節(jié)省內(nèi)存的效果。
// Redis跳表插入示例
int skiplistInsert(skiplist *SL, int key)
{
skiplistNode *update[maxlevel];
skiplistNode *x;
x = sl->head;
int i;
for(i = sl->level - 1; i >= 0; i--) {
while(x->forward[i] != NULL && (x->forward[i]->key
x = x->forward[i];
}
update[i] = x; //記錄搜索路徑
}
x = x->forward[0];
// 插入新節(jié)點
int level = randomLevel();
if (level > sl->level) {
for (int i = sl->level; i
update[i] = sl->head;
}
sl->level = level;
}
x = new skiplistNode(level);
x->key = key;
for (i= 0; i
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return 1;
}
從上面的源碼可以看出，插入節(jié)點時，會從頭指針（head）開始在每一級搜索出插入位置的前驅(qū)結(jié)點，再隨機生成一個插入節(jié)點的層數(shù)，最后將其插入每一級鏈表。
Redis跳表源碼剖析與實現(xiàn)就是這樣，通過不斷搜索，每一層的表項之間也可以互聯(lián)緊密關(guān)聯(lián)，同時由于隨機性原因，維護這些關(guān)系也是非常有效的。
香港服務(wù)器選創(chuàng)新互聯(lián)，2H2G首月10元開通。
創(chuàng)新互聯(lián)（www.cdcxhl.com）互聯(lián)網(wǎng)服務(wù)提供商,擁有超過10年的服務(wù)器租用、服務(wù)器托管、云服務(wù)器、虛擬主機、網(wǎng)站系統(tǒng)開發(fā)經(jīng)驗。專業(yè)提供云主機、虛擬主機、域名注冊、VPS主機、云服務(wù)器、香港云服務(wù)器、免備案服務(wù)器等。
網(wǎng)頁題目：Redis跳表的源碼剖析與實現(xiàn)（redis跳表源碼）
鏈接地址：http://www.fisionsoft.com.cn/article/cdcoshs.html
