【数据结构应用】搜索引擎中的数据结构和算法

一个完整的搜索引擎主要包含以下四部分核心工作：

1. 搜集

• 搜取网页链接：图、广度优先算法
• 网页去重：布隆过滤器

2. 分析
   TODO
3. 索引
   TODO
4. 查询
   TODO

搜集阶段用到的文件：

1. links.bin: 用来存储爬取到的网页链接。因为内存是有限的，需要磁盘来存储不断爬取的网页链接；另外持久化网页链接，还可以支持断点续爬。
2. bloom_filter.bin: 布隆过滤器文件。用来对爬取到的链接进行判重。这个文件跟上面的文件一样，在宕机重启或者正常重启后，为了布隆过滤器内的内容不销毁，可以定时将内存中布隆过滤器的内容持久化到磁盘中。
3. doc_row.bin：网页原始文件。后面会用它们来进行离线分析和索引。一个网页假设64kb，可以在一个文件中存储多个网页原始内容。可以采用 doc_id+分隔符1+doc_size+分隔符1+doc_content+行分隔符这样的格式存储。设置单个文件的大小上限，比如说1G。
4. doc_id.bin: 网页链接-doc_id映射文件。用来建立链接到doc_id的对应关系的文件。

分析阶段生成的文件：
1.tmp_index.bin：临时索引文件。页面的有效内容经过分词后形成的临时倒排索引文件，格式为term_id+分隔符1+doc_id+行分隔符。这里采取term_id的方式是为了节省存储空间。
2.term_id.bin: 词库映射文件。词语id-词语内容的映射文件，为了节省存储空间。

索引阶段：
1.index.bin: 将上一步生成tmp_index.bin文件中的term_id-doc_id的映射进行排序，合并。
2.term_offset.bin: 记录term_id在倒排索引文件中的偏移量，可以快速获取term的索引信息。

查询阶段：
1.term_id.bin: 收到请求后，查询这个文件，查出词语对应的term_id；
2.term_offset.bin: 在这个文件中查term在倒排索引文件中的偏移位置；
3.index.bin:根据上一步的查询结果，读取term对应的索引值；
4.doc_id.bin:根据文章id，找到链接值。