56,681
社区成员
发帖
与我相关
我的任务
分享请教关于搜索引擎在蜘蛛抓取时如何防止访问重复URL的问题
在搜索引擎中，通常已访问过的URL库都是亿级别的，如何在蜘蛛访问前知道某一个URL以前是否有访问过呢。
我以前的做法是使用数据库，建立一个表，然后为URL字段设置一个唯一索引，这样插入失败就说明这个网址已经访问过了，但是随着网址数量越来越多，就出问题了，数据库太大了。而且也没办法判断一个网址是否已经更新了是否需要再次去访问一次，比如没办法判断 网页的最后更新时间，网页的长度比对等等。
我查看了一些资料也问了一些朋友，大家都说需要使用MD5进行哈希处理，但是我始终没有想明白如何才能达到O(1)的时间复杂度，希望一些有经验的朋友能指导一下，最好有完整的思路，也可以推荐我一些详细描写这方面知识的书或是网页。
最近为这个问题实在是郁闷极了。
我以前的做法是使用数据库，建立一个表，然后为URL字段设置一个唯一索引，这样插入失败就说明这个网址已经访问过了，但是随着网址数量越来越多，就出问题了，数据库太大了。而且也没办法判断一个网址是否已经更新了是否需要再次去访问一次，比如没办法判断 网页的最后更新时间，网页的长度比对等等。
我查看了一些资料也问了一些朋友，大家都说需要使用MD5进行哈希处理，但是我始终没有想明白如何才能达到O(1)的时间复杂度，希望一些有经验的朋友能指导一下，最好有完整的思路，也可以推荐我一些详细描写这方面知识的书或是网页。
最近为这个问题实在是郁闷极了。
...全文
请发表友善的回复…
发表回复
Delta 2009-11-16
- 打赏
- 举报
来看看。呵呵
bananabbs 2009-11-16
- 打赏
- 举报
递归的性能消耗也会比较大
Xiao_Qiang_ 2009-11-16
- 打赏
- 举报
是这个
http://blog.csdn.net/Xiao_Qiang_/archive/2008/10/03/3013448.aspx
http://blog.csdn.net/Xiao_Qiang_/archive/2008/10/03/3013448.aspx
Xiao_Qiang_ 2009-11-16
- 打赏
- 举报
使用bitmap,梁斌的<<走进搜索引擎>>说到过,
下面是我python的实现,还有java的;
http://hi.csdn.net/link.php?url=http://blog.csdn.net%2FXiao_Qiang_
http://hi.csdn.net/link.php?url=http://blog.csdn.net%2FXiao_Qiang_
下面是我python的实现,还有java的;
http://hi.csdn.net/link.php?url=http://blog.csdn.net%2FXiao_Qiang_
http://hi.csdn.net/link.php?url=http://blog.csdn.net%2FXiao_Qiang_
gonxi 2009-11-16
- 打赏
- 举报
对于百万级以下的url地址列表,可以使用数据库,或者写到索引文件中处理.
对于海量数据来说,我现在想到的办法是根据url中的hostname来分区,每个爬虫处理一个区的url,如果发现不是本区的url,就发到分发服务器,分发服务器再根据hostname发到对应分区的爬虫处理.
不过这样处理也遇到一个问题,hostname与ip之间的多对多关系,这个还没解决
对于海量数据来说,我现在想到的办法是根据url中的hostname来分区,每个爬虫处理一个区的url,如果发现不是本区的url,就发到分发服务器,分发服务器再根据hostname发到对应分区的爬虫处理.
不过这样处理也遇到一个问题,hostname与ip之间的多对多关系,这个还没解决
cfhamlet 2009-11-15
- 打赏
- 举报
楼上有些网友果然是大牛，膜拜之，如果简单问题，可以试试bloomfilter
lover4ever 2009-11-15
- 打赏
- 举报
采用URL转MD5再存储到数据库我认为还是太慢，虽然原理简单
本人前段时间专门去学习数据结构，在此发表一点自己的想法，高手勿笑
我的思路主要是利用树这种数据结构
1.对每个网站的域名或者IP使用一个树结点
2.把对应网站的每一个目录添加为对应域名或者IP的子节点，当然目录可能还会包含子目录，递归即可
3.把每一个URL添加为所属目录的子节点，
要查找目标URL是否已访问，只需先判定网站URL节点是否已存在，然后找到目录的子节点，最后找到URL，层层递归，
这种方法比用数据库那鸟方法好多了，楼主不妨试一试，欢迎发邮件到lover4ever@126.com
本人前段时间专门去学习数据结构，在此发表一点自己的想法，高手勿笑
我的思路主要是利用树这种数据结构
1.对每个网站的域名或者IP使用一个树结点
2.把对应网站的每一个目录添加为对应域名或者IP的子节点，当然目录可能还会包含子目录，递归即可
3.把每一个URL添加为所属目录的子节点，
要查找目标URL是否已访问，只需先判定网站URL节点是否已存在，然后找到目录的子节点，最后找到URL，层层递归，
这种方法比用数据库那鸟方法好多了，楼主不妨试一试，欢迎发邮件到lover4ever@126.com
missbeast 2009-11-15
- 打赏
- 举报
有点复杂
ls逍遥 2009-11-15
- 打赏
- 举报
mark!
iisbsd 2009-11-14
- 打赏
- 举报
[Quote=引用 21 楼 huzhibin2000 的回复:]
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了
[/Quote]
决定用数据库之前，三思，三思。
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了
[/Quote]
决定用数据库之前，三思，三思。
shetianlang 2009-11-14
- 打赏
- 举报
膜拜！
huzhibin2000 2009-11-14
- 打赏
- 举报
可以采用hash算法对数据库进行分表分库. 比方说根据url中的hostname进行分表分库,再加上楼上的对URL计算md5存储,就算你有10亿条记录,分100库*100表(共1万个表),这样每个表才10万条记录,查询起来不会慢.
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了.希望对楼主有帮助.
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了.希望对楼主有帮助.
平凡的思想者 2009-11-13
- 打赏
- 举报
我觉得楼主的问题还是采用memory表比较好些，毕竟这是一个成熟的做法，自己写代码还有调试，效率未必比数据库的hash算法高。
如果要保存的话，可以定时把memory表的数据导入到另外一张表。
或者每次更新memory表时更新另外一张表，这样数据就完全同步。
系统重启后，从另外一张表的数据来重新构造一个memory表。
另外，mmap不受物理内存限制，只要你物理内存加虚拟内存够用就可以了。
如果要保存的话，可以定时把memory表的数据导入到另外一张表。
或者每次更新memory表时更新另外一张表，这样数据就完全同步。
系统重启后，从另外一张表的数据来重新构造一个memory表。
另外，mmap不受物理内存限制，只要你物理内存加虚拟内存够用就可以了。
netxuning 2009-11-13
- 打赏
- 举报
to iisbsd:
我现在总要隔一段时间将哈希表的内容回写到一个文件上，以便宕机后有所保留！
还有一个问题，mmap会不会受内存大小的限制？比如我的内存大小128M, 要映射256M的文件，会出现什么问题呢？
我现在总要隔一段时间将哈希表的内容回写到一个文件上，以便宕机后有所保留！
还有一个问题，mmap会不会受内存大小的限制？比如我的内存大小128M, 要映射256M的文件，会出现什么问题呢？
netxuning 2009-11-13
- 打赏
- 举报
楼上说的用mmap能够永久存储，是什么思路？
我最近也在考虑mmap， 缘于苦于我的哈希表无法永久存储！
但不知道具体如何解决！
[Quote=引用 8 楼 iisbsd 的回复:]
如果是这种结构，还不如用STL里面的set一类的东西，可能会更快一些（至少节省了SQL语句的分析时间）
[/Quote]
这个确实，楼主以后应该改成这样，但鉴于楼主已经用数据库实现，建议先按我的思路改改试试，看看能不能满足需求，毕竟这样的实现成本要低很多！
我最近也在考虑mmap， 缘于苦于我的哈希表无法永久存储！
但不知道具体如何解决！
[Quote=引用 8 楼 iisbsd 的回复:]
如果是这种结构，还不如用STL里面的set一类的东西，可能会更快一些（至少节省了SQL语句的分析时间）
[/Quote]
这个确实，楼主以后应该改成这样，但鉴于楼主已经用数据库实现，建议先按我的思路改改试试，看看能不能满足需求，毕竟这样的实现成本要低很多！
iisbsd 2009-11-13
- 打赏
- 举报
[Quote=引用 7 楼 netxuning 的回复:]
memory引擎默认的索引方法就是hash.所以，楼主按上边方法建表即可！先试试排重的速度有没有提升！
[/Quote]
如果是这种结构，还不如用STL里面的set一类的东西，可能会更快一些（至少节省了SQL语句的分析时间），如果需要永久存储的话，用mmap就好。
通用的技术永远没有专用的技术快。
memory引擎默认的索引方法就是hash.所以，楼主按上边方法建表即可！先试试排重的速度有没有提升！
[/Quote]
如果是这种结构，还不如用STL里面的set一类的东西，可能会更快一些（至少节省了SQL语句的分析时间），如果需要永久存储的话，用mmap就好。
通用的技术永远没有专用的技术快。
guoyunsky 2009-11-13
- 打赏
- 举报
1.URL换为MD5，减少存储和计算空间，楼上有
2.由于URL是一直增加的，如果放在内存里肯定不可取。建议使用嵌入式数据库储存，如JAVA的BDB。采用通用型数据局储存太耗时间和效率(因为程序和数据库需要通信等)
2.由于URL是一直增加的，如果放在内存里肯定不可取。建议使用嵌入式数据库储存，如JAVA的BDB。采用通用型数据局储存太耗时间和效率(因为程序和数据库需要通信等)
xzjxylophone 2009-11-13
- 打赏
- 举报
太牛 X了 我无与伦比了。
felix3118 2009-11-13
- 打赏
- 举报
用树保存。能快速定位。
iisbsd 2009-11-13
- 打赏
- 举报
这个……感谢大家的鼓励，真的动手写了，才发现不知道说什么：
http://blog.csdn.net/iisbsd/archive/2009/11/13/4807534.aspx
我更喜欢问答的。
有谁想写的，我提供观点、素材，甚至内幕。^_^
http://blog.csdn.net/iisbsd/archive/2009/11/13/4807534.aspx
我更喜欢问答的。
有谁想写的，我提供观点、素材，甚至内幕。^_^
加载更多回复（12）
