在搜索引擎中,通常已访问过的URL库都是亿级别的,如何在蜘蛛访问前知道某一个URL以前是否有访问过呢。我以前的做法是使用数据库,建立一个表,然后为URL字段设置一个唯一索引,这样插入失败就说明这个网址已经访问过了,但是随着网址数量越来越多,就出问题了,数据库太大了。而且也没办法判断一个网址是否已经更新了是否需要再次去访问一次,比如没办法判断 网页的最后更新时间,网页的长度比对等等。我查看了一些资料也问了一些朋友,大家都说需要使用MD5进行哈希处理,但是我始终没有想明白如何才能达到O(1)的时间复杂度,希望一些有经验的朋友能指导一下,最好有完整的思路,也可以推荐我一些详细描写这方面知识的书或是网页。最近为这个问题实在是郁闷极了。
这个思路就是先换算出url的md5码,用这个md5来近似代表这个url,也被称为url的指纹!之所以这样做的目的第一是为了减少存储空,毕竟md5才32或64个位!其次是md5的随机特性很适合哈希表的寻址!至于为什么选择哈希表,因为其思路是将查询的数据通过哈希函数直接算出存储地址,算是直接寻址,所以复杂度为O(1).楼主上边的最大困惑好像在于存储空间,没有提到查询速度!看来数据库查询的速度完全可以满足楼主的需求!如果是这样,楼主可以考虑用bloomfilter来实现,这是哈希表的一个变种!更为节约空间!
这个问题全靠在本地机器上存储的记录肯定无法解决,还是要靠判断http header的Last-Modified和Content-Length信息来判断网页是否更新!
建议楼主看看wget larbin的源码,里边有具体实现!
如果是查询速度问题的话,先将你的数据表的存储引擎改为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会不会受内存大小的限制?比如我的内存大小128M, 要映射256M的文件,会出现什么问题呢?
如果要保存的话,可以定时把memory表的数据导入到另外一张表。
或者每次更新memory表时更新另外一张表,这样数据就完全同步。
系统重启后,从另外一张表的数据来重新构造一个memory表。另外,mmap不受物理内存限制,只要你物理内存加虚拟内存够用就可以了。
cassandra:facebook
tokyo cabinet:mixi.com
MongoDB:sourceforge
Voldemort:linkedin
CouchDB:Ubuntu One如果你对上面这些公司的规模都不是很了解,那你还是用数据库吧。其实很想写点东西——大规模的web应用真的不适合用数据库,不过不知道那里写合适,再看机会吧。
2.由于URL是一直增加的,如果放在内存里肯定不可取。建议使用嵌入式数据库储存,如JAVA的BDB。采用通用型数据局储存太耗时间和效率(因为程序和数据库需要通信等)
分表分库是腾讯,迅雷等大型互联网公司后台最常用的策略了.希望对楼主有帮助.
2.把对应网站的每一个目录添加为对应域名或者IP的子节点,当然目录可能还会包含子目录,递归即可
3.把每一个URL添加为所属目录的子节点,要查找目标URL是否已访问,只需先判定网站URL节点是否已存在,然后找到目录的子节点,最后找到URL,层层递归,这种方法比用数据库那鸟方法好多了,楼主不妨试一试,欢迎发邮件到[email protected]
下面是我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