基于B-樹和B+樹融合索引的海量URL管理技術(shù).pdf

1、海量URL的高效存儲和快速訪問是高性能Web爬蟲的關(guān)鍵技術(shù)?，F(xiàn)有的海量URL數(shù)據(jù)管理技術(shù)大部分是基于B樹或B+樹索引結(jié)構(gòu)的。B+樹索引的特點(diǎn)是支持動態(tài)操作，其更新速度很快但是空間利用率很低。這種現(xiàn)象導(dǎo)致了 B+樹索引樹高的增加，檢索速度的下降。B*樹結(jié)構(gòu)可以大幅度的提高B+樹節(jié)點(diǎn)的空間利用率，這種結(jié)構(gòu)通過延緩分裂操作來達(dá)到提高空間利用率，但是B*樹索引的更新速度遠(yuǎn)遠(yuǎn)不能滿足我們高性能WEB爬蟲的需要。
　　本文通過對聚焦爬蟲在網(wǎng)絡(luò)

2、上爬行過程的深入分析，明晰了爬蟲運(yùn)行時對URL數(shù)據(jù)管理的主要技術(shù)需求，針對B*樹更新效率低下的問題，提出了一種新的索引結(jié)構(gòu)——B+樹和B*樹融合的索引結(jié)構(gòu)，并基于該索引結(jié)構(gòu)設(shè)計出海量 URL的存儲、快速更新和訪問方法。本文的主要貢獻(xiàn)體現(xiàn)在以下幾個方面：
　?。?）本文結(jié)合B+樹和B*樹的優(yōu)點(diǎn)，設(shè)計了NP_B+Tree索引和NP_B+Tree節(jié)點(diǎn)結(jié)構(gòu)。這種索引在高速插入時只對葉子節(jié)點(diǎn)進(jìn)行B*樹的維護(hù)操作，而對B+的內(nèi)節(jié)點(diǎn)的操作采取B

3、+樹的更新操作。在葉子節(jié)點(diǎn)上，NP_B+Tree索引通過采用延緩分裂的操作提高了索引的葉子節(jié)點(diǎn)的空間利用率，間接減少了內(nèi)節(jié)點(diǎn)數(shù)目，降低了樹高。同時NP_B+Tree在所有節(jié)點(diǎn)上繼續(xù)使用B+樹的分裂操作，維持了高速更新。這種索引更新和隨機(jī)查詢速度極其穩(wěn)定，能夠滿足WEB爬蟲對URL數(shù)據(jù)管理的速度需求。
　?。?）文中的NP_B+Tree節(jié)點(diǎn)的新結(jié)構(gòu)通過增加指針來獲取更好的時間效率，它不僅在能加速NP_B+Tree的維護(hù)操作，而且對緩

4、存的管理也有很大幫助。
　?。?）此外，本文通過分析爬蟲下載得到的URL數(shù)據(jù)的分布模式，獲得了 URL數(shù)據(jù)預(yù)取算法。接著設(shè)計了高速數(shù)據(jù)緩存系統(tǒng)。然后使用任務(wù)流水線技術(shù)和寫入緩存排序等優(yōu)化方案進(jìn)一步加速了爬蟲URL管理系統(tǒng)的運(yùn)行速度，使得更新速度比無緩存時增加了4倍。最后通過實(shí)驗(yàn)討論證明了我們的結(jié)論。
　　基于以上研究成果，本文設(shè)計了由URL任務(wù)流水線調(diào)度模塊、URL數(shù)據(jù)哈希模塊、URL索引管理模塊、URL緩存管理模塊和URL