顾名思义这章就是要谈怎样构造索引的问题，或者说在有限内存和有限时间内，怎么样高效的对大数据集构造索引文件。一旦有了这个索引文件，那么索引的压缩，基于索引的排序，前面的章节都已经讲过。
链接列表
先来看看最一般的方法，在内存中构建这样的数据结构，包含一个term字典，这个字典本身可以用数组，hash表，二分查找树来实现，字典中的每 项，都包含一个指向term的倒排列表的指针，那么对于一个term的倒排列表一般用单项链表来实现，因为这个是动态的，就是说每一项包含文档号，文档内 频率，和下一项指针。
然后遍历每一篇文档，对于文档中的每个term，在字典中如果有就直接把文档号和频率挂在这个term的倒排列表后面，如果没有，先在字典中加上这个term，然后再挂。
当所有文档都处理完了， 我们就在内存中保存了一个完整的倒排索引，最后一步就是把这个内存中的索引存储到磁盘上的一个倒排文件。
那么这个方法，容易理解，又简单看上去很好，但有个问题，就是如果对于大文档集，那内存的消耗是很大的。
那么时间换空间，你可以把链表缓存到数据库，或虚拟内存上面去，当然这个方法不可行，因为效率太低，在index文档时，需要先遍历倒排列表去找到每个term所对应的链表， 这种随机访问会有大量的磁盘读写。
基于排序的倒排
对于大文档集的索引，在有限内存情况下，不可能把索引都放在内存里，必然要放到磁盘上，那么对于磁盘的问题是，随机访问的效率很低。所以如果所有索引项都是有序的存放在文件中，那么这样顺序的访问磁盘文件还是比较高效的。
那么什么样的数据结构适合在文件中排序了，答案是三元组 <t, d, fd,t >
这样在index文档时就不用去遍历查找了， 三元组本身就记录了所有的关系，当然三元组会造成数据冗余，在每个三元组中都要保留termid
算法是这样的：
1. 创建空的字典S，和一个磁盘上的临时文件
2. 遍历每一篇文档，对文档中的term，字典中没有的话，加到字典中，有的话，读出termid，组成三元组<t, d, fd,t >并存到临时文件中。
3. 开始排序，因为内存有限不可能把所有三元组都读进来排序，所以要分段排序
就是每次读入内存能够容纳的k条三元组，按termid升序排序，termid相同的，就按docid升序排序
那么这排序后的k条三元组就是一个有序段(sorted run)
然后将有序段写回临时文件
这样不断的读入直到全部处理完
4. 现在的状况就是临时文件里面都是有序段，那么下面要做的就是merge，如果初始有R个有序段，那么通过logR趟(pass)merge，生成最终的有序段，即排序完成，这是个标准的外排序的做法。
5. 最后将这个临时文件顺序读出来生成最终的压缩倒排文件，完成后可删掉临时文件。
这个方法的好处就是一直是顺序读磁盘，没有那种需要查找遍历的随机访问。但有个问题就是会耗费比较多的磁盘，因为你在做两段merge的时候，merge的结果必须存到一个新的临时文件中，就是峰值需要超过原始文件2倍的磁盘空间。
索引压缩
前面说了，基于排序的倒排要耗费过多的磁盘资源， 所以下面要谈的是，怎么在创建倒排文件时尽量减少磁盘资源的耗费。
压缩临时文件
临时文件里面都是存放了三元组 <t, d, fd,t >，对于 d, fd,t 的压缩前面在索引压缩时候就谈过，方法很多
那么就来看看t的压缩
在每个有序归并段中，t值是非减的，所以选择差分编码是自然的选择，就是记录这个t和前一个的差值，这个t-gap是零或大于零的整数。
可以直接用一元编码来进行编码，那么可以想象的出，这样存储t所需的空间是很小的
可以看出想要有比较好的压缩效果，必须对有序段做压缩，上面的算法改成这样
对于2，3合并为
遍历每篇文档，取出term组成三元组<t, d, fd,t >这里不直接存到临时文件，先存在内存中，当内存中存放的三元组条数达到k时，对这k条三元组进行排序，然后压缩，最后把这个压缩过的有序段写入临时文件。
4.因为有序段时压缩编码过的，所以在并归的时候要先解码，并归完再压缩编码，写回临时文件
原地多路并归
并归阶段是处理器密集型，而不是磁盘密集型， 所以使用多路并归可以进一步降低倒排时间。
推广一下， 假定当前全部的R个并归段进行R路并归，先要从每个并归段读入一个b字节的块，这个b的大小取决于内存大小，这个块是每个并归段的buffer，当一个并归段的块被读完，则从磁盘上再读入一块。
R路并归需要用到最小堆来从候选集合中有效的找到最小值。
那么不断的从堆顶取到最小值写入新的临时文件中， 直到最后完成排序。那么这样我们还是需要2倍原始文件的磁盘耗费，能不能进行原地并归了，下面就介绍一下原地多路并归算法，这个算法比较复杂，也挺有意思
原地并归，就是不占用更多的磁盘空间，并归完后还是写回原临时文件，而不用写入新的临时文件，为达到这个目的有几点是需要认真考虑的
1. 要进行R路并归，会先从每个并归段读入b字节的块到内存，那么容易想到我们只要把排序的结果也组成b字节的块，就可以覆盖到这些已被读过的块空间上，实现原地并归。
问题是每个并归块不一定是b的整数倍，最后读出的一个块可能会小于b，那么这样这个不规则的块会给这个算法带来困扰，那么这个的解决办法很简单，就是padding，对每个并归段后面加上padding，使他一定为b的整数倍。
2. 按上面的说法，我们把排好序的块写回被读过的空块中，有个问题是这些空块是零散的，无序的。所以我们需要一个快表block table来记录块的顺序，如block_table[1]表示当前临时文件中的第一块实际的块顺序是多少，比如block_table[1]＝3，表示 现在放第一块的应该移到第三块。
那么所以最后我们还要根据block table对临时文件进行重排，以恢复原来的顺序，这个算法是可以在线性时间里完成的
算法如下，算法的目的就是满足block_table[i]＝i，
从1到n遍历块表，如果block_table[i] 设为k不等于i, 说明临时文件第i块里面放的不是真正顺序上的第i块，
那么做法是，把当前的第i块放到缓存中，然后去找block_table[j]＝i，就是找出顺序上的第i块，放到i位置上
现在第j块空出来了， 看一下k是否等于j，如果等于正好放到j位置上
如果不等于，继续去找block_table[s]＝j，放到j位置上，这样一直找下去，直到block_table[k]，可以把缓存中的第k块放进去。
当遍历一遍，保证从1到n块都满足block_table[i]＝i，则重排完成。
3. b值大小的选取，如果b值选的过大会导致内存中放不下R+1个b块，选的过小会耗费过多的磁盘读写次数。
做法是给b一个2的幂形式的初值，这样当b过大时，方便b/2来折半，而且这种方法保证归并段仍然是新的b值的倍数。
那么具体做法就是当b*(R+1) > M时，set b ＝ b/2
那么给出原地并归的完整算法，
1. 初始化
创建空字典S
创建空临时文件
设 L为字典占的空间大小
设 k =(M -L)/w, k为并归段包含三元组的个数，w为一个三元组 <t, d, fd,t >所占用的空间
设 b ＝ 50Kb
设 R ＝0， R为并归段的个数
2. 处理文档和生成临时文件
遍历每一篇文档D
parse文档成term
对于每个term
如果term在S中存在，取出termid
在S中不存在
把term加到S中
更新L，k （因为字典S变大，使可用内存变小，所以k会变小）
把<t, d, fd,t >加到triple数组中
任何时候，当triple数组中的triple个数达到k时，生成一个并归段
对并归段按term进行排序
对各个field进行压缩
最后对并归段进行padding，保证是b的倍数，写入临时文件
R = R+1
当b*(R+1) > M时，set b ＝ b/2
3. 并归
从每个并归段读入一块，在这些块的number加到freelist里面， 就是说这些块读过了，可以被输出块覆盖
从每个块取一个triple，共R个triple，建最小堆
不断取堆顶triple， 放到输出块中， 并从相应的块中取新的triple加到堆中
当输出块满的时候，从freelist中找一个空的块，如果没有空的，就创建一个新的块append到临时文件后。
把输出块写入这个空块，更新freelist和block table
同时当每个并归段读入的块耗完的时候，再读相应并归段的next block，并更新freelist
4. 临时文件重排
5. Truncate 并释放尾部无用的空间
压缩的内存内倒排
现在把基于排序的倒排方法放在一边， 回到前面提到的内存内的链结列表方法，这种方法结合压缩技术也可以达到比较好的效果。
现在将要描述的这个方法，基于一个假设就是，每个术语t的文档频率ft 在倒排前已知。 当然想要已知，实现中，就是先遍历统计一遍，第二遍再来建立倒排。
那么费这个劲去预先统计术语t的文档频率ft 有什么好处吗
a. 之前每个term的倒排列表都是用单向链表的结构来实现，因为你不知道到底有多少文档，必须动态的；那么现在你知道文档频率，那么就可以确切知道需要分配多少空间了，可以用数组来代替单项链表，那么至少可以省下这个next指针的耗费。
b. 知道文档的总数N，那么文档编号可以用logN位去编码，而不用整型大小32位
c. 同样知道最大的文档内频率m，也可以用logm位编码fd,t
总之就是说，事先知道一些信息，可以减少数据编码的可能性，也就是说信息熵变小，所以用于编码的位数也就会变小，从而节省了空间。
当然这样做对于内存的占用还是很大，那么又有底下两种方法，来减少内存的消耗
基于字典的切分
基于文本的切分
原理就是把全部倒排列表放内存里面太大，那么就把建倒排的任务分成若干个小任务，每次在内存里面只保留倒排的一部分
基于字典的切分，就是每次只建立和部分term相关的倒排，分多趟覆盖整个字典。
基于文本的切分，就是每次只建立部分文本的倒排，分多趟覆盖整个文本集。
本文章摘自博客园，原文发布日期：2011-07-04