scrapy - 网站的url的深广优先遍历及去重

scrapy是抓取web站点，并提取结构化数据的python框架。

爬取网站的过程相当于遍历一棵树的过程，每个子节点相当于一个url

深度优先遍历（递归实现）：

对每一个分支路径深入到不能再深入位置，且每个节点只能访问一次。

• 先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
• 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
• 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

深度优先png

广度优先遍历（队列实现）：

又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可访问

广度优先.png

网站url结构是一种有层次的树结构
而url连接结构图是有回路的

要避免陷入反复爬取某些页面的循环
就需要url去重，记录已经爬取过的url

爬虫去重策略

1. 把url保存到数据库中，每次在数据库中查询
2. 访问过的url保存到set，O（1）代价可查询url，但是占用空间大
3. 把url通过md5方法压缩长度，哈希保存到set （scrapy方法）
4. bitmap，把访问过的url通过hash函数映射到某一位（bit），缺点是冲突高，但能极大减少内存。
5. bloomfilter改进，多重hash降低冲突。