动态索引通过在内存中维护临时索引，实现对动态文档的实时搜索功能。而随着新加入文档对内存渐趋待尽的消耗，就需要我们找到合适的内存释放方法，亦即将临时索引内容更新到磁盘索引中，为后续文档誊出空间。这就是下面要讲的，动态索引更新策略。
常用新策略有四种：完全重建策略，再合并策略，就地更新策略、混合策略。
1. 完全重建策略
将达到一定数量的新增文档，连带老文档一起进行合并，然后对所有文档重新建立索引。新生成索引取代原来索引响应查询操作，而老的索引则被释放。
但需要注意的是，因新索引的建立需要消耗较多时间，在新索引建立完成之前，老索引都要继续发挥作用。
考虑到重建索引的代价问题，不建议大文档采用此类操作。
2. 再合并策略
一种“当搜索系统用来维护临时倒排索引的内存被消耗殆尽，或新增文档达到一定数量时，合并临时索引和老文档的倒排索引，以生成新索引”的更新策略。
更新步骤：
A. 解析新进入系统的文档，并更新内存中的临时索引，追加“新出现单词的倒排列表项”至“倒排列表”末尾，形成“增量索引”；
B.内存被“增量索引”消耗光时，将“增量索引”和老的倒排索引进行合并。下图为合并过程示意图：倒排文件里的倒排列表，已按照索引单词字典顺序由低到高进行排序，增量索引遍历词典的时候也按照该顺序对老的倒排文件进行扫描，并顺序读取，减少了文件操作中比较耗时的磁盘寻道时间，可以有效地增加合并效率。
合并过程中，需依次遍历“增量索引”和老索引单词词典中包含的单词及其对应的倒排列表，可用两个指针分别指向两套索引中目前需要合并的单词（参考上图箭头所指），并按照如下方式进行倒排列表的合并：
如果 “增量索引”单词指针指向的单词, 其词典排序小于老索引单词指针指向的单词。说明该单词在老索引中没有出现过，将该单词对应的倒排列表写入新索引的倒排文件，同时“增量索引”单词指针后移指向下一个单词。
如果两个“单词指针”指向的单词相同。说明这个单词在“增量索引”和老索引中同时出现，则将老索引中该单词对应的倒排列表写入新索引倒排列表，并把“增量索引”中该单词对应的倒排列表追加到其后，这样就完成了这个单词所有倒排列表的合并。
如果老索引的“单词指针”指向的单词，其词典序小于“增量索引”单词指针指向的单词。说明该单词只在老索引中出现过，直接将老索引中对应的倒排列表写入新索引倒排文件，同时老索引的单词指针做后移操作，指向下一个单词进行继续合并。
两索引的所有单词都遍历完成后，新索引建成，此时释放老索引，采用新索引。同样的，为响应用户查询，合并索引期间仍需使用老索引维系工作。
优点：效率高。因为对老倒排索引进行遍历时，已按照索引单词的词典序由低到高排好顺序，所以可以顺序读取文件内容，减少了磁盘寻道时间。
缺点：磁盘输入输出耗时。生成新的倒排索引文件，需从老索引中读取单词并写入新索引。
3. 原地更新策略
索引更新过程中，只对老索引倒排列表中变化的单词进行读取处理，并在索引合并过程中采用追加操作（参考图），即将增量索引里单词的倒排列表项追加到老索引相应位置的末尾。
由于“原地更新策略”在索引创建之初，已在每个单词的倒排列表末尾预留出一定的磁盘空间，所以，索引合并时，只需将增量索引追加到预留空间中即可。
“原地更新策略”更新效率一般比“再合并策略”要低：
首先，倒排列表“迁移”操作较为常见，快速迁移对磁盘连续存储区有较高要求，导致磁盘可用空间维护和管理成本较高；
其次，倒排文件中相邻索引单词的倒排列表，一般按照词典序顺序存储，数据迁移时某些单词及其对应倒排列表从老索引中移出，破坏了单词连续性，导致索引合并时不能顺序读取。因此，必须维护一个单词到其倒排文件相应位置的映射表，不仅降低了磁盘读取速度，也占用了大量的内存空间。
4. 混合策略
一种“按性质将单词分类，并对不同类别单词采用不同策略”的更新方式。
常见做法是，根据单词倒排列表长度，划分单词为“长倒排列表单词”和“短倒排列表单词”。对“长倒排列表单词”采取“原地更新策略”，对“短倒排列表单词”采取“再合并策略”。
因为“原地更新策略”能节省磁盘读写次数，更适合“长倒排列表单词”；“短倒排列表单词”读写开销相对而言不算太大，利用“再合并策略”来处理，可发挥顺序读写优势。
（本文精简自《这就是搜索引擎：核心技术详解》，欢迎有兴趣的进一步阅读）
网友评论