1.  涉及存储规模的一些计算

前面提到对于索引目前100亿中文网页进行倒排索引需要TB级的存储空间，这么大规模的数据如何生成？在生成后如何存储？存储后如何支持高效的检索？这一连串的问题将在本节解答。

1.1  正排表与倒排表的合并

下载系统将抓取网页存放在网页库中，分析系统在分析后得到网页对象发送给索引系统，因此索引不停地得到这样的网页对象。由于网页对象在分析系统中进行了分词计算，最终分析的结果发往索引系统。

在索引系统中，通过计算不难得到如图4-10所示的正排表。在实际操作中，正排表不写入文件，而是保存在内存中。可以理解为内存中存储的正排索引，是正排索引的一种具体表现形式，同理，倒排表也是内存中存储的倒排索引，也是倒排索引的一种具体表现形式。

众所周知，由于磁盘的存储特性，所以很难在较大文件的中间追加数据。追加数据就不得不进行大量的数据移动，这种开销是极大的。回到这个例子中来，如图4-13所示的临时倒排文件中无法再追加有关T1的记录。

综上所述，生成倒排文件之前，倒排表（图4-12）由于存放在内存中，因此可以任意追加数据。在顺序写入磁盘成为倒排文件后，倒排文件不再变化。但由于不断有新的数据需要进行索引，所以这样的临时倒排文件数量不可避免地还会不断增加。在导入全部需要作索引的数据后，索引系统会有多个这样的临时倒排文件，不妨假设共有64个这样的临时倒排文件。

出于性能上的考虑，在一次检索时只需要读取一个倒排文件即可得到全部与检索词相关的索引信息。而不是依次读取全部64个临时倒排文件，然后进行结果组合。因此必须将这64个临时倒排文件归并成一个更大的倒排文件，称为"最终倒排文件"，其大小略小于64个临时倒排文件之和。因为在这64个临时倒排文件中分别保留了词典信息，所以这部分冗余的数据在归并成最终倒排文件后只需要保留一份词典即可。

在具体实现上，还有一种合并方法，简单说来就是将一个正排表（包含多个DocId的记录）通过对索引词排序的方法，然后一次性或者分批次地写入倒排表中。在第七节中会提到这个方法，我们这里先通过一个例子理解这个方法。首先正排表的结构需要进行调整，如图4-14所示。

这里的正排表和前面介绍的稍有不同，可以看到LId被冗余地存放。

在内存中保留一块这样的区域存放正排表，每增加一个需要索引的文档，就在正排表中追加一条记录。当追加足够多的记录后，正排表足够大，并符合批量做倒排表的条件后，按照关键词编号（WordId）进行一次稳定排序（稳定排序可以参考有关数据结构的书籍，例如归并排序就是一种稳定排序），得到如图4-15所示的排序后的正排表，这里认为T1