倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号（DocID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项（Posting），包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。右图是倒排列表的示意图，在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。
在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap）。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。如图2所示的例子中，原始的 3个文档编号分别是187、196和199，通过编号差值计算，在实际存储的时候就转化成了：187、9、3。
之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。 索引的构建 相当于从正排表到倒排表的建立过程。当我们分析完网页时 ,得到的是以网页为主码的索引表。当索引建立完成后 ,应得到倒排表 ,具体流程如图所示：
流程描述如下：
1）将文档分析称单词term标记，
2）使用hash去重单词term 3）对单词生成倒排列表 倒排列表就是文档编号DocID，没有包含其他的信息（如词频，单词位置等），这就是简单的索引。 这个简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制： 1）需要有足够的内存来存储倒排表，对于搜索引擎来说， 都是G级别数据，特别是当规模不断扩大时 ,我们根本不可能提供这么多的内存。 2）算法是顺序执行，不便于并行处理。 归并法 ,即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。
如图 归并示意图：
合并流程：
1）页面分析，生成临时倒排数据索引A，B，当临时倒排数据索引A，B占满内存后，将内存索引A，B写入临时文件生成临时倒排文件， 2) 对生成的多个临时倒排文件 ,执行多路归并 ,输出得到最终的倒排文件 ( inverted file)。
索引创建过程中的页面分析 ,特别是中文分词为主要时间开销。算法的第二步相对很快。这样创建算法的优化集中在中文分词效率上。
