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

摘要

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

目录

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

A MANAGEMENT TECHNIQUES FOR MASS URL DATA BASED ON COMPLEX INDEX FROM B* TREE AND B+ TREE

摘 要

Abstract

目 录

第1章 绪 论

1.1 课题研究背景和意义

1.2 国内外相关研究和综述

1.3 课题研究内容

1.4 本文的结构安排

第2章 海量URL存储的关键技术分析

2.1 引言

2.2 WEB爬虫对海量URL管理的要求

2.3 海量URL管理的关键技术

2.4 本章小结

第3章 海量URL去重技术和数据存储结构研究

3.1 引言

3.2 海量URL去重技术

3.3 URL索引存储结构NP_B+Tree

3.4 NP_B+Tree存储结构的性能分析和实验

3.5 本章小结

第4章 基于缓存技术的海量URL管理方案

4.1 引言

4.2 海量URL数据的预取、缓存策略

4.3 海量URL管理系统运行优化设计

4.4 本章小结

第5章 海量URL管理系统的设计与实现

5.1 引言

5.2 URL管理系统系统的设计目标

5.3 URL管理系统的体系结构和功能模块设计

5.4 海量URL管理系统性能测试

5.5 本章小结

结 论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢