3.5.2 索引原理
为了方便索引大量的文档，可以将Lucene中的一个索引分成若干个子索引，称为段(segment)。段中包含一些可搜索的文档。在给定的段中可以快速遍历任何给定索引词在所有文档中出现的频率和位置。IndexWriter收集在内存中的多个文档，然后在某个时间点把这些文档写入一个新的段，写入点可以通过Lucene内部的配置类或者外部程序控制。这些文档组成的段将保持不动，直到Lucene把它合并进大的段。MergePolicy控制Lucene如何合并段。
索引文档时，首先对文档分词后建立正排索引，然后建立倒排索引。在索引优化阶段，会把小的段合并成大的段。其中可能用到的算法有：合并两个排好序的数组成为一个大的排好序的数组。
为了提高性能，索引首先缓存在内存中，如果缓存达到预定的内存数量，就会写入硬盘。然而，即使IndexWriter从缓存中把这些文档的索引写入硬盘，在没有提交之前IndexReader也不能看到这些新加入的文档。如果频繁地调用IndexWriter.commit就会降低索引的通量。所以不要过于频繁地提交索引。可以通过测试来决定具体加入多少篇文档后再提交索引。索引文件的逻辑视图如图3-15所示。
图3-15 索引文件的逻辑视图
Lucene把一个文档写入索引时，首先生成这个文档的倒排索引，然后再把文档的倒排索引合并到段的倒排索引中。先看一下最简单的统计一个文档中所有单词出现频次的例子：
//单词和对应的次数
HashMap<String, Integer> postingTable = new HashMap<String, Integer>();
StringTokenizer st = new StringTokenizer(inputStr);
while(st.hasMoreTokens()){ //按空格切分输入串
String word = st.nextToken();
//检查单词是否在HashMap中
if (postingTable.containsKey(word)) {
//取得单词出现次数，加1后放回去
postingTable.put(word, postingTable.get(word) + 1);
} else {
//第一次看到这个单词，设置次数为1次
postingTable.put(word, 1);
}
}
描述单个文档的Posting表由Posting类组成的数组构成：
final class Posting { // 一个文档中的一个词相关的信息
Term term; // 词
int freq; // 这个词在文档中的频率
int[] positions; // 词出现的位置
}
生成文档的倒排索引的简略代码如下：
final void addDocument(Document doc)
throws IOException {
//使用散列表缓存词和位置对应关系
Hashtable<Term, Posting> postingTable = new Hashtable<Term, Posting>();
//invertDocument对文档倒排，具体执行的工作有：
//对文档内容分词，然后把每个词放入postingTable
//postingTable.put(term, new Posting(term, position, offset));
invertDocument(doc);
//对postingTable排序后放入数组
Posting[] postings = sortPostingTable();
}
首先按列读入每个文档，然后处理同名的列。之后，把每个新列中的数据写到缓存。
textStart也是用来区分词的唯一值，但是这个值太大了，不方便存储，所以要重新生成一个连续编号的termID。
postingsArray用来记录一个词之前有没有看到过。如果以前没看到过，就调用newTerm(termID)方法，否则就调用addTerm(termID)方法。
if(! postingsArray.textStarts.contains(textStart)){
int termID = numPostings++;
postingsArray.textStarts[termID] = textStart;
consumer.newTerm(termID);
}else{
consumer.addTerm(termID);
}
postingsHash数组用来加快这个判断过程。可以把它看成散列表中的数组表。并行数组postingsArray中的textStarts则用来判断是否包含当前词。
在reset()方法中，把postingsHash中的初始值设置成-1。
Arrays.fill(postingsHash, 0, numPostings, -1);
初始化的原理代码如下：
int postingsHashSize = 4;
int[] postingsHash = new int[postingsHashSize];
int postingsHashMask = postingsHashSize-1;
根据词所在的位置来找槽的位置。值是词编号。使用二次探测再散列法解决冲突。
int code = textStart;
int hashPos = code & postingsHashMask;
// 定位散列表中的RawPostingList
int termID = postingsHash[hashPos];
if (termID ! = -1 && postingsArray.textStarts[termID] ! = textStart) {
// Conflict: keep searching different locations in
// the hash table.
final int inc = ((code>>8)+code)|1;
do {
code += inc;
hashPos = code & postingsHashMask;
termID = postingsHash[hashPos];
} while (termID ! = -1 && postingsArray.textStarts[termID] ! = textStart);
}
如果发现一个词没有在postingsHash存过，就在postingsHash中记录这个词的编号。
int numPostings = 0;
int termID = numPostings++;
int code = 100; //词所在的位置
int hashPos = code & postingsHashMask;
postingsHash[hashPos] = termID;
然后压缩掉没有用到的位置。
private void compactPostings() {
int upto = 0; //记录已经填实的位置
for(int i=0; i<postingsHashSize; i++) { //从前往后遍历postingsHash中的每一个值
if (postingsHash[i] ! = -1) { //如果不是初始值
if (upto < i) { //而且中间有空位
postingsHash[upto] = postingsHash[i]; //压缩
postingsHash[i] = -1; //标志这个位置已经空了
}
upto++; //已经填实的位置标志加1
}
}
}
得到的是一个词编号序列。
倒排索引在FreqProxTermsWriter类的appendPostings()方法中创建，基于从文档中统计出的信息，例如词频、文档频率、词位置等。
DocumentsWriter中包含一个索引链。
Consumer是一个定义接口的抽象类。索引时，在不同的层次，有不同的Consumer类。例如DocConsumer处理整个文档。DocFieldConsumer处理不同的列，每次处理一个。
InvertedDocConsumer消耗产生的词序列。
TermsHashConsumer写和它自己相关的字节到内存中的posting lists(投递列表)。posting lists以字节切片存储，按词索引。
DocumentsWriter*.java更简单了，它只和DocConsumer打交道，并不知道Consumer在做什么。
DocConsumer下面是做实际工作的索引链。
● NormsWriter在内存中记录归一化信息，然后把这些信息写入_X.nrm。
● FreqProxTermsWriter在内存中记录postings数据，然后写入_X.frq/prx。
● StoredFieldsWriter负责写入列存储的值信息，把内存中的值信息写入_X.fdx/fdt。
● TermVectorsTermsWriter把内存中的词向量信息写入_X.tvx/tvf/tvd。
DocumentsWriter虽然没有做具体的事情，但是仍然管理一些事情，例如清空一个段，关闭文档储存，缓存和使删除生效，释放内存，当需要的时候中止整个过程，等等。
DocInverterPerField得到位置信息。
FieldInvertState记录要加入索引的词数量。通过FieldInvertState的attributeSource属性取得最后坐标，也就是字段长度。
为了让posting list中的文档序列压缩后更小，可以把相似的文档聚类，让前后两个文档的编号值尽可能小。