深圳SEO公司
欢迎您光临浏览!

涉及存储规模的正排表与倒排表的合并

前面提到对于索引目前100亿中文网页进行倒排索引需要TB级的存储空间,这么大规模的数据如何生成?在生成后如何存储?存储后如何支持高效的检索?这一连串的问题将在本节解答。
正排表与倒排表的合并
下载系统将抓取网页存放在网页库中,分析系统在分析后得到网页对象发送给索引系统,因此索引不停地得到这样的网页对像。由于网页对象在分析系统中进行了分词计臬,最终分析的结果发往索引系统。
在索引系统中,通过计算不难得到如图5-10所示的正排表。
倒排表
如图5-12所示, TI是文档Docx的一个词汇,在左边的词典中找到T1的位置,然后通过其Doclit位置域存放的DocList位置信息找到记级表。并将文档编号(Docld)、在文档命中的次数( NHits ),以及命中的位置列表( HitLiat)作为倒排表中的记录表中的一个记录。可以认为正排表和倒排表合并的过程,就是正排表中的救据追加倒排表的数据过程。追加后,正排表并不保留。而倒排表在内存中存储一定的记录后,成批顺序地写入磁盘,成为临时倒排文件(本章约定,在提到正排表时,表示其存放在内存中;而特指倒排文件时,表示其存放在磁盘中),如图5-13所示。众所周知,由于磁盘的存储特性,所以很难在较大文件的中间追加数据。迫加数据就不得不进行大量的数据移动.这种开销是极大的。回到这个例子中来,如图5一13所示的临时倒排文件中无法再追加有关T1的记录。
临时倒排表
综上所述。生成倒排文件之前,倒排表(图5-12)由于存放在内存中,因此可以任意追加数据。在顺序写入磁盘成为倒排文件后,倒排文件不再变化。但由于不断有新的数据需要进行索引,所以这样的临时倒排文件数量不可避免地还会不断增加。在导入全部需要作索引的数据后,索引系统会有多个这样的临时倒排文件,不妨假设共有64个这样的临时倒排文件。
出于性能上的考虑,在一次检索时只需要谈取一个倒排文件即可得到全部与检索词相关的索引信息。而不是依次读取全部64个临时倒排文件,然后进行结果组合。因此必须将这64个临时倒排文件归并成一个更大的倒排文件。称为“最终倒排文件”,其大小略小于64个临时倒排文件之和。因为在这64个临时倒排文件中分别保留了词典信息,所以这部分冗余的数据在归并成最终倒排文件后只需要保留一份词典即可。
在且体实现上,还有一种合并方法,简单说来将是将一个正排表(包含多个Docld的记录)通过对索引词排序的方法,然后一次性或者分批次地写入倒排表中。在第七节中会提到这个方法我们这里先通过一个例子理解这个方法.首先正排表的结构需要进行调整,如图5-14所示。
正排表
这里的正排表和前面介绍的稍有不同,可以看到Lid被冗余地存放。
 在内存中保留一块这样的区城存放正排表。每增加一个需要索引的文档,就在正排表中追加一条记录。当追加足够多的记录后,正排表足够大,并符合批量做倒排表的条件后,按照关健词编号(Wordld)进行一次稳定排序(稳定排序可以参考有关数据结构的书籍,例如归并排序就是一种稳定排序),得到如图5-15所示的排序后的正排表。这里认为Tl<T2<T3。
排序后的正排表
通过估计,每个临时倒排文件的大小大约为100mb,因此甚至可以不需要写入倒排表,而直接顺序写入磁盘中的临时倒排文件。这样就形成了内存中存放正排表,磁盘中放临时倒排文件的结果。
本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 涉及存储规模的正排表与倒排表的合并
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址