搜索引擎五--索引的建立与更新

about云腾讯认证空间

问题导读
1.两遍文档遍历法速度快的原因是什么？
2.如何创建索引？
3.归并法和排序法的区别是什么？
4.常用的索引更新策略有哪4种？

索引的建立

前一总结里说到，如果索引结构建立好了，可以提高搜索的速度，那么给定一个文档集合，索引是如何建立起来的呢？建立索引的方式有很多种，在这里我就书中提到的三种方法简单总结一下。

两遍文档遍历法

第一次文档遍历

第一次扫描文档集合时，并没有立即开始建立索引，而是收集一些的统计信息，比如文档集合包含的文档个数N、文档集合内包含的不同单词个数M以及每个单词在哪些文档中出现过的信息DF等等。将所有单词对应的DF值全部相加，就可以知道建立最终的索引需要多少内存了，然后在内存中将连续存储区划分成不同大小的片段，词典内某个单词根据自己对应的DF信息，可以通过指针指向属于自己的内存片段的起始位置和终止位置，这样在第二遍扫描中，这个单词对应的倒排列表信息会被填充进这个片段中。

第二次文档遍历

这一次扫描的时候，就开始真正建立每个单词的倒排列表信息了，即对每个单词来说，获得包含这个单词的每个文档的文档ID，以及这个单词在文档中出现的次数，这样就可以不断填充第一次遍历扫描所分配的内存空间。当然，如果要记录单词在文档中出现的位置也是可以的，第一次扫描中分配内存时加上这个位置信息就可以了。

值得注意的是：此方法完全是在内存里完成索引的创建过程的，而后面两种方法则是通过内存和磁盘相互配合来完成索引建立任务的。而正因为创建索引是在内存中完成的，所以就要求内存一定要足够大，否则文档集合太大的话，内存不能够满足需求。而对文档集合进行两遍扫描，所以从速度上相比后面两种方法不占优势。

排序法

排序法在建立索引的过程中，始终在内存中分配固定大小的空间用来存放词典信息和索引的中间结果，当分配的空间被消耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占的空间，以用作下一轮存放索引中间结果的存储区。这种情况下，可以把内存看做驿站，它只是一个中间转折点。这种方法分为两个步骤：中间结果内存排序和合并中间结果。

为什么要进行排序呢？主要是为了方便后续的处理。因为在形成中间结果文件前，已经按照单词ID和文档ID进行了排序，所以进入内存缓冲区的数据都是已经排好序的，合并过程中，将不同缓冲区中包含同一个单词ID的信息进行合并，如果某个单词ID的所有信息全部合并完成，那么说明这个单词的倒排列表已经构建完成了，将其写入最终索引中，同时将各个缓冲区中对应这个单词ID信息清空。就这样一直往下进行，直到所有的单词ID对应的倒排列表都已经创建完成。最后的结果，就是最终的索引文件。

归并法

由于排序法有一个不足之处，那就是在将中间结果写入磁盘的时候，词典信息一直在内存中进行维护，这样也会占据一部分的内存。归并法就是对排序法做出了改进，即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空。

归并法整体流程也是分为两个大的阶段，首先在内存里维护中间结果，当内存占满时，将内存数据写入磁盘临时文件，第二阶段对临时文件进行归并形成最终索引。

归并法和排序法的区别

首先，排序法在内存中存放的是词典信息和三元组数据（单词ID，文档ID，单词频率），在建立索引的过程中，词典和三元组数据并没有直接的联系，词典只是为了将单词映射为单词ID。而归并法则是在内存中建立一个完整的内存索引结构，相当于对目前处理的文档子集建立起了一个倒排索引。

其次，在将中间结果写入磁盘临时文件时，归并法将整个内存的倒排索引写入临时文件，对于某个单词的倒排列表在写入磁盘文件时，将词典项放在列表最前端，之后跟随相应的倒排列表，这样依次将单词和对应的倒排列表写入磁盘文件，随后彻底清空所占内存。而排序法只是将三元组数据排序后写入磁盘文件，词典作为一个映射表一直存储在内存中。

在最后合并为最终索引的过程中，排序法是根据同一单词ID的这样三元组依次进行合并，归并法的临时文件则是每个单词对应的部分倒排列表，所以在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表就可以了，与此同时，最后的合并过程中也会形成最终的词典信息。如果大家对算法里的归并排序有所了解的话，就很清楚这种方法了吧。

索引更新策略

常用的索引更新策略有4种：完全重建策略、再合并策略、原地更新策略以及混合策略。

完全重建策略：很直观的方法，当新增文档达到一个数量时，将新增文档和原先的老文档进行合并，然后利用上文提到的建立索引的方式，对所有文档重新建立索引。

再合并策略：有新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录信息，当新增文档达到一定数量的时候，则把临时索引文件和老文档的倒排索引文件进行合并，以生成新的索引。

原地更新策略：在索引合并时，并不生成新的索引文件，而是直接在原先的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引对应的倒排列表项的末尾，这样的话，就只更新增量索引里出现的单词相关信息，其他单词信息不做变动。

混合策略：结合不同索引更新策略的优势，将不同的索引更新策略混合以形成更高效的方法。

混合策略一般会将单词根据其不同性质进行分类，不同类别的单词，对其索引采取不同的索引更新策略。常见的做法是：根据单词的倒排列表长度进行划分，因为有些单词经常在不同文档中出现，所以其对应的倒排列表就较长，而有些单词很少见，其倒排列表就较短。那么长倒排列表单词采取原地更新策略，因为这种策略能够节省磁盘读写次数；而短倒排列表就采取再和并策略。通过这种根据实际情况来分别采取实际策略的方法，效果体现的比较显著，磁盘的读写操作和各种策略的优势都充分体现出来了。

相关内容：

这就是搜索引擎--读书笔记七--倒排列表压缩算法