搜索引擎对网页索引更新策略
动态索引通过在内存中维护临时索引，可以实现对动态文档和实时搜索的支持。但是服务器内存总是有限的，随着新加入系统的文档越来越多，临时索引消耗的内存也会随之增加。当最初分配的内存将被使用完时，要考虑将临时索引的内容更新到磁盘索引中，以释放内存空间来容纳后续的新进文档，此时要考虑合理有效的索引更新策略。
常用的索引更新策略有4种：完全重建策略、再合并策略、原地更新策略及混合策略。
1、完全重建策略（Complete Re-Build）
完全重建策略是一个相当直观的方法，当新增文档达到一定数量，将新增文档和原先的老文档进行合并，然后利用前述章节提到的建立索引的方式，对所有文档重新建立索引。新索引建立完成后，老的索引被遗弃释放，之后对用户查询的响应完全由新的索引负责。
因为重建索引需要较长时间，在进行索引重建的过程中，内存中仍然需要维护老的索引，来对用户的查询做出响应。只有当新索引完全建立完成后，才能释放旧的索引，将用户查询响应切换到新索引上。
这种重建策略比较适合小文档集合，因为完全重建索引的代价较高，但是目前主流商业搜索引擎一般是采用此方式来维护索引的更新的，这与互联网本身的特性有关。
2、再合并策略（Re-Merge）
有新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录其信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。
在实际的搜索系统中，再合并策略按照以下步骤进行索引内容的更新。
· 当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引。
· 一旦增量索引将指定的内存消耗光，此时需要进行一次索引合并，即将增量索引和老的倒排索引内容进行合并，图3-18是合并过程示意图。这里需要注意的是：倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高进行了排序，增量索引在遍历词典的时候也按照字典序由低到高排列，这样对老的倒排文件只需进行一遍扫描，并可顺序读取，减少了文件操作中比较耗时的磁盘寻道时间，可以有效地提高合并效率。
在合并过程中，需要依次遍历增量索引和老索引单词词典中包含的单词及其对应的倒排列表，可以用两个指针分别指向两套索引中目前需要合并的单词 ，按照如下方式进行倒排列表的合并。
考虑增量索引的单词指针指向的单词，如果这个单词在词典序中小于老索引的单词指针指向的单词，说明这个单词在老索引中未出现过，则直接将这个单词对应的倒排列表写入新索引的倒排文件中，同时增量索引单词指针后移指向下一个单词。
如果两个单词指针指向的单词相同，说明这个单词在增量索引和老索引中同时出现，则将老索引中这个单词对应的倒排列表写入新索引的倒排列表，然后把增量索引中这个单词对应的倒排列表追加到其后，这样就完成了这个单词所有倒排列表的合并。图3-18中箭头所指单词是搜索，说明此时合并到了该单词，因为在老的索引系统和增量索引中都包含这个单词，所以首先将老索引对应的倒排列表追加到新索引倒排文件末尾，之后将增量索引中搜索这个单词对应的倒排列表追加在其后，这样就完成了这个单词索引项的合并。两个索引的单词指针都移动到下一个单词继续进行合并。
如果某个单词只在老索引中出现过，即发现老索引的单词指针指向的单词，其词典序小于增量索引单词指针指向的单词，则直接将老索引中对应的倒排列表写入新索引倒排文件中。老索引的单词指针后移
指向下一个单词，继续进行合并。
当两个索引的所有单词都遍历完成后，新索引建成，此时可以遗弃释放老索引，使用新索引来响应用户查询请求。
同样地，在按照这个策略进行索引合并的过程中，为了能够响应用户查询，在合并索引期间，需要使用老索引响应用户查询请求。
再合并策略是效率非常高的一种索引更新策略，主要原因在于：在对老的倒排索引进行遍历时，因为已经按照索引单词的词典序由低到高排好顺序，所以可以顺序读取文件内容，减少磁盘寻道时间，这是其高效的根本原因。但是这种方法也有其缺点，因为要生成新的倒排索引文件，所以对于老索引中的很多单词来说，尽管其倒排列表并未发生任何变化，但是也需要将其从老索引中读取出来并写入新索引中，这种对磁盘输入输出的消耗是没有太大必要且非常耗时的。
3、原地更新策略（In-Place）
原地更新策略的基本出发点，可以认为是试图改进再合并策略的缺点。也就是说，在索引更新过程中，如果老索引的倒排列表没有变化，可以不需要读取这些信息，而只对那些倒排列表变化的单词进行处理。甚至希望能更进一步：即使老索引的倒排列表发生变化，是否可以只在其末尾进行追加操作，而不需要读取原先的倒排列表并重写到磁盘另一个位置？如果能够达到这个目标，明显可以大量减少磁盘读／写操作，提升系统执行效率。
为了达到上述目标，原地更新策略在索引合并时，并不生成新的索引文件，而是直接在原先老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾，这样就可达到上述目标，即只更新增量索引里出现的单词相关信息，其他单词相关信息不做变动。
但是这里存在一个问题：对于倒排文件中的两个相邻单词，为了在查询时加快读取速度，其倒排列表一般是顺序序列存储的，这导致没有空余位置用来追加新信息。为了能够支持追加操作，原地更新策略在初始建立的索引中，会在每个单词的倒排列表末尾预留出一定的磁盘空间，这样，在进行索引合并时，可以将增量索引追加到预留空间中。
这种合并策略的一个说明。在图中，老索引中每个单词的倒排列表末尾都预留出空余磁盘空间，以作为信息追加时的存储区域。在对新增索引进行合并时，按照词典序，依次遍历新增索引中包含的单词，并对新增倒排列表的大小和老索引中相应预留空间大小进行比较，如果预留空间足够大，则将新增列表追加到老索引即可，如果预留空间不足以容纳新增倒排列表，那么此时需要在磁盘中找到一块完整的连续存储区，这个存储区足以容纳这个单词的倒排列表，之后将老索引中的倒排列表读出并写入新的磁盘位置，并将增量索引对应的倒排列表追加到其后，这样就完成了一次倒排列表的“迁移”工作。
，可以看出，单词“技术”和“引擎”在老索引中的预留空间足够大，所以对增量索引只需做追加写入即可，但是对于单词“搜索”来说，其预留空间不足以容纳新增倒排列表，所以这个单词的倒排列表需要迁移到磁盘另外一个连续存储区中。
原地更新策略的出发点很好，但是实验数据证明其索引更新效率比再合并策略低，主要是出于以下两个原因。
在这种方法中，对倒排列表进行“迁移”是比较常见的操作，为了能够进行快速迁移，需要找到足够大的磁盘连续存储区，所以这个策略需要对磁盘可用空间进行维护和管理，而这种维护和查找成本非常高，这成为该方法效率的一个瓶颈。
对于倒排文件中的相邻索引单词，其倒排列表顺序一般是按照相邻单词的词典序存储的，但是由于原地更新策略对单词的倒排列表做数据迁移，某些单词及其对应倒排列表会从老索引中移出，这样就破坏了这种单词连续性，导致在进行索引合并时不能进行顺序读取，必须维护一个单词到其倒排文件相应位置的映射表，而这样做，一方面降低了磁盘读取速度，另外一方面需要大量的内存来存储这种映射信息。
4、混合策略（Hybrid）
混合策略的出发点是能够结合不同索引更新策略的长处，将不同的索引更新策略混合，以形成更高效的方法。
混合策略一般会将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。常见的做法是：根据单词的倒排列表长度进行区分，因为有些单词经常在不同文档中出现，所以其对应的倒排列表较长，而有些单词很少见，则其倒排列表就较短。根据这一性质将单词划分为长倒排列表单词和短倒排列表单词。长倒排列表单词采取原地更新策略，而短倒排列表单词则采取再合并策略。
之所以这样做，是由于原地更新策略更适合长倒排列表单词，因为这种策略能够节省磁盘读／写次数，而长倒排列表单词的读／写开销明显要比短倒排列表单词大很多，所以如果采用原地更新策略，效果体现得比较显著。而大量短倒排列表单词读／写开销相对而言不算太大，所以利用再合并策略来处理，则其顺序读／写优势也能被充分利用。