论文部分内容阅读
海量URL的高效存储和快速访问是高性能Web爬虫的关键技术。现有的海量URL数据管理技术大部分是基于B树或B+树索引结构的。B+树索引的特点是支持动态操作,其更新速度很快但是空间利用率很低。这种现象导致了B+树索引树高的增加,检索速度的下降。B*树结构可以大幅度的提高B+树节点的空间利用率,这种结构通过延缓分裂操作来达到提高空间利用率,但是B*树索引的更新速度远远不能满足我们高性能WEB爬虫的需要。本文通过对聚焦爬虫在网络上爬行过程的深入分析,明晰了爬虫运行时对URL数据管理的主要技术需求,针对B*树更新效率低下的问题,提出了一种新的索引结构——B+树和B*树融合的索引结构,并基于该索引结构设计出海量URL的存储、快速更新和访问方法。本文的主要贡献体现在以下几个方面:(1)本文结合B+树和B*树的优点,设计了NP_B+Tree索引和NP_B+Tree节点结构。这种索引在高速插入时只对叶子节点进行B*树的维护操作,而对B+的内节点的操作采取B+树的更新操作。在叶子节点上,NP_B+Tree索引通过采用延缓分裂的操作提高了索引的叶子节点的空间利用率,间接减少了内节点数目,降低了树高。同时NP_B+Tree在所有节点上继续使用B+树的分裂操作,维持了高速更新。这种索引更新和随机查询速度极其稳定,能够满足WEB爬虫对URL数据管理的速度需求。(2)文中的NP_B+Tree节点的新结构通过增加指针来获取更好的时间效率,它不仅在能加速NP_B+Tree的维护操作,而且对缓存的管理也有很大帮助。(3)此外,本文通过分析爬虫下载得到的URL数据的分布模式,获得了URL数据预取算法。接着设计了高速数据缓存系统。然后使用任务流水线技术和写入缓存排序等优化方案进一步加速了爬虫URL管理系统的运行速度,使得更新速度比无缓存时增加了4倍。最后通过实验讨论证明了我们的结论。基于以上研究成果,本文设计了由URL任务流水线调度模块、URL数据哈希模块、URL索引管理模块、URL缓存管理模块和URL记录管理模块等5个部分组成的URL管理系统的体系结构,并且编程实现了这个原型系统。为高性能WEB爬虫的设计打下了坚实基础。