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