我们先来回顾一下，对于能够在内存中处理的小规模的文档集合，我们是如何生成基于哈希表的倒排索引的。步骤如下：
- 给每个文档编号，作为它们的唯一标识，并且排好序；
- 顺序扫描每一个文档，将当前扫描的文档中的所有内容生成 < 关键字，文档 ID，关键字位置 > 数据对，并将所有的 < 关键字，文档 ID，关键字位置 > 这样的数据对，都以关键字为 key 存入倒排表（位置信息如果不需要可以省略）；
- 重复第 2 步，直到处理完所有文档。这样就生成一个基于内存的倒排索引。
对于大规模的文档集合，如果我们能将它分割成多个小规模文档集合，是不是就可以在内存中建立倒排索引了呢？这些存储在内存中的小规模文档的倒排索引，最终又是怎样变成一个完整的大规模的倒排索引存储在磁盘中的呢？这两个问题，你可以先思考一下，然后我们一起来看工业界是怎么做的。
首先，搜索引擎这种工业级的倒排索引表的实现，会比我们之前学习过的更复杂一些。比如说，如果文档中出现了「极客时间」四个字，那除了这四个字本身可能被作为关键词加入词典以外，「极客」和「时间」还有「极客时间」这三个词也可能会被加入词典。因此，完整的词典中词的数量会非常大，可能会达到几百万甚至是几千万的级别。并且，每个词因为长度不一样，所占据的存储空间也会不同。
所以，为了方便后续的处理，我们不仅会为词典中的每个词编号，还会把每个词对应的字符串存储在词典中。此外，在 posting list 中，除了记录文档 ID，我们还会记录该词在该文档中出现的每个位置、出现次数等信息。因此，posting list 中的每一个节点都是一个复杂的结构体，每个结构体以文档 ID 为唯一标识。完整的倒排索引表结构如下图所示：
那么，我们怎样才能生成这样一个工业级的倒排索引呢？
首先，我们可以将大规模文档均匀划分为多个小的文档集合，并按照之前的方法，为每个小的文档集合在内存中生成倒排索引。
接下来，我们需要将内存中的倒排索引存入磁盘，生成一个临时倒排文件。我们先将内存中的文档列表按照关键词的字符串大小进行排序，然后从小到大，将关键词以及对应的文档列表作为一条记录写入临时倒排文件。这样一来，临时文件中的每条记录就都是有序的了。
而且，在临时文件中，我们并不需要存储关键词的编号。原因在于每个临时文件的编号都是局部的，并不是全局唯一的，不能作为最终的唯一编号，所以无需保存。
我们依次处理每一批小规模的文档集合，为每一批小规模文档集合生成一份对应的临时文件。等文档全部处理完以后，我们就得到了磁盘上的多个临时文件。
那磁盘上的多个临时文件该如何合并呢？这又要用到我们熟悉的 多路归并技术 了。每个临时文件里的每一条记录都是根据关键词有序排列的，因此我们在做多路归并的时候，需要先将所有临时文件当前记录的关键词取出。如果关键词相同的，我们就可以将对应的 posting list 读出，并且合并了。
如果 posting list 可以完全读入内存，那我们就可以直接在内存中完成合并，然后把合并结果作为一条完整的记录写入最终的倒排文件中；如果 posting list 过大无法装入内存，但 posting list 里面的元素本身又是有序的，我们也可以将 posting list 从前往后分段读入内存进行处理，直到处理完所有分段。这样我们就完成了一条完整记录的归并。
每完成一条完整记录的归并，我们就可以为这一条记录的关键词赋上一个编号，这样每个关键词就有了全局唯一的编号。重复这个过程，直到多个临时文件归并结束，这样我们就可以得到最终完整的倒排文件。
这种 将大任务分解为多个小任务，最终根据 key 来归并 的思路，其实和分布式计算 Map Reduce 的思路是十分相似的。因此，这种将大规模文档拆分成多个小规模文档集合，再生成倒排文件的方案，可以非常方便地迁移到 Map Reduce 的框架上，在多台机器上同时运行，大幅度提升倒排文件的生成效率。那如果你想了解更多的内容，你可以看看 Google 在 2004 年发表的经典的 map reduce 论文，论文里面就说了使用 map reduce 来构建倒排索引是当时最成功的一个应用。
