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

Question

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