Three steps to construct Inverted Index as following:

最难的step中：

1. Token sequence.
2. Sort by term.
3. Dictionary & Postings

第2步中的最现实的问题是：假如100G的terms如何排序？

External Sorting Algorithm

基于块的排序索引方法

注释：

4. 文档集读取

5. 排序

6. 排序结果f_i 存放到disk

7. Merge 这些排序结果为一个整体的Inverted Index list. 使用小窗口一点点地放入min-heap，

   堆顶端输出的是Inverted Index list的 dictionary部分，由小变大的顺序（因为f_i 已排序）

内存式单遍扫描索引构建方法

注释：

拥有同一hash value的terms的排序设计:

Insert-at-back and move-to-front heuristic 

 

每个块f_i 建立新dict；
去除了高代价的sort

最后一步依然是 MergeBlocks(.)

动态索引 - Dynamic Indexing

注释：

Main Index在Disk; Auxiliary Index在Memory。

可以视为 Immediate Merge 与 No merge 的一个折中。

由于每个倒排记录在 log₂(T/n)层 的每一层中都只处理一次，因此整个索引构建的时间是Θ(T*log₂(T/n))。

引伸：

求Disk中最后留下的Index的数量。

We use |C| to denote the total size of the document collection, and M to denote the memory size.

Let‘s assume that: C = h*M

For i in [0, log2h]{　　X = [h - (2i – 1)] mod [2i+1]　　If X belong to (0, 2i],　　　　exist in column.　　Else,　　　　not exist.}
The sum of existing X is the answer.

[IR] Index Construction