如何设计一个搜索引擎

1、什么是检索？

指从用户特定的信息需求出发，对特定的信息集合采用一定的方法、技术手段，根据一定的线索与规则从中找出相关信息。

对应到我们实际工作中，检索其实就是：

如何用最小的内存(物理成本)，最快（时间成本）的取出我们需要的数据。

2、检索体系架构

3、存储介质层

3.1 磁盘为什么能存储数据

机械硬盘的磁盘主体是一块金属薄片（也有用其他材料的），上面涂覆一层磁性材料，可以理解为一层小磁针。

硬盘工作时，磁盘在马达的驱动下高速旋转，转速高达数千转每分钟，磁头则在磁头驱动系统的的控制下，在高速旋转的磁盘表面飞行。

①、写数据

磁头线圈上通电，在其周围产生磁场，磁化磁盘表面的磁性材料，不同方向的电流产生的磁场方向不同，磁盘表面的磁性材料被磁化的极性也不同，不同极性便代表0与1；

②、读数据

磁头线圈切割磁盘表面的磁性材料的磁场，产生电信号，不同极性的磁性材料产生的感应电流方向不同，因此可以读出0与1。

注意：断电并不会影响磁盘表面的磁性材料的极性，因此断电后数据仍然不会消失，但剧烈的碰撞或加热则有可能导致数据丢失。

3.2 磁盘和内存的区别

①、持久性

磁盘能永久存储（HDD10年，SDD5年），断电不丢失数据；

内存断电即丢失数据。

②、容量

磁盘通常是几百G到几个T；

内存通常是几个G到几十个G。

③、价格

内存 > 磁盘

④、读写速度

内存 > SDD > HDD

4、数据结构层

4.1 数组

1.数组是相同数据类型的元素的集合。 2.数组各元素是按照先后顺序连续存储的。 3.插入慢：无序数组末尾插入快，其余情况需要维护数组地址连续效率都是比较差。 4.查找：支持下标随机查找快，有序数组也可以用诸如二分法加快查找速度。 5.删除慢：和插入类似，除了末尾插入快。其余情况需要维护数组地址连续都比较慢。

4.2 链表

1.链表物理存储单元上非连续（可以充分利用计算机内存）、非顺序的存储结构。 2.不支持随机读取。 3.存储空间会增大，比如单向链表每个节点都会存储下一个节点的引用。 4.插入快。 5.删除快。 6.查找慢。

其余比如栈、队列、二叉树，红黑树，B+树等等都是这两种数据结构的单独变化或组合变化。

4.3 栈

栈只支持两个基本操作：入栈 push()和出栈 pop()。

典型应用：

①、实现字符串逆序；

②、判断标签是否匹配；

③、计算机中的函数调用；

4.4 队列

和栈类似，也只支持两个操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。

②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

③、优先级队列（Priority Queue）：数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

④、阻塞队列（Block Queue）：在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

典型的生产者-消费者模型。

⑤、并发队列

典型应用：

①、线程池

②、数据库连接池

对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

4.5 树

链表的插入和删除比较快，但是查找却比较慢，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均需要比较N/2次。

那么有没有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是 树 诞生了。

①、二叉树

二叉树的相关介绍：https://cloud.tencent.com/developer/article/1013261

二叉树的每个节点最多只能有两个子节点，如下图：

如果左节点比根节点小，右节点比根节点大，那就是平衡二叉树。二叉搜索树的效率在O(N)和O(logN)之间，取决于树的不平衡程度。最差也会退化成一个链表。

②、红黑树

为了避免二叉树退化成链表，需要尽量保证树的平衡，于是有了 红黑树。

红黑树的相关介绍：https://cloud.tencent.com/developer/article/1079403

③、B+树

上面说的树每个节点都最多只能有两个子节点，有些情况下，数据量特别大，会导致树的高度很大，这会导致我们查找某个数据需要多次IO，要知道 IO 相对而言是很慢的，有没有可能每个节点能有很多字节点呢？

类似 B+ 树，2-3-4 树诞生了。

典型应用：关系型数据库存储数据结构。

1.数据很大，不可能全部存储在内存中，还要持久化，故要存储到磁盘上。

2.减少查找过程中磁盘I/O的存取次数。

局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

与磁盘预读，预读的长度一般为页（page）的整倍数，（在许多操作系统中，页得大小通常为4k）

叶子节点数据多。

3.支持范围查找

④、LSM 树

Log Structured Merge Trees

一个日志系统有如下特征：

一、数据量大且持续生成

二、写入操作会特别频繁

三、查询快，且查询一般不是全范围的随机搜索，而是近期检索。

B+ 树为什么不行？（叶子节点存储在磁盘中，需要随机写磁盘，数据量大会导致性能急剧下降）

LSM 树：

内存树存放近期写入的数据，有序且支持更新，支持随时查询。磁盘树则通常有多个，顺序写入。

⑤、Trie 树

字典树、前缀树、单词查找树。

典型应用：

字符串检索

百度谷歌搜索框

拼写检查

4.6 跳表

链表的基础上增加了多级索引。

Redis 中的有序集合（Sorted Set）就是用跳表来实现的。

4.7 散列表

散列表相关介绍：https://cloud.tencent.com/developer/article/1079392

通过把关键值映射到表中一个位置来访问记录，这个映射函数叫做散列函数，存放记录的数组叫做散列表。

解决哈希冲突：

①、开放寻址法：线性探测、双重散列

②、链表法

散列表设计原则：

①、散列函数

②、初始容量；

③、装载因子；

④、散列冲突解决办法；

典型应用：

①、有限的数据集合中快速查询数据

比如：Word 文档中单词拼写检查功能是如何实现的？

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。

所以可以将全部英文单词放到散列表，用户输入单词直接去散列表里面查，没有就报错。

②、词频统计、访问统计等等。

4.8 布隆过滤器

布隆过滤器相关介绍：https://cloud.tencent.com/developer/article/1638225

简单来说就是一个二进制数组。

典型应用：数据海量，不要求一定准确的场景。

①、判断ID是否已经注册，即使误判也能容忍。

②、爬虫判断网页是否已经爬过。

4.9 图

存储：

①、邻接矩阵

②、邻接表

DFS（Deep First Search）深度优先搜索算法

BFS（Breath First Search）广度优先搜索算法

飞机航线

电子线路

城市地图

好友关系

5、算法层

比较好用的查找算法是二分法O(logn)，在有序的数据结构中是特别bug的，但是如何进行快速的排序，有如下常用的排序算法：

实际应用：

①、如何根据年龄给100W用户排序？

利用桶排序，从1岁到150岁（有人会说超过150岁，这里超过三界之外的人不算），建立150个桶，然后遍历这100W个用户，依次放入150个桶中，遍历完，边排好序了。

②、如何快速查询每个考生的高考排名？

同样也是桶排序，高考分数0-750，也就是顶多 750 个桶。

6、业务设计层

6.1 爬虫系统

通过高性能的爬虫系统来完成网页的持续抓取，然后将抓取到的网页存入存储平台中。

一般来说是是将抓取到的网页存放在基于 LSM 的 HBase 中，以便支持数据的高效读写。

①、爬取网页

首先找到权重较高的网页，比如新浪、腾讯，通过广度优先搜索算法放入爬取队列中；

计算网页权重算法：PageRank

网页太多，持久化队列，便于断点爬取。

如何爬取网页链接：可以获取到网页的 HTML 文件，看成一个大的字符串，然后利用字符串匹配算法，获取 或者 这样的标签内容。

②、网页去重

利用布隆过滤器。

需要注意的是：布隆过滤器是在内存中的，如果机器重启，布隆过滤器就会被清空，防止网页重复爬取，需要持久化布隆过滤器，比如定时每半小时持久化一次。

③、原始网页存储

便于后面的离线分析，索引构建，需要将海量的原始网页存储。

网页很多，通常的文件系统不适合存储这么多的文件，而是将多个网页存储在一个文件中。

④、网页编号和链接存储

上一步给每个网页分配了一个id，在存储网页的同时，也将网页编号和网页链接存储在一个文件中。

6.2 分析索引系统

①、抽取网页文本信息

网页都是遵循 HTML 规范的，只需要去掉JavaScript代码、CSS代码，还有比如下拉框的代码。

在网页这个大字符串中，一次性查找 , , </option）为止。而这期间遍历到的字符串连带着标签就应该从网页中删除。

②、网页质量分析

去掉低质量的垃圾网页

③、反作弊

避免一些作弊网页来干扰搜索结果

④、分词创建临时索引

抽取到网页文本信息之后，对文本信息进行分词，并创建临时索引文件。

英文网页：只需要通过空格、标点符号等分隔符，将每个单词分割开来就可以了。

中文网页：借助词库并采用最长匹配规则，来对文本进行分词。

临时索引文件如下：

注意这里存的是单词编号，因为单词很多，为了节省内存，用一个散列表存储：单词编号-单词。

⑤、通过临时索引创建倒排索引

⑥、记录单词编号在倒排索引文件的偏移位置

帮助我们快速地查找某个单词编号在倒排索引中存储的位置，进而快速地从倒排索引中读取单词编号对应的网页编号列表。

6.3 查询

doc_id.bin：记录网页链接和编号之间的对应关系。

term_id.bin：记录单词和编号之间的对应关系。

index.bin：倒排索引文件，记录每个单词编号以及对应包含它的网页编号列表。

term_offsert.bin：记录每个单词编号在倒排索引文件中的偏移位置。

①、当用户在搜索框中，输入某个查询文本的时候，我们先对用户输入的文本进行分词处理。假设分词之后，我们得到 k 个单词。

然后对这 k 个单词进行纠错模型判断：

②、纠错完成之后，我们拿这 k 个单词，去 term_id.bin 对应的散列表中，查找对应的单词编号。经过这个查询之后，我们得到了这 k 个单词对应的单词编号。

③、我们拿这 k 个单词编号，去 term_offset.bin 对应的散列表中，查找每个单词编号在倒排索引文件中的偏移位置。经过这个查询之后，我们得到了 k 个偏移位置。

④、我们拿这 k 个偏移位置，去倒排索引（index.bin）中，查找 k 个单词对应的包含它的网页编号列表。经过这一步查询之后，我们得到了 k 个网页编号列表。

⑤、我们针对这 k 个网页编号列表，统计每个网页编号出现的次数。具体到实现层面，我们可以借助散列表来进行统计。统计得到的结果，我们按照出现次数的多少，从小到大排序。出现次数越多，说明包含越多的用户查询单词（用户输入的搜索文本，经过分词之后的单词）。

经过这一系列查询，我们就得到了一组排好序的网页编号。我们拿着网页编号，去 doc_id.bin 文件中查找对应的网页链接，分页显示给用户就可以了。

10、总结

检索核心思路：通过合理的组织数据，尽可能的快速减少查询范围。

①、合理选择存储介质、存储数据结构；

②、合理创建索引，使得索引和数据分离；

③、减少磁盘IO，将频繁读取的数据加载到内存中；

④、读写分离；

⑤、分层处理；

参考文档：极客时间《数据结构与算法之美》

数组：https://cloud.tencent.com/developer/article/1013247

链表：https://cloud.tencent.com/developer/article/1013272

栈：https://cloud.tencent.com/developer/article/1013249

队列：https://cloud.tencent.com/developer/article/1013262

二叉树：https://cloud.tencent.com/developer/article/1013261

红黑树：https://cloud.tencent.com/developer/article/1079403

2-3-4树：https://cloud.tencent.com/developer/article/1079396

哈希表：https://cloud.tencent.com/developer/article/1079392

图：https://cloud.tencent.com/developer/article/1079391

布隆过滤器：https://cloud.tencent.com/developer/article/1638225