后端面试38讲_29_26_搜索引擎架构如何瞬间完成海量数据检索
你好，我是李智慧。
我们在使用搜索引擎的时候呢，搜索结果页面会展示搜索到的结果数目以及花费时间。
比如用google搜索中文后端技术这个词，主要示要通一六点七一条记录，结果这时零点四五秒。
我们知道google收录了全世界几乎所有的公开网页，这是一个非常庞大的数目。
那么google是如何在如此短的时件来完成了如此庞大的数据搜索呢？数据的搜索与查找技术是计算机软件的核心算法之一，这方面已经有非常多的技术和实践。
而对于搜索引擎来说，那么海量文档进行快速内容解锁，主要用到的就是倒排索引技术。
像google这样一个互联网搜索引擎，首先需要通过网络爬虫获取全球的公开网页。
那么，搜索引擎如何知导全世界的网页都在哪里呢？事实上，互联网一方面将全世界的人和网络应用联系起来，另一方方面也将全世界的网页通过超链接联系起来。
几乎每个网页都包含了一些其他网页的超链接。
这些超链接互相连接，就让全世界的互联网构成了一个大的网络。
所以搜索引擎只要解析这些网页得到里面的超链接，然后继索下载这些超链接的网页继续解析，这样就可以得到全世界的网页了。
这个过程具体是这样的，首先选择一些种子UIL,然后通过爬虫把这些UL对应的页面爬下来。
其实所谓的爬虫就是发送URL请求下载相对应的HTML页面，然后将这些HTML页面存储到自己的服务器上，并解析这些页面的HTML内容。
当解析到网页里超链接URL的时候，再检查这个超链接是否已经在前面爬取过了。
如果没有，就把这个超链接放到一个队列中，后面会请求这个UL得到对应的HTML页面，并解析其中包括的超链接。
如此不断重复，就可以将全世界的HTML页面存储到自己的服务器中。
你在文稿中可以看到，爬虫系统的架构图得到了全部网页以后，需要对每个网页进行编号，得到全部网页的文档集合，然后再解析每个页面提取文档里的每个单词。
如果是英文，那么每个单词就用空格来分割，比较容易。
如果是中文，需要用中文分词器才能够提取每个单词。
比如后端技术使用中文分词器，得到的就是后端和技术两个词，然后考察每个词在哪些文档中出现。
比如后端在文档二四五七中出现，技术在文档一二四中出现，这样我们就可以得到一个单词文档矩阵。
你在文章中可以看到，把这个单词文档矩阵，按照单词文档列表的方式组织起来，就得到倒排索引了。
我们这个例子中只有两个单词七个文档。
事实上，google数一万亿计的网页就是通过这样倒排索引的方式组织起来的。
网页的数量虽然不可思议的庞大，但是单词数却是比较有限的，所以整个倒排索引的大小，比起网页的数量要小得多。
Google将每个单词的文档列表存储在硬盘中。
而对于文档数量没那么大的应用而言，文档列表也可以存储在内存中。
每个单词记录一下硬盘或者内存中的文档地址列表，搜索的时候只要搜索到单词，就可以快速得到文档地址。
列表根据列表中的文档编号展示对应的文档信息，就完成了海量数据的快速检索。
而搜索单词的时候呢，我们可以将搜索单词构成一个哈希表，根据搜索词直接查找哈希表就可以得到单词了。
如果搜索词是后端，那么快速得到文档列表有四个。
如果搜索词是后端技术，那么首先需要对搜索词进行分词，得到后端和技术两个搜索单词分别得到这两个单词的文档列表，然后将这两个文档列表去交集，也很快可以得到搜索结果。
有两个，虽然搜索引擎利用倒拍索引可以很快就得到搜索结果了。
但是在实践中，搜索引擎还是会应用缓存，对搜索进行加速，将整个搜索词对应的搜索结果直接放入缓存，以减少倒回索页的访问压力以及不必要的结合计算。
有了倒排索引，虽然可以快速得到搜索结果了，但是如果搜索结果比较多，哪些文档应该优先展现给用户呢？我们使用google搜索后端技术的时候，虽然google告诉我们搜索结果有六点七亿个，但是我们通常在搜索结果列表的头几个就能够找到想要的结果，而列表越往后结果越越不是我们想要的。
Google是如何知道我们想要的结果是哪些呢？这样的搜索结果展示显然是排过序的那搜索引擎的结果是如何排序的呢？事实上，google使用了一种叫做配ge rank的算法计算，每个网页的权重搜索结果就按照权重排序，权重高的网页最终展现结果的时候排在前面。
那么为什么权重高的网页正好就是用户想要看到的呢？我们先看一下这个网页权重排序算法及配ge rank算法配置rank算法认为，如果一个网页里包含了某个网页的超链接，那么就表示该网页认可某个网页，或者说该网页给某个网页投了一票，如下ABCD四个网页。
如果网页的方向就是表示a链接的方向，b的箭头指向a表示b网页包含a网页的超链接，也就是该网页给a网页投了一票。
开始的时候，所有的网页都初始化权重为一。
然后根据超链接关系计算新的权重，比如b页面包含a和d两个页面的超链接，那么自己的权重一就被分成两个二分之一，分别投给a和d而a页面的超链接包含在BCD三个页面中，那么a页面新的权重就是这三个页面透给他的权重值之和二分之一加三分之一加一等于，六分之十一。
经过一轮配置，rank计算之后，每个页面都有了新的权重，然后基于这个新的权重再计算一轮，直到所有的网页权重都稳定下来，就得到最终所有网页的权重，即最终的配置rank值。
通常这一个网页包含了另一个网页，是对另一个网页的认可，认为这个网页质量高，值得推荐。
而被重要网页推荐的网页也应该是重要的配置。
Rank算法就是对这一设想的实现配置。
Rank值代表了一个网页，受到的推荐程度越受推荐越重要。
就越是用户想要看到的基于每个网页的配置rak值对豆瓣索页中的文档列表进行排序。
排在前面的文档，通常也是用户想要看到的文档配ge rak算法。
对于互联网网页培序效果很序比是。
对于那些用户生成内容的网站而言，比如豆瓣、知乎，或者我们的info code比果。
我们想要在这些网站内部进行搜索，配ge rap算法就没有什么效果了。
因为豆瓣的影评，知乎的回答，info code的技术文章之间很少通过超链接进行排序。
那么想要对这些站内搜索引擎的结果进行排序，就需要利用其他的一些信息和算法。
比如，可以利用文章获得的点赞数进行排序，点赞越多表示越获得其他用户的认可，越应该在搜索结果中排在前面，利用点赞数、排序或者page rank值排序，都是利用内容中存在的推荐信息排序，而这些推荐信息来自于广大参与其中的人。
因此，这些算法实现也被使为集体智慧编程，除了利用点赞数进行排序。
有时候我们更期望搜索结果，按照内容和搜索词的相关性进行排序。
比如我在info co点CN搜索page rank,实际上并不想看到那些点赞很多，但是只提到了一点page rank的文章，而是想看到主要讲page rank算法的文章。
这种情况可以使用词频TF进行排序。
词频表示，某个词在该文档中出现的频繁程度，也代表了该词和该文档的相关程度。
你在文章中可以看到词频程度使用豆瓣电影进行搜索的时候，豆瓣的搜索结果主要是电影名中包含了搜索词的电影。
比如我们搜索黑客这个词，豆瓣的搜索结果列表就是以黑客为电影名的电影。
但是如果我想搜索电影内容中关于黑客的，但是标题中可能没有黑客两个字的电影。
豆瓣的搜索就无能为力了。
几年前，我自己专门写了一个电影搜索引擎，利用豆瓣的影评内容建立倒拍索引，利用磁频算法进行排序。
你在文中可以看到搜索的结果，这个结果更符合我对电影搜索引擎的期待。
如果你对这个搜索引擎有兴趣，源代码的地址，我已经放到文章里了。
事实上，搜索引擎技术不只是用在google这样的搜索引擎互联网应用中。
对于大多数应用而言，如果想要对搜集规模的数据进行快速检索，都需要使用搜索引擎技术。
而对于淘宝这样的平台性应用，搜索引擎技术，甚至驱动其核心商业模式。
一方面，淘宝海量的商品需要通过搜索引擎完成查找。
另一方面，淘宝的主要盈利也是来自于搜索引擎排名。
所以本质上淘宝的核心技术和盈利模式跟百度、google其实是一样的。
文中我们讨论了配ge rank算法。
如果只有几百个网页，那么写一个程序计算，每个网页的配置rank值就可以了。
但是如果google这样万亿级的网页，网页之间的超链接关系数量更加庞大，而配置rank算法又需要多轮计算，如何才能较快的计算出所有网页的置parank值呢？欢迎你在评论区写下你的思考，也欢迎把这篇文章分享给你的朋友，或者同事一起交流一下。