学位论文 > 优秀研究生学位论文题录展示

基于B~*树和B+树融合索引的海量URL管理技术

作　者: 李春山
导　师: 徐晓飞；叶允明
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: WEB爬虫 URL管理 NP_B+Tree 节点结构缓存优化管理
分类号: TP311.12
类　型: 硕士论文
年　份: 2009年
下　载: 63次
引　用: 0次
阅　读: 论文下载

内容摘要

海量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爬虫的设计打下了坚实基础。

全文目录

摘要  4-6
Abstract  6-10
第1章绪论  10-17
  1.1 课题研究背景和意义  10-12
    1.1.1 研究背景  10
    1.1.2 研究意义  10-12
  1.2 国内外相关研究和综述  12-14
    1.2.1 WEB爬虫技术现状  12-13
    1.2.2 URL管理系统技术现状  13-14
  1.3 课题研究内容  14-15
  1.4 本文的结构安排  15-17
第2章海量URL存储的关键技术分析  17-26
  2.1 引言  17
  2.2 WEB爬虫对海量URL管理的要求  17-19
    2.2.1 Crawler的爬行  17-19
    2.2.2 Crawler对海量URL管理的基本要求  19
  2.3 海量URL管理的关键技术  19-24
    2.3.1 URL去重技术  19-21
    2.3.2 海量URL管理系统的索引技术  21-23
    2.3.3 海量数据管理的缓存技术  23-24
    2.3.4 URL数据管理系统运行优化  24
  2.4 本章小结  24-26
第3章海量URL去重技术和数据存储结构研究  26-44
  3.1 引言  26
  3.2 海量URL去重技术  26-29
    3.2.1 URL去重技术的选择  26-27
    3.2.2 URL的哈希函数选择  27-29
  3.3 URL索引存储结构NP_B+TREE  29-38
    3.3.1 适用于海量数据管理的NP_B+Tree索引  29-30
    3.3.2 NP_B+Tree的存储结构描述  30-32
    3.3.3 NP_B+Tree的基本操作  32-38
  3.4 NP_B+TREE存储结构的性能分析和实验  38-43
    3.4.1 NP_B+Tree存储空间存储占有量分析  38-40
    3.4.2 NP_B+Tree的更新效率分析  40-41
    3.4.3 NP_B+Tree的查询效率分析  41-43
  3.5 本章小结  43-44
第4章基于缓存技术的海量URL管理方案  44-54
  4.1 引言  44
  4.2 海量URL数据的预取、缓存策略  44-49
    4.2.1 预取、缓存相结合的访问策略  44-45
    4.2.2 针对URL数据访问方式的数据预取算法  45-47
    4.2.3 预取、缓存模块的性能分析与实验  47-49
  4.3 海量URL管理系统运行优化设计  49-52
    4.3.1 基于任务流水线思想的运行管理优化  49
    4.3.2 内外存替换时的缓存排序优化  49-50
    4.3.3 海量URL管理系统运行优化实验分析  50-52
  4.4 本章小结  52-54
第5章海量URL管理系统的设计与实现  54-60
  5.1 引言  54
  5.2 URL管理系统系统的设计目标  54
  5.3 URL管理系统的体系结构和功能模块设计  54-57
    5.3.1 URL管理系统的体系结构  54-55
    5.3.2 URL管理系统功能模块详细设计  55-57
  5.4 海量URL管理系统性能测试  57-59
    5.4.1 开发平台及工具  57
    5.4.2 海量URL管理系统运行性能实验  57-59
  5.5 本章小结  59-60
结论  60-62
参考文献  62-66
致谢  66

基于B~*树和B+树融合索引的海量URL管理技术

内容摘要

全文目录

相似论文