搜索引擎背后的经典数据结构和算法 _搜索引擎

前言
我们每天都在用百度，google这些搜索引擎，那大家有没想过搜索引擎是如何实现的呢，看似简单的搜索其实技术细节非常复杂，说搜索引擎是 IT 皇冠上的明珠也不为过，今天我们来就来简单过一下搜索引擎的原理，看看它是如何工作的，当然搜索引擎博大精深，一篇文章不可能完全介绍完，我们只会介绍它最重要的几个步骤，不过万变不离其宗，搜索引擎都离不开这些重要步骤，剩下的无非是在其上添砖加瓦，所以掌握这些「关键路径」，能很好地达到观一斑而窥全貎的目的。
本文将会从以下几个部分来介绍搜索引擎，会深度剖析搜索引擎的工作原理及其中用到的一些经典数据结构和算法，相信大家看了肯定有收获。

搜索引擎系统架构图
搜索引擎工作原理详细剖析

搜索引擎系统架构图搜索引擎整体架构图如下图所示，大致可以分为搜集，预处理，索引，查询这四步，每一步的技术细节都很多，我们将在下文中详细分析每一步的工作原理。

文章插图

搜索引擎工作原理详细剖析一、搜集爬虫一开始是不知道该从哪里开始爬起的，所以我们可以给它一组优质种子网页的链接，比如新浪主页，腾讯主页等，这些主页比较知名，在 Alexa 排名上也非常靠前，拿到这些优质种子网页后，就对这些网页通过广度优先遍历不断遍历这些网页，爬取网页内容，提取出其中的链接，不断将其加入到待爬取队列，然后爬虫不断地从 url 的待爬取队列里提取出 url 进行爬取，重复以上过程...
当然了，只用一个爬虫是不够的，可以启动多个爬虫并行爬取，这样速度会快很多。
1、待爬取的 url 实现待爬取 url 我们可以把它放到 redis 里，保证了高性能，需要注意的是，Redis 要开启持久化功能，这样支持断点续爬，如果 Redis 挂掉了，重启之后由于有持久化功能，可以从上一个待爬的 url 开始重新爬。
2、如何判重如何避免网页的重复爬取呢，我们需要对 url 进行去重操作，去重怎么实现？可能有人说用散列表，将每个待抓取 url 存在散列表里，每次要加入待爬取 url 时都通过这个散列表来判断一下是否爬取过了，这样做确实没有问题，但我们需要注意到的是这样需要会出巨大的空间代价，有多大，我们简单算一下，假设有 10 亿 url （不要觉得 10 亿很大，像 Google, 百度这样的搜索引擎，它们要爬取的网页量级比 10 亿大得多），放在散列表里，需要多大存储空间呢？
我们假设每个网页 url 平均长度 64 字节，则 10 亿个 url 大约需要 60 G 内存，如果用散列表实现的话，由于散列表为了避免过多的冲突，需要较小的装载因子（假设哈希表要装载 10 个元素，实际可能要分配 20 个元素的空间，以避免哈希冲突），同时不管是用链式存储还是用红黑树来处理冲突，都要存储指针，各种这些加起来所需内存可能会超过 100 G，再加上冲突时需要在链表中比较字符串，性能上也是一个损耗，当然 100 G 对大型搜索引擎来说不是什么大问题，但其实还有一种方案可以实现远小于 100 G 的内存：布隆过滤器。

文章插图

针对 10 亿个 url，我们分配 100 亿个 bit，大约 1.2 G, 相比 100 G 内存，提升了近百倍！可见技术方案的合理选择能很好地达到降本增效的效果。
当然有人可能会提出疑问，布隆过滤器可能会存在误判的情况，即某个值经过布隆过滤器判断不存在，那这个值肯定不存在，但如果经布隆过滤器判断存在，那这个值不一定存在 ,针对这种情况我们可以通过调整布隆过滤器的哈希函数或其底层的位图大小来尽可能地降低误判的概率，但如果误判还是发生了呢，此时针对这种 url 就不爬好了，毕竟互联网上这么多网页，少爬几个也无妨。
3、网页的存储文件: doc_raw.bin爬完网页，网页该如何存储呢，有人说一个网页存一个文件不就行了，如果是这样，10 亿个网页就要存 10 亿个文件，一般的文件系统是不支持的，所以一般是把网页内容存储在一个文件（假设为 doc_raw.bin）中，如下

文章插图

当然一般的文件系统对单个文件的大小也是有限制的，比如 1 G，那在文件超过 1 G 后再新建一个好了。
图中网页 id 是怎么生成的，显然一个 url 对应一个网页 id，所以我们可以增加一个发号器，每爬取完一个网页，发号器给它分配一个 id，将网页 id 与 url 存储在一个文件里，假设命名为 doc_id.bin,如下