腾讯面试题： 百度搜索为什么那么快？数据结构与算法小松与蘑菇-

我还记得去年面腾讯时，面试官最后一个问题是：百度/google的搜索为什么那么快？

这个问题我懵了，我从来没想过，搜素引擎的原理是什么

然后我回答：百度爬取了各个网站的信息，然后进行排序，当输入关键词的时候进行文档比对……巴拉巴拉

面试官：这不是我想要的答案

我内心

这个问题我一直耿耿于怀，终于今天，我把他写出来，以后再问，我直接把这篇文章甩给他！！！

两个字：倒排，将贯穿整篇文章，也是面试官想要的答案

首先我们知道，百度肯定是有爬虫，到处爬取网页，进行某种处理。然后通过你输入的关键词进行某种计算再返回给你的

我们先来看看什么是某种处理

某种处理

当百度爬取了海量网页后，每一个网页我们称为”文档“，不可能就杂乱无章的放着，它使用了文档集合，就是类似的文档放在一个集合中

那什么样的文档算类似呢？相信你猜到了，文档中有相同关键字的就可以放在一个集合中

来举例说明

假设全世界只有下面5个文档（网页），文档内容也很简单，就一句话（注意是内容，不是标题）

百度爬取后，将他们进行编号，然后对文档进行扫描分词，因为百度内部有词库，匹配上的词将被切分，所以文档1号将被切分为【谷歌，地图，之父，跳槽，FaceBook】，后面的文档也一样，然后对切分出来的单词进行倒排处理，形成倒排列表

啥是倒排处理？右边这堆杂乱无章的数字咋来的？别急，仔细看，1号单词“谷歌”是不是在1,2,3,4,5号文档都出现过？9号单词“离开”是不是只在3号文档出现过？

是的，倒排列表所做的，就是保存对应单词所出现过的文档编号

我想你开始明白他的目的了，当我们搜索“谷歌”的时候，他就会获得“谷歌”这一单词对应的倒排列表，知道哪些文档包含他，然后将这些文档提取出来返回给你，这就是一种单词映射文档的方法

但是，没那么简单，因为只有这样的话，我在一篇博客上把所有的单词都写上，这样杂乱无章的文章岂不是要被推荐给全体中国人？？？

所以倒排列表还要保存下列信息

保留的信息变成了二元组，比如16号单词“网站”的(5:1)，5表示出现的文档编号，1表示出现的次数，也就是说，有了这个信息，如果一个单词在文档中频率越高(英文缩写TF)，搜素引擎就可以把他排在前面推给你

除了频率，还有位置，比如”谷歌“就是在1号文档中出现了一次的单词，位置在第一个，用<1>表示

可能到这你有点记不住有哪些网页了，再看一遍比对下

这样子，搜素引擎就可以根据你的关键词在倒排列表中找到含有这个关键词的文档集合，然后根据关键词在文档集合中各个文档出现的频率和位置综合判断返回给你排序后的文档

上句话比较长，加粗部分连在一起读意思不变

实际上很多搜索引擎基本就是这样做的，只不过各家还有别的参考标准，比如百度还会参考热度，你的搜索记录，还有网站给的钱（你懂的）等等综合打分，按评分高低返回搜索结果的排序

上面的所以记录处理好后都会存放在磁盘中，然后等你关键词来后再调入内存

假设世界上只有5个文档，那么上面的东西完全够了，但实际上，世界上有亿万个文档，此时，问题的性质已经变了，不是找不找得到的问题，而是怎么找更快，更准的问题，这需要算法，也就是我们上面提到的某种计算

某种计算

第一个问题就是，词库那么多，当你输入“苹果”的时候，百度如何将你的关键词和他内部倒排列表的“苹果”一词联系起来？

计算机是不认识“苹果”的，这里，可以通过哈希的方法将“苹果”转换为一个编号

所谓哈希，即使将一个词通过某种算法映射为一个符号，比如“将单词转换为其长度”就是一种算法，虽然很low，这样“苹果”就是2，“梨”就是1，不同的哈希算法有不同的转换结果，但是必然会有一个东西——哈希冲突，比如“桃子”也是2，此时，需要使用链表，也称冲突表，将编号相同的单词链在一起

当我们搜索“苹果”的时候，经过哈希计算，得知其编号为2，然后发现2中有一个链表，里面可能保存着“苹果”，”桃子”，“蘑菇”等，然后再遍历链表找到苹果即可

这里和java8中的hashmap思想一致，不过链表也会过长，所以可以使用别的数据结构代替，比如红黑树，b树等

解决了第一个问题，我们就可以通过关键词获得他的Id,然后得到所建立的倒排列表了，比如“谷歌”

第二个问题，由于文档的数量庞大，我们获取的文档往往编号位数都很多，而不像上图那样1,2,3,4,5,导致倒排列表无谓的扩大，所以我们这里进行作差

就是后面的文档编号减去前面的，在取文档（从磁盘中读取）的时候加回来即可

第三个问题，如何从磁盘中读取文档

现在我们已经有了倒排列表

可以有两种方法从磁盘中读取文档

两次遍历法

第一遍，扫描文档集合，找到文档数量N, 文档集合内所包含的不同单词数M,和每个单词出现的频率DF（如下图），以及一些别的必要信息，这些东西所占内存加起来，得到需要开辟的内存空间，

同时这个空间是以单词为单位划分，比如“谷歌”一词有5篇文档，

1. 第一遍主要就是确定要开辟多大的内存空间来显示文档

2. 第二遍扫描，就是边扫描，匹配对应的文档编号（三元组中的第一个数），载入内存

但是这个方法有一个问题，那就是文档集合有多大，内存就有多大，所以，很可能内存会溢出，不过都放在内存中速度也很快，这是一种空间换时间的方法

相信你发现了，但凡设计到读取，一定有两种以上的方法，空间优先或是时间优先，第二种就是时间换空间——排序法

排序法

现在我们只用固定大小的内存，如何从上图中的倒排列表得知每个单词对应的文章集合所需要的内存空间有多少呢？

我们需要解析文档，构造（单词ID,文档ID，单词频率）三元组，然后进行排序，按单词ID,文档ID,单词频率先后排，最后如果规定的内存满了，就将这些三元组通通写入一个临时文件A中

为什么要这样呢？想想看，如果我们最后拿到了一个（单词A,文档A，单词频率），我们就可以很轻松的知道一个单词对应哪个文档，和对应的频率，

也就是一个三元组告诉我们单词A对应的文档A，另一个三元组告诉我们单词A对应文档B……，这些三元组加起来我们就知道了单词A对应的文档集合，就可以知道他需要多少内存空间来填补这些文档了

可能解析50个文档后规定的内存就满了，然后把这些三元组们写入磁盘临时文件A，就可以再读下一篇50个文档了，注意，词典是不断增加的，比如前50个文档只有上面7个单词，后50个文档可能出现了别的单词，此时要插入词典中，词典一直在内存

这样，只用固定大小的内存就可以50一批的解析完所有文档，写入了一个个的临时文件A,B,C,D，再将这些临时文件合并，就是把他们分别读入内存中的缓冲区，合成最终索引后再写入磁盘，这样通过最终索引就知道有哪些单词对应多少文档，还有频率，然后根据这些开辟内存空间读取进入内存返回给你即可

排序法叙述起来比较复杂，但是其实理解起来很简单，耐心读一定能懂哦

限于篇幅，这里只讲了你输入关键词到他返回给你大致的网页的过程，其实，百度如何爬取网页？如何保证网页的时效性？如何筛选垃圾网站？如何分布式存储海量网页？如何应对超长关键字查询？如何根据用户历史记录精准分析用户意图？
等等都需要大量的篇幅详解，一篇文章不可能讲完，下次有机会再分析吧

作者简介 ：【小松与蘑菇】，微信公众号同名，喜欢读书和收集书，文章参考自《这就是搜索引擎核心技术详解》，关注公众号回复【搜索引擎】，即可获取资源，一起交流学习吧