如何使用磁盘上的倒排文件进行检索?

简介: 利用倒排文件检索时,优先将词典加载至内存以提升效率。通过哈希表或B+树定位关键词,再读取对应文档列表(posting list)。若其过长,则采用分层索引(如跳表、B+树)按需加载;结合LRU缓存常用数据,减少磁盘IO,提高检索性能。

那对于这样一个大规模的倒排文件,我们在检索的时候是怎么使用的呢?其实,使用的时候有一条核心原则,那就是 内存的检索效率比磁盘高许多,因此,能加载到内存中的数据,我们要尽可能加载到内存中。

我们知道,一个倒排索引由两部分构成,一部分是 key 集合的词典,另一部分是 key 对应的文档列表。在许多应用中,词典这一部分数据量不会很大,可以在内存中加载。因此,我们完全可以将倒排文件中的所有 key 读出,在内存中使用哈希表建立词典。

那么,当有查询发生时,通过检索内存中的哈希表,我们就能找到对应的 key,然后将磁盘中 key 对应的 postling list 读到内存中进行处理了。

说到这里,你可能会有疑问,如果词典本身也很大,只能存储在磁盘,无法加载到内存中该怎么办呢?其实,你可以试着将词典看作一个有序的 key 的序列,那这个场景是不是就变得很熟悉了?是的,我们完全可以用 B+ 树来完成词典的检索。

这样一来,我们就可以把检索过程总结成两个步骤。
● 第一步,我们使用 B+ 树或类似的技术,查询到对应的词典中的关键字。
● 第二步,我们将这个关键字对应的 posting list 读出,在内存中进行处理。

到这里,检索过程我们就说完了。不过,还有一种情况你需要考虑,那就是 如果 posting list 非常长,它是很有可能无法加载到内存中进行处理的。比如说,在搜索引擎中,一些热门的关键词可能会出现在上亿个页面中,这些热门关键词对应的 posting list 就会非常大。那这样的情况下,我们该怎么办呢?

其实,这个问题在本质上和词典无法加载到内存中是一样的。而且,posting list 中的数据也是有序的。因此,我们完全可以对长度过大的 posting list 也进行类似 B+ 树的索引,只读取有用的数据块到内存中,从而降低磁盘访问次数。包括在 Lucene 中,也是使用类似的思想,用分层跳表来实现 posting list,从而能将 posting list 分层加载到内存中。而对于长度不大的 posting list,我们仍然可以直接加载到内存中。

此外,如果内存空间足够大,我们还能使用缓存技术,比如 LRU 缓存,它会将频繁使用的 posting list 长期保存在内存中。这样一来,当需要频繁使用该 posting list 的时候,我们可以直接从内存中获取,而不需要重复读取磁盘,也就减少了磁盘 IO,从而提升了系统的检索效率。

总之,对于大规模倒排索引文件的使用,本质上还是我们之前学过的检索技术之间的组合应用。因为倒排文件分为词典和文档列表两部分,所以,检索过程其实就是分别对词典和文档列表的访问过程。因此,只要你知道如何对磁盘上的词典和文档列表进行索引和检索,你就能很好地掌握大规模倒排文件的检索过程。

相关文章
|
11月前
|
编解码 算法 前端开发
java后端开发学习路线+避坑指南
java后端开发学习路线+避坑指南
|
11月前
|
存储 索引
如何使用「全量索引结合增量索引」方案?
采用“全量索引+增量索引”方案可高效处理大规模数据更新。系统周期生成不可变的全量索引,提升检索性能;实时新增数据则构建内存中的增量索引,支持快速写入。查询时合并两者结果,并通过删除列表标记已删数据,避免脏数据返回。结合Double Buffer机制,还可实现无锁访问,显著提升系统并发能力与检索效率。(238字)
|
11月前
什么是局部敏感哈希?
局部敏感哈希(LSH)是一种将高维数据映射为低维编码的技术,使相似数据更可能生成相近或相同的哈希值。不同于传统哈希对微小变化敏感,LSH通过随机超平面划分空间,使邻近点在多个划分中大概率落入同侧,从而获得相似哈希码。常用海明距离衡量哈希值相似性,适用于近似最近邻搜索与大规模文本去重等场景。
|
11月前
|
机器学习/深度学习 搜索推荐 算法
推荐引擎:没有搜索词,「头条」怎么找到你感兴趣的文章?
资讯类App通过“下拉刷新”精准推荐内容,背后依赖推荐引擎的检索技术。它基于用户行为数据构建用户画像与文章画像,结合协同过滤、内容召回等算法,实现个性化推荐,并通过多路召回与分层排序提升效率与准确性。
|
11月前
|
负载均衡 算法 网络协议
负载均衡:节点负载差距这么大,为什么收到的流量还一样?
本文讲解RPC框架中的负载均衡机制,对比传统Web负载均衡,阐述其由调用端自主选择节点的优势。针对业务提出“智能调控流量”需求,提出自适应负载均衡方案:通过收集服务节点的CPU、内存、响应耗时等指标进行打分,动态调整节点权重,结合随机权重算法实现流量合理分配,提升系统稳定性和可用性。
|
11月前
|
存储
LSM 树是如何检索的?
LSM树检索先查内存中的C0树,命中则直接返回;未命中再查磁盘C1树。为避免返回过期数据,删除操作会在C0树中标记key为“已删除”,查询时遇此标记即返回失败,并在滚动归并时批量清理C1树中对应数据,实现高效、延迟删除。
|
11月前
|
Docker 容器
Dockerfile
Dockerfile是构建Docker镜像的脚本文件,包含一系列指令,每条指令创建一个镜像层。编写时需用大写指令、按序执行,#为注释。通过docker build构建镜像,再用docker run运行容器。构建时,Docker引擎逐条执行指令,提交每一层变更,最终生成新镜像。
|
11月前
|
存储 索引
直接进行多次查询会有什么问题?
直接多次查询会增加次数与开销。以GeoHash查找最近加油站为例,逐步扩大范围虽可行,但“逐圈扩展”效率低,查询次数多;“缩短编码”虽快,却需重复二分查找,浪费资源。优化需平衡查询次数与存储成本。
|
11月前
|
存储 负载均衡 索引
简单的分布式结构是什么样的?
简单分布式结构通过分发服务器将请求分配给多台具备完整索引的索引服务器,实现负载均衡与高吞吐。虽不减少单次查询时间,但可通过拆分索引、分散内存加载来降低检索规模,提升单次效率,是分布式检索优化的关键思路。(238字)
|
11月前
|
存储
如何利用批量写入代替多次随机写入?
LSM树通过延迟写入优化磁盘I/O:数据先写入内存中的C0树,达到阈值后批量以块为单位写入磁盘的C1树。C1树采用B+树结构且叶子节点全满,无需预留空间,提升写入效率,适用于高并发写场景。(239字符)