lucene3.0.3中的数字索引以及数字范围查询

      我看了3个下午，加上一个上午终于看懂了lucene对于数字的索引和对于数字范围的检索，主要的时间都是花在了NumericRangeQuery上，尽管一次一次的失败但是我并没有放弃的打算，研究与探索本来就是我的一大兴趣，最后的喜悦要比之前所有的痛苦都要来的爽！谢谢笔记，方便可能正在迷茫的你。备注：如果你对lucene的索引格式不熟悉尤其刚接触lucene的话，请绕行，这片笔记只适合对源码有深入研究的程序员。

      对于数字的索引并不是直接将数字变为字符串，因为这样的话没法进行范围搜索，比如我们索引1、5、20、56、89、200、201、202、203...299、500，如果按照lucene的字符排序，这些term在词典表中的排序为1、20、200、201、202、203...299、5、56、500、89，显然他的顺序是没有用于范围查询的，如果我们要进行范围搜索1-300的话，我们就要穷尽所有该域下的term，因为可能有以9开头的term，但是他出现在所有的term的最后面，所以明显按照字符顺序排序不是最好的排序方式。我们看卡luene是怎么样存储的，对于数字的域，是使用lucene的NumeircField，他里面有个最重要的属性是TokenStream——NumericTokenStream，它用来将这个域的数字进行分词（也就是形成一个特里树），看下他的incrementToken方法，该方法用于对数字进行分词，这里我们以long（也就是64位作为例子）型的数字作为例子，进行分词的方法是调用的NumericUtils.longToPrefixCoded方法：

/** 将一个数字值分多次进行shift，一次处理precisionStep的位数 */
@Override
public boolean incrementToken() {
	
	if (valSize == 0)
		throw new IllegalStateException("call set???Value() before usage");
	if (shift >= valSize)
		return false;
	clearAttributes();
	final char[] buffer;
	switch (valSize) {
		case 64:
			buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_LONG);
			// 将数字变为字符，返回的字符内容放入buffer中
                        // 每调用一次会形成一个字符串，放入到buffer中，所以关键的就是这个方法，他会使用到当前已经处理的位数已经精度的位数
			termAtt.setTermLength(NumericUtils.longToPrefixCoded(value, shift, buffer));
			break;
		case 32:
			buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_INT);
			termAtt.setTermLength(NumericUtils.intToPrefixCoded((int) value, shift, buffer));
			break;
		default:
			// should not happen
			throw new IllegalArgumentException("valSize must be 32 or 64");
	}
	typeAtt.setType((shift == 0) ? TOKEN_TYPE_FULL_PREC : TOKEN_TYPE_LOWER_PREC);
	posIncrAtt.setPositionIncrement((shift == 0) ? 1 : 0);//第一次的时候表示是一个数字，非第一次为0表示是同一个数字，所以位置增量是0
	shift += precisionStep;//增加偏移量
	return true;
	
}

 在上面的方法中有两个重要的属性，一个是shift，一个是precisionStep，在计算机中，数字用二进制表示，在进行分词的时候他的思路是每次都向左偏移precisionStep的位数，被偏移过的数字都被忽略，而剩余的数字则形成一个字符串，precisionStep就是每次都偏移的二进制的位数，而shift表示现在已经偏移过的总的位数，我们看下NumericUtils.longToPrefixCoded的源码：

public static int longToPrefixCoded(final long val, final int shift, final char[] buffer) {
		
	if (shift > 63 || shift < 0) 
		throw new IllegalArgumentException("Illegal shift value, must be 0..63");
	
	// 计算本次处理的所有的位数要生成的char的个数，计算的规则为 64-已经处理的位数（也就是shift）然后除以7，因为后面用每7个bit位形成一个字符，（63-shift）/7 + 1等价于这个意思。
	int nChars = (63 - shift) / 7 + 1;
	
	// 这个是本次处理的所有的位数加上记录偏移量的字符产生的char的总个数，比上面的多一的原因是第一个字符用于存储偏移量，偏移量用32+shift表示，形成一个字符。
	int len = nChars + 1;
	// 填写第一个字符——偏移的位数，为32+shift 用第一位表示偏移量也是有原因的，因为偏移量越大他的位数也就越高，那么表示的数也就越大（所有的数字在存储时都是有偏移量的，刚上来的是偏移量为0）， 这一点和字符串的字符顺序也是对应的，如果高位（靠左边）更大则这个字符串会排在后面（即 bx 一定在ax后面）
	buffer[0] = (char) (SHIFT_START_LONG + shift);
		
	//0x8000000000000000L这个数字是第64位为1，其他位为0。抑或他的目的是将最高位取反，也就是如果原来是正数符号位变为1，负数的符合位变为0。通过这个操作后，所有的负数排在正数的前面，且正数的相对位置不变，负数的也不变化。（此步骤自己想，我在这里不做解释）
	long sortableBits = val ^ 0x8000000000000000L;
	sortableBits >>>= shift; //不计算已经shift的位数，只计算还剩余的位数。
	while (nChars >= 1) { //循环，每7位处理一次，这里之所以用7位形成一个字符也是有原因的，因为最终在磁盘上是使用utf-8格式，7位的话最大是127，在127以下时utf8编码采用的是一个字节表示一个字符，这时最节省空间。
		// Store 7 bits per character for good efficiency when UTF-8 encoding.
		// The whole number is right-justified so that lucene can
		// prefix-encode the terms more efficiently.  。
		// 只取最后的7个bit，形成一个char。也就是每7个bit形成一个char，放入到buffer中
		buffer[nChars--] = (char) (sortableBits & 0x7f);
		sortableBits >>>= 7;//继续处理下一个7位
	}
	return len;
} 

 

 

上面的方法用二进制描述不太形象，我们用十进制来举个例子，假设我们要索引的是8153这个数字，我们的precisionStep是1，也就是每一次偏移一个十进制的位，第一次shift是0，所以整个8152会形成一个字符串，外加上用于存储偏移量的位数（在这里我们省去用来表示偏移量的位数，并直接用数字的字符串形式作为最终形成的字符串），所以第一次形成的字符串是8153，第二次是815（但是偏移量是1），第三次是81（偏移量是2），第四次是8（偏移量是3），所以很容易发现他是一个特里结构，他形成的这四个term的意思也可以这样理解，8xxx的或者是81xx的或者是815x的，还有最精确的8153都是可以搜索到当前的文档。现在我们把precision变大一点，为两个十进制的位，则会形成8153和81，他表示在8153和81xx这两个term都可以搜到这个document。可以发现，当precision更小的时候，会生成更多的term，那么索引也一定会更大（如果precision过大，其实在进行范围搜索的时候会降低速度，这个到搜索的时候再说）。当我们在索引别的数字的时候就会继续形成不同的term，所有的这些term会最终组成一个特里树，并且precisionStep越小这个树的节点就会越多，最终的索引的体积也会越大。

      

        搜索：NumericRangeQuery  这个类用于使用特里树进行范围的搜索，他的关键是对要进行搜索的范围进行分词，找到在特里树上的节点（也就是之前建立索引时声称的term）然后再按照重写规则对所有找到的term进行重写，比如声称一个booleanQuery，或者是生成一个filter，就这么简单，但是他花费了我很长的时间才看懂。NumericRangeQuery最关键的部分就是找到之前的term，通过调用它的getEnum方法，该方法返回了一个NumericRangeTermEnum，我们看看它的代码：

// 将查询区间分解成若干个小的查询区间
NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
	@Override
	public final void addRange(String minPrefixCoded, String maxPrefixCoded) {
		rangeBounds.add(minPrefixCoded);
		rangeBounds.add(maxPrefixCoded);
	}
}, precisionStep, minBound, maxBound);

 上述方法就是根据要查找的区间范围（也就是最大值和最小值）以及prerecisionStep，找到形成的特里树上的节点，将这些节点放入到一个链表里面，提一句，在NumericRangeTermEnum的构造方法里面，已经将所有的对比转化为>=或者是<=，我们看一下NumericUtils.splitLongRange方法

/** 将查询区间分解成若干个小的查询区间*/
private static void splitRange(final Object builder, final int valSize, final int precisionStep, long minBound,//下线
		long maxBound/*上线*/) {
	if (precisionStep < 1)
		throw new IllegalArgumentException("precisionStep must be >=1");
	if (minBound > maxBound)
		return;
	for (int shift = 0;; shift += precisionStep) {
		
		// calculate new bounds for inner precision 
		final long diff = 1L << (shift + precisionStep); 
		final long mask = ((1L << precisionStep) - 1L) << shift;//当前精度范围的最大值
			
		// minBound在本次处理的精度内有没有要限制的部分，如果等于0说明是本精度范围内没有任何限制，也就是本精度范围的任何值都是可以的。继续匹配上一个精度即可。
		// 如果是true，则说明本精度范围要添加限制，所以在后面有addRange （看下面的解释1）。 
		final boolean hasLower = (minBound & mask) != 0L;
		// 因为mask是次精度范围的最大值，如果等于mask说明本层次的所有值都符合要求，不等于说明是有限制的，有的term是不包含的。
		// 如果是true，则本精度要添加限制，所以后面有addRange （看解释2）
		final boolean hasUpper = (maxBound & mask) != mask;  
		
		
		// 如果在当前区间有值的话就会要加diff，即下一次的区间一定要大于下一个精度的最小值（也就是加一个下一个精度的最小值），然后把当前的精度的限制去掉之后
		// 比如十进制中的 632，precisionStp是1，在把632中的2删掉之后，不能仅仅是63x，因为这样话，631  630也会匹配，所以要加一个十进位的1，表示64x的任意值都是可以的，而不是63x。
		final long nextMinBound = (hasLower ? (minBound + diff) : minBound) & ~mask;//&~mask 将shift到shift+precisionStep位变为0.
		
		// 道理和上面的一样，比如十进制中的对比，如果最后一位是9的话则任何本精度的值都会满足，则直接对比下一个精度即可，如果maxBound是765，则不能仅仅是删掉最后的精度5，因为单纯的76x并不能完全限制，
		// 因为769  768 这样的值在第二个精度的时候也会满足条件。所以必须减小一位下一个精度，也就是使用75x是可以的。
		final long nextMaxBound = (hasUpper ? (maxBound - diff) : maxBound) & ~mask;
		
		// 这两个是极端的情况，看下面的解释三
		final boolean lowerWrapped = nextMinBound < minBound;
		final boolean upperWrapped = nextMaxBound > maxBound;
		
		// 1、第一个判断是有没有下一个精度
		// 2、第二个判断是下一个精度是不是交叉，即最小值比最大值要大，如果是这样，就不再对比了，因为在继续下去仍然是最小值大于最大值。
		// 3、4的原理在解释3、4中
		if (shift + precisionStep >= valSize || nextMinBound > nextMaxBound || lowerWrapped || upperWrapped) {
			// We are in the lowest precision or the next precision is not available.
			addRange(builder, valSize, minBound, maxBound, shift);
			// exit the split recursion loop
			break;
		}
		
		if (hasLower)
                        //添加最小的区间限制
			addRange(builder, valSize, minBound, minBound | mask, shift);//minBound是当前精度的最小值，minBound|mask表示当前精度的最大值，
		
		if (hasUpper)
                         //添加最大的区间限制
			addRange(builder, valSize, maxBound & ~mask, maxBound, shift);

		minBound = nextMinBound;
		maxBound = nextMaxBound;
	}
}

       解释1：final boolean hasLower = (minBound & mask) != 0L;  如果minBound和当前精度的最大值做对比等于0，说明minBound在当前精度范围的所有位都是0，那么次精度范围任何一个值都满足>=0的要求，所以他就不用添加一个节点了，此精度范围内不会形成一个限制的节点，继续减小精度即可。相反，如果当前精度范围内是有限制的，也就是不是最小值，那么就要添加一个限制的节点用来限制查找的结果，所以当前为true的时候，会在后面添加addRange方法（等会再看）。

 

      解释2：final boolean hasUpper = (maxBound & mask) != mask，如果maxBound 和当前精度的最大值相等，则在当前精度范围内，所有的值都会满足<=maxBound的要求，这是就不用添加当前精度的限制了，继续减小精度即可。

  解释3：nextMinBound < minBound; 貌似是所有的nextMinBound都要大于minBound，因为nextMinBound都加上了下一个精度的最小值，怎么可能比minBound小呢？其实不是，因为他是有64位或者是32位限制的，我们还是用10进制来描述，因为计算机中有32位 64位的限制，我们在10进制中用3位的限制，所以我们在处理997的时候，已经在处理过最后的7之后，我们要加上10，再删除最后的一位，则就会变为100x，由于3位的限制，所以就会变为00x，这里的判断就是这种情况。当出现这种情况时，说明minBound已经是下一个精度范围的最大值了，现在已经不能继续往特里树的根前进了，所以要退出查找更多term的循环。

  解释4：nextMaxBound > maxBound;道理和上面的3一样，我们还是举10进制的例子：比如我们处理的是003，precisionStep是1，十进制的位数限制为3,，现在处理的3，然后前往下一个precisionStep，减10，则变为负数了，所以就会出现这种情况，他的意思是已经无法再特里树里面找到更深的节点了。

 

 

addRange方法：最终还是调用的longToPrefix方法，将数字变为字符串，然后放入到一个链表里面，对于每一次调动都会添加两个term。

 

我们再看一下最后他是如何使用产生的这些term的，在org.apache.lucene.search.NumericRangeQuery.NumericRangeTermEnum.next()方法中

/** Increments the enumeration to the next element. True if one exists. */
@Override
public boolean next() throws IOException {
	
        //这里的操作貌似没有必要关闭当前的termEnum，为什么不通过调用一个termEnum不停的读呢？为什么还要关掉然后重新打开？
        //因为在搜集词典表中的term的时候，他们不是挨着的，还有一个原因是特里树里面的限制性的节点限制的term通过从前向后读取是读取不到的，要重新从头读取，不一点不像一般的term的查找，
        //而通过使用词典表的索引（通过使用3.0中的tii文件），也就是在下面while中的创建termEnum的方式，可以更加快速的找到要查找的term。
	// if a current term exists, the actual enum is initialized:
	// try change to next term, if no such term exists, fall-through
	if (currentTerm != null) {
		assert actualEnum != null;
		if (actualEnum.next()) {
			currentTerm = actualEnum.term();
			if (termCompare(currentTerm))
				return true;
		}
	}
	
	// if all above fails, we go forward to the next enum, if one is available
	currentTerm = null;
	while (rangeBounds.size() >= 2) {//只要还剩最后的两个，也就值最后退出循环的addRange
		
		assert rangeBounds.size() % 2 == 0;
		// close the current enum and read next bounds
		if (actualEnum != null) {
			actualEnum.close();
			actualEnum = null;
		}
		final String lowerBound = rangeBounds.removeFirst();//
		this.currentUpperBound = rangeBounds.removeFirst();
		// create a new enum
		actualEnum = reader.terms(termTemplate.createTerm(lowerBound));
		currentTerm = actualEnum.term();
		if (currentTerm != null && termCompare(currentTerm))
			return true;
		// clear the current term for next iteration
		currentTerm = null;
	}
			
	// no more sub-range enums available
	assert rangeBounds.size() == 0 && currentTerm == null;
	return false;
}

 他的思路是根据产生的用来作为限制条件的term，来查找处于他们区间的所有term，所以到这里思路就明朗起来了，概括一下：他是根据maxBoung和minBound和precisionStep产生多个限制的term，然后根据这些限制性的term在词典表中来查找所有的处于他们去见的term，使用这个办法的好处是：他能减少对叶子节点的使用，因为在生成所有的限制性term的时候，都是使用的特里树的父节点，以及父节点的父节点，直到已经没有父节点了或者是maxBound和minBound相互交叉，这样在查找的时候词典表就会绕过大量的term，只寻找在限制性节点之间的term，使得搜索到的term的数量大大减少，从而加速搜索的速度。

在搜索时使用的precisionStep的大小的影响：此值越大，则生成的特里树深度越浅，限制性节点的范围越大，查找到的term的数量就会更多，在合并倒排表的时候就会越慢；此值越小，则生成的特里树的深度越大，限制性节点的个数越大，搜索到的term的数量越小，合并时的速度越大。