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

搜索引擎的倒排索引文件的创建过程

倒排索引文件的创建过程更像是一个工程建设,其中大量应用了批量计算及流水计算的技巧,完成如此大规模的倒排索引文件的创建一直是搜索引擎的核心难点。
创建倒排表
首先深圳SEO先通过一个例子完整地体会单个索引结点倒排文件的创建过程,如图5-22所示。这里的网岩浆库支持顺序访问模式(参见第三章第五节),能够顺序读取存放其中的文档,为了简化,我们假定读取的文档按照顺序分别为文档1,文档2和文档3,其正文内容分别为“ratdog”,“dog cat”和“rat dog”。通过在内存中完成正排得到词出现的文档和位置信息,例如,rat(1,1)表示在文档1的第1个位置出现“rat”这个索引词。接下来通过对字母排序(汉字可以按照汉字汇编号排序),得到一个临时的按照索引词有序的结构,这有助于顺序写入各个索引词对应的记录表。在图5-22所示的倒排表达到一定大小(例如100MB)时,将倒排表顺序写入到临时倒排文件中。完成全部网页库索引工作后,将产生的多个临时倒排文件归并为一个最终倒排文件(图5-22中忽略临时倒排文件归并的过程)。
临时倒排文件归并的过程
从计算的角度上讲,临时倒排文件创建的全过程包含了磁盘读取(loading),计算(peocessing)写入磁盘(flushing)这3个过程,磁盘读取从网页库中读取一个个的文档;计算过程包括了正排计算,排充及归并等;写入磁盘主要是写入临时倒排文件。如果采用多道并行处理,则可大大提高索引 创建的效率。
如果将整个临时倒排文件创建过程抽象为L(loading),P(PROCESSING)和F(flushing)3个顺序的操作,即到写入临时倒排文件为止,则L操作和F操作是磁盘密集型操作;而P操作是CPU密集型操作。为简化,采用两个线程并发操作的处理方法,如图5-23所示。
线程并发操作的处理方法
这里线程1首先开始执行L操作,在执行P操作时磁盘空闲,这时线程2使用磁盘执行L操作。理论上最佳的效果是无论在什么时间点,总是一个线程占用CPU;另一个线程占用磁盘,这样相互配合可以高效地完成索引创建过程。这里还有一个问题就是一次L操作读取多少文档才是最佳的,可以使得这种合作能够最少出现互相等待的情况。对于两道线程并发,一个L操作的时间相当,即线程1的P操作能够和线程2的L操作重叠。当然实际处理中还有很多技巧,读者可以参阅文献(Arvind Arasu etal.2001)获取更加详细的技术细节。
本文出自深圳SEO公司,未经允许不得转载:深圳SEO公司-深圳SEO服务公司 » 搜索引擎的倒排索引文件的创建过程
分享到: 更多 (0)

评论 抢沙发

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