那对于这样一个大规模的倒排文件,我们在检索的时候是怎么使用的呢?其实,使用的时候有一条核心原则,那就是 内存的检索效率比磁盘高许多,因此,能加载到内存中的数据,我们要尽可能加载到内存中。
我们知道,一个倒排索引由两部分构成,一部分是 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,从而提升了系统的检索效率。
总之,对于大规模倒排索引文件的使用,本质上还是我们之前学过的检索技术之间的组合应用。因为倒排文件分为词典和文档列表两部分,所以,检索过程其实就是分别对词典和文档列表的访问过程。因此,只要你知道如何对磁盘上的词典和文档列表进行索引和检索,你就能很好地掌握大规模倒排文件的检索过程。