请教关于搜索引擎在蜘蛛抓取时如何防止访问重复URL的问题

在搜索引擎中，通常已访问过的URL库都是亿级别的，如何在蜘蛛访问前知道某一个URL以前是否有访问过呢。我以前的做法是使用数据库，建立一个表，然后为URL字段设置一个唯一索引，这样插入失败就说明这个网址已经访问过了，但是随着网址数量越来越多，就出问题了，数据库太大了。而且也没办法判断一个网址是否已经更新了是否需要再次去访问一次，比如没办法判断网页的最后更新时间，网页的长度比对等等。我查看了一些资料也问了一些朋友，大家都说需要使用MD5进行哈希处理，但是我始终没有想明白如何才能达到O(1)的时间复杂度，希望一些有经验的朋友能指导一下，最好有完整的思路，也可以推荐我一些详细描写这方面知识的书或是网页。最近为这个问题实在是郁闷极了。

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

这个思路就是先换算出url的md5码，用这个md5来近似代表这个url,也被称为url的指纹！之所以这样做的目的第一是为了减少存储空，毕竟md5才32或64个位！其次是md5的随机特性很适合哈希表的寻址！至于为什么选择哈希表，因为其思路是将查询的数据通过哈希函数直接算出存储地址，算是直接寻址，所以复杂度为O(1).楼主上边的最大困惑好像在于存储空间，没有提到查询速度！看来数据库查询的速度完全可以满足楼主的需求！如果是这样，楼主可以考虑用bloomfilter来实现，这是哈希表的一个变种！更为节约空间！
这个问题全靠在本地机器上存储的记录肯定无法解决，还是要靠判断http header的Last-Modified和Content-Length信息来判断网页是否更新！
至于书籍和资料，楼主可搜一下数学之美， mining the web 等，
建议楼主看看wget larbin的源码，里边有具体实现！
非常感谢 netxuning 的回复，我就是在乎查询速度，因为随着数据库逐渐变大，速度也越来越慢而且也没办法存储那么多数据，所以我得想办法改变这些。
如果是查询速度问题的话，先将你的数据表的存储引擎改为memory, 索引改为hash,将url换算成md5然后再存储.
这样数据表会变得小很多，能够尽量装进内存，在内存里查询！
create table url_key(md5 bigint primary key) engine=memory;mysql> show index from url_key;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| url_key |          0 | PRIMARY  |            1 | md5         | NULL      |           0 |     NULL | NULL   |      | HASH       |         |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
memory引擎默认的索引方法就是hash.所以，楼主按上边方法建表即可！先试试排重的速度有没有提升！
如果是这种结构，还不如用STL里面的set一类的东西，可能会更快一些（至少节省了SQL语句的分析时间），如果需要永久存储的话，用mmap就好。通用的技术永远没有专用的技术快。
楼上说的用mmap能够永久存储，是什么思路？
我最近也在考虑mmap，缘于苦于我的哈希表无法永久存储！
但不知道具体如何解决！
这个确实，楼主以后应该改成这样，但鉴于楼主已经用数据库实现，建议先按我的思路改改试试，看看能不能满足需求，毕竟这样的实现成本要低很多！
to iisbsd:
我现在总要隔一段时间将哈希表的内容回写到一个文件上，以便宕机后有所保留！还有一个问题，mmap会不会受内存大小的限制？比如我的内存大小128M, 要映射256M的文件，会出现什么问题呢？
我觉得楼主的问题还是采用memory表比较好些，毕竟这是一个成熟的做法，自己写代码还有调试，效率未必比数据库的hash算法高。
如果要保存的话，可以定时把memory表的数据导入到另外一张表。
或者每次更新memory表时更新另外一张表，这样数据就完全同步。
系统重启后，从另外一张表的数据来重新构造一个memory表。另外，mmap不受物理内存限制，只要你物理内存加虚拟内存够用就可以了。
mmap在物理内存不够的时候会开始使用交换区，如果你准备使用mmap的话，最好保证每台机器上的数据都能保存在物理内存中，然后多台机器可以通过哈希分片保存，当然，需要自己写服务器，但是如果你懒的话，继续往下看……我建议处理大批量简单数据的应用都看看非数据库的解决方案，还是那句话，数据库太通用，性能并不好。至于方案是否成熟，成本是否低廉，这里有个列表，我相信他们还是比较成熟的，而且鉴于他们的规模，成本也应该是低廉的。这些都是在线应用，如果是离线的，建议看看hadoop什么的：memcacheDB：新浪
cassandra：facebook
tokyo cabinet：mixi.com
MongoDB：sourceforge
Voldemort：linkedin
CouchDB：Ubuntu One如果你对上面这些公司的规模都不是很了解，那你还是用数据库吧。其实很想写点东西——大规模的web应用真的不适合用数据库，不过不知道那里写合适，再看机会吧。
这个……感谢大家的鼓励，真的动手写了，才发现不知道说什么：http://blog.csdn.net/iisbsd/archive/2009/11/13/4807534.aspx我更喜欢问答的。有谁想写的，我提供观点、素材，甚至内幕。^_^
1.URL换为MD5，减少存储和计算空间，楼上有
2.由于URL是一直增加的，如果放在内存里肯定不可取。建议使用嵌入式数据库储存，如JAVA的BDB。采用通用型数据局储存太耗时间和效率(因为程序和数据库需要通信等)
可以采用hash算法对数据库进行分表分库. 比方说根据url中的hostname进行分表分库,再加上楼上的对URL计算md5存储,就算你有10亿条记录,分100库*100表(共1万个表),这样每个表才10万条记录,查询起来不会慢.
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了.希望对楼主有帮助.
楼上有些网友果然是大牛，膜拜之，如果简单问题，可以试试bloomfilter
采用URL转MD5再存储到数据库我认为还是太慢，虽然原理简单本人前段时间专门去学习数据结构，在此发表一点自己的想法，高手勿笑我的思路主要是利用树这种数据结构1.对每个网站的域名或者IP使用一个树结点
2.把对应网站的每一个目录添加为对应域名或者IP的子节点，当然目录可能还会包含子目录，递归即可
3.把每一个URL添加为所属目录的子节点，要查找目标URL是否已访问，只需先判定网站URL节点是否已存在，然后找到目录的子节点，最后找到URL，层层递归，这种方法比用数据库那鸟方法好多了，楼主不妨试一试，欢迎发邮件到[email protected]
对于百万级以下的url地址列表,可以使用数据库,或者写到索引文件中处理.对于海量数据来说,我现在想到的办法是根据url中的hostname来分区,每个爬虫处理一个区的url,如果发现不是本区的url,就发到分发服务器,分发服务器再根据hostname发到对应分区的爬虫处理.不过这样处理也遇到一个问题,hostname与ip之间的多对多关系,这个还没解决
使用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_
是这个
http://blog.csdn.net/Xiao_Qiang_/archive/2008/10/03/3013448.aspx