新闻动态
搜索引擎索引的再合并策略
https://www.sytm.net 发布日期:2013/9/15 7:54:16

当有不断的新的文档进入搜索系统时,搜索系统在内存维护临时倒排索引来记录其信息,当新增文档达到一定数量的时候,或者当指定大小的内存被消耗完,则把临时索引和老文档的倒排索引进行合并,以生成新的索引。在实际的搜索系统中,再合并策略按照以下步骤进行索引内容的更新。

当新增文档进入系统,解析文档,之后更新内存中维护的临时索引,文档中出现的每个单词,在其倒排列表末尾追加倒排列表项,这分临时索引可称为增量索引。

一旦增量索引将指定的内存消耗光,此时需要进行一次索引合并,即将增量索引和老的倒排索引内容进行合并。这里需要注意的是:倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高进行了排序,增量索引在遍历词典的时候也按照字典由低到高排列,这样对老的倒排文件只需进行一遍扫描,并可顺序读取,减少了文件操作中比较耗时的磁盘寻道时间,可以有效地提高合并效率。

在合并过程中,需要依次遍历增量索引和老索引词词典中包含的单词及其对应的倒排列表,可以用两个指针分别指向两套索引中目前需要合并的单词,按照如下方式进行倒排列表的合并。

考虑增量索引的单词指向的单词,如果这个单词在词典序中小于老索引的单词指针指向的单词,说明这个单词在老索引中未出现过,则直接将这个单词对应的倒排列表写入新索引的倒排文件中,同时增量索引单词指针后移指向下一个单词。

如果两个单词指针指向的单词相同,说明这个单词在增量索引和老索引中同时出现,则将老索引中这个单词对应的到排列表写入新索引的倒排列表,然后把增量索引中这个单词对应的倒排列表追加到其后,这样就完成了这个单词所有倒排列表的合并。

如果某个单词只在老索引中出现过,即发现老索引的单词指针指向单词,其词典序小于增量索引单词指针指向单词,则直接将老索引中对应的倒排列表写入新索引倒排文件中。老索引的单词指针后移指向下一个单词,继续进行合并。

当两个索引的所有单词都遍历完成后,新索引建成后,此时可以遗弃释放老索引,使用新索引来响应用户查询请求。

同样地,在按照这个策略进行索引合并的过程中,为了能够响应用户查询,在合并索引期间,需要使用老索引响应用户查询请求。再合并策略是效率非常高的一种索引更新策略,主要原因在于:在对老的倒排索引进行遍历时,因为已经按照索引单词的词典序由低到高排好顺序,所以尅顺序读取文件内容,减少磁盘寻道时间,这是其高效的根本原因。但是这种方法也有其缺点,因为要生成新的倒排索引文件,所以对于老索引中的很多单词来说,尽管其倒排列表并未发生任何变化,但是也需要将其从老索引中读取出来写入新索引中,这种对磁盘输入输出的消耗是没有太大必要且非常耗时的。

更多阅读
返回列表
© 2010 TianMei Technology All rights reserved. ICP:辽B2-20150138辽公网安备 21010202000010号  目录概览