lucene中的docValue实现源码解读（七）——SortedDocValue的读取

之前的一个博客中写了sortedDocValue的写入，这次看看再使用sortedDocValue的时候是如何读取的。读取的方法还是掌握在Lucene410DocValuesProducer中，方法是public SortedDocValues getSorted(FieldInfo field)，我们先看一下这个方法返回的对象SortedDocValue吧，在这个类的源码中可以发现这个类是继承自于BinaryDocValues，所以上一篇博客中说的SortedDocValue就是SortedBinaryDocValue也就是正确的了，lucene是故意省去了Binary。他的方法除了BinaryDocValue的ByteRef get( int docid）之外，又增加了很多，如下：

public abstract class SortedDocValues extends BinaryDocValues {
  /**
   * Returns the ordinal for the specified docID. 返回制定的doc的byte[]的排序，如果看懂了上一篇博客的话，就很容易的知道是使用了存储结构的Numeric部分。
   * @param  docID document ID to lookup
   * @return ordinal for the document: this is dense, starts at 0, then increments by 1 for the next value in sorted order. Note that missing values are indicated by -1.如果一个doc没有的值的话返回的-1
   */
  public abstract int getOrd(int docID);

  /** 
   * 根据排序找到对应的byte[]。根据上一篇博客，可以知道是读取的binary部分，根据ord确定要读取的是哪个小块，然后根据第一部分的第二个小部分（记录每个小块的索引）找到对应的开始位置，然后读取指定的byte[]。
   */
  public abstract BytesRef lookupOrd(int ord);

  /**
   * 返回所有的byte[]的个数。
   */
  public abstract int getValueCount();

  private final BytesRef empty = new BytesRef();

  @Override
  public BytesRef get(int docID) {//这个是重写了BinaryDocValue的get方法，即根据docid获得对应的byte[]
    int ord = getOrd(docID);//获得这个doc次序，这个是读取的第二部分，即Numeric部分
    if (ord == -1) {
      return empty;
    } else {
      return lookupOrd(ord);//根据次序再次查找
    }
  }

  /** 
   * 得到这个key的次序，如果不存在，返回一个负数
   */
  public int lookupTerm(BytesRef key) {
    int low = 0;
    int high = getValueCount()-1;
    //使用二分法查找，不过要查询很多次，
    while (low <= high) {
      int mid = (low + high) >>> 1;
      final BytesRef term = lookupOrd(mid);
      int cmp = term.compareTo(key);
      if (cmp < 0) {//这个key要比term大一些，所以要向右查找
        low = mid + 1;
      } else if (cmp > 0) {////这个key要比term小一些，所以要向左查找
        high = mid - 1;
      } else {
        return mid; // key found
      }
    }
    return -(low + 1);  // key not found.
  }
  
  /**
   * 这个是返回一个迭代器，迭代所有的写入的byte[]。
   */
  public TermsEnum termsEnum() {
    return new SortedDocValuesTermsEnum(this);
  }
}

看完了SortedDocValue的方法之后，我们几乎可以猜测他的读取的过程，还是看看源码吧，和之前的读取的过程一样，在Lucene410DocValuesProducer的构造方法中就会读取所有的meta（也就是docValue的索引）文件，对应于SortedDocValue的如下：

 

private void readSortedField(int fieldNumber, IndexInput meta, FieldInfos infos) throws IOException {
	// sorted = binary + numeric
	if (meta.readVInt() != fieldNumber) {
		throw new CorruptIndexException(
				"sorted entry for field: " + fieldNumber + " is corrupt (resource=" + meta + ")");
	}
	if (meta.readByte() != Lucene410DocValuesFormat.BINARY) {
		throw new CorruptIndexException(
				"sorted entry for field: " + fieldNumber + " is corrupt (resource=" + meta + ")");
	}
	
	BinaryEntry b = readBinaryEntry(meta);//读取binary，也就是第一部分，不过这次和之前的格式是不一样的，这次使用的前缀的压缩，所以我们有必要再次回到readBinaryEntry方法
	binaries.put(fieldNumber, b);//缓存

	if (meta.readVInt() != fieldNumber) {
		throw new CorruptIndexException(
				"sorted entry for field: " + fieldNumber + " is corrupt (resource=" + meta + ")");
	}
	if (meta.readByte() != Lucene410DocValuesFormat.NUMERIC) {
		throw new CorruptIndexException(
				"sorted entry for field: " + fieldNumber + " is corrupt (resource=" + meta + ")");
	}
	NumericEntry n = readNumericEntry(meta);//读取numeric，也就是第二部分，这一部分和之前的NumericDocValue是一样的，所以这里不再看了。
	ords.put(fieldNumber, n);//缓存读取的结果
}

 之前在BinaryDocValue的时候，看过readBinaryEntry，但是没有看前缀压缩的个数，所以再看一下，代码如下：

static BinaryEntry readBinaryEntry(IndexInput meta) throws IOException {
	BinaryEntry entry = new BinaryEntry();
	entry.format = meta.readVInt();//存储的格式
	entry.missingOffset = meta.readLong();//记录那些含有值的docSet的fp
	entry.minLength = meta.readVInt();//最小值
	entry.maxLength = meta.readVInt();//最大值
	entry.count = meta.readVLong();//所有的doc的数量（在sortedBinary中，这个是写入的byte[]的个数，不再是doc的数量了）
	entry.offset = meta.readLong();//真正的docValue的fp
	switch (entry.format) {
	case BINARY_FIXED_UNCOMPRESSED://忽略，我们看使用前缀压缩的那个
		break;
	case BINARY_PREFIX_COMPRESSED://这个是在sorted的docValue的时候使用的
		entry.addressesOffset = meta.readLong();//每个小块在data中的开始位置，也就是上一篇博客中说的第一大部分的第二小部分的开始位置
		entry.packedIntsVersion = meta.readVInt();
		entry.blockSize = meta.readVInt();
		entry.reverseIndexOffset = meta.readLong();//第一大部分的第三小部分的开始位置
		break;
	case BINARY_VARIABLE_UNCOMPRESSED:
		entry.addressesOffset = meta.readLong();//忽略，看使用前缀压缩的那个
		entry.packedIntsVersion = meta.readVInt();
		entry.blockSize = meta.readVInt();
		break;
	default:
		throw new CorruptIndexException("Unknown format: " + entry.format + ", input=" + meta);
	}
	return entry;
}

 看了之后也没发现什么，只是读取了三个索引，一个是docValue的开始的位置，第二个是记录每个小块的开始位置的索引，也就是第一大部分的第二小部分的开始位置，还有第一大部分的第三小部分的开始位置。但是没有读取第二大部分的位置，因为第二大部分是在readNumeric中读取的。

 

上面看完了读取meta文件的读取，下面 看看具体的查找docValue的过程吧，在里面一定会读取data文件中的第一部分和第二部分，所以我们先看下这两个方法吧，其中读取第一部分，也就是使用前缀压缩的docValue是很难得，而第二部分是读取numeric，这个和普通的NumericDocValue是一样的，之前已经写过了（是有三种格式的）所以略过了。

读取前缀压缩的docValue的方法是在getBinary中，如下：

public BinaryDocValues getBinary(FieldInfo field) throws IOException {
	BinaryEntry bytes = binaries.get(field.number);
	switch (bytes.format) {
	case BINARY_FIXED_UNCOMPRESSED:
		return getFixedBinary(field, bytes);//所有的byte[]长度一致的
	case BINARY_VARIABLE_UNCOMPRESSED:
		return getVariableBinary(field, bytes);//不一样的
		
	case BINARY_PREFIX_COMPRESSED://这个是用在sorted docValue里面，里面使用了前缀压缩，基于块存储
		return getCompressedBinary(field, bytes);
	default:
		throw new AssertionError();
	}
}

重点看第三个吧：

private BinaryDocValues getCompressedBinary(FieldInfo field, final BinaryEntry bytes) throws IOException {
	final MonotonicBlockPackedReader addresses = getIntervalInstance(field, bytes);//记录每个块在index中的地址，也就是第一大部分的第二部分的读取，读取进入一个MonotonicBlockPackedReader对象，可以将其看为是一个大的long数组
	final ReverseTermsIndex index = getReverseIndexInstance(field, bytes);//最后的那一部分
	assert addresses.size() > 0; // we don't have to handle empty case
	IndexInput slice = data.slice("terms", bytes.offset, bytes.addressesOffset - bytes.offset);//所有的小块的部分，从一开始到位置索引的部分
	return new CompressedBinaryDocValues(bytes, addresses, index, slice);//将所有的结果返回在一个对象里面。
}

  其中，因为篇幅的原因，我们忽略getIntervalInstance方法，也忽略getReverseIndexInstance方法，但是我们有必要看一下生成的CompressedBinaryDocValues对象，他也是一个BinaryDocValue，所以也有相应的方法，具体看一下：

static final class CompressedBinaryDocValues extends LongBinaryDocValues {
	public CompressedBinaryDocValues(BinaryEntry bytes, MonotonicBlockPackedReader addresses,ReverseTermsIndex index, IndexInput data) throws IOException {
		this.maxTermLength = bytes.maxLength;//所有的byte[]中最大的长度
		this.numValues = bytes.count;//byte[]的个数
		this.addresses = addresses;  //每个小块的存储位置
		this.numIndexValues = addresses.size();//所有的位置的个数，也就是小块的个数
		this.data = data;
		this.reverseTerms = index.terms;//存储的第一大部分的第三部分，也就是每隔1024个存储一个byte[]的地方
		this.reverseAddresses = index.termAddresses;//第一大部分的第三小部分的位置。
		this.numReverseIndexValues = reverseAddresses.size();//第一个大部分的第三小部分的大小。
		this.termsEnum = getTermsEnum(data);//获得term的枚举器，也就是用来查找所有的btye[]的对象。可以发现下面的很多方法都是调用的这个对象的方法。
	}
	@Override
	public BytesRef get(long id) {
		try {
			termsEnum.seekExact(id);//查找指定排序的BytesRef。调用的就是termEnum的方法
			return termsEnum.term();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}
	long lookupTerm(BytesRef key) {//根据字符串进行查询，如果存在返回其次序，否则返回负数
		try {
			switch (termsEnum.seekCeil(key)) {//
			case FOUND:
				return termsEnum.ord();
			case NOT_FOUND:
				return -termsEnum.ord() - 1;
			default:
				return -numValues - 1;
			}
		} catch (IOException bogus) {
			throw new RuntimeException(bogus);
		}
	}

	TermsEnum getTermsEnum() {
		try {
			return getTermsEnum(data.clone());
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

通过上面，可以发现最终要的就是获得一个TermEnum，而返回的就是一个CompressedBinaryTermsEnum，所以看下这个类的代码吧，尤其是要关注一下TermsEnum的方法

class CompressedBinaryTermsEnum extends TermsEnum {
	/** 当前读取的term的次序 */
	private long currentOrd = -1;
	// offset to the start of the current block
	private long currentBlockStart;
	/** 传入的data文件 */
	private final IndexInput input;
	// delta from currentBlockStart to start of each term
	/**这个是记录每个小块中不是第一个term的byte[] 在每个小块的第二部分的结束位置*/
	private final int offsets[] = new int[INTERVAL_COUNT];
	//每个小块中除了第一个byte[]意外的那些byte[]的自己的长度 前缀以外的自己的部分的开始地址
	private final byte buffer[] = new byte[2 * INTERVAL_COUNT - 1];
	/**当前读取的term*/
	private final BytesRef term = new BytesRef(maxTermLength);
	/** 每一个小块的第一个term   */
	private final BytesRef firstTerm = new BytesRef(maxTermLength);
	private final BytesRef scratch = new BytesRef();
	/** 传入的就是data文件 */
	CompressedBinaryTermsEnum(IndexInput input) throws IOException {
		this.input = input;
		input.seek(0);//指向这个文件的开始，因为在存储的时候，第一个位置就是存储的binaryDocValue。
	}
        //读取一个小块的第一部分
	private void readHeader() throws IOException {
		firstTerm.length = input.readVInt();
		input.readBytes(firstTerm.bytes, 0, firstTerm.length);//读取每个小块的第一个term
		input.readBytes(buffer, 0, INTERVAL_COUNT - 1);//在读取剩下的15个长度，这里说的长度说的是除了共享前缀以外每个byte[]自己的长度。读取到buffer里面
		if (buffer[0] == -1) {//表示是有超过255的，则读取short,在有超过255的时候会单独记录一个数字
			readShortAddresses();
		} else {
			readByteAddresses();
		}
		currentBlockStart = input.getFilePointer();
	}
	//这个方法和下面的readShortAddress看一个即可
	private void readByteAddresses() throws IOException {
		int addr = 0;//每个term的结束位置
		for (int i = 1; i < offsets.length; i++) {//从1开始，因为只记录15个
			addr += 2 + (buffer[i - 1] & 0xFF);//当前处理的term在当前小块中记录每个term自己的byte[]的部分的结束地址（不是开始而是结束）。这里的2是由两个1组成的，一个是在写入的时候就少写了一个byte的长度，所以要加上1，第二个是在每个term的单独的byte[]之前有一个
byte记录共享前缀的长度，所以也要加上这个byte，所以他的结束位置就是1（少写的1）+1（共享前缀的长度的1）+除了共享前缀之外的部分的长度。
这里的2是这样，原来保存长度是一个byte，并且在保存的时候buffer[i-1]中的值多减了一个byte，所以要再补回来。
			offsets[i] = addr;//这里是从1开始的，因为第0个表示的是这个块中第一个byte[]的偏移量，他就是0 ，所以这里从1开始。  这个offset表示的是这个块中除了第一个（即全部记录在beadbuffer中的那个外）其他的15个byte[]的信息在byteBuffer中的偏移量
		}
	}
	private void readShortAddresses() throws IOException {
		input.readBytes(buffer, INTERVAL_COUNT - 1, INTERVAL_COUNT);
		int addr = 0;
		for (int i = 1; i < offsets.length; i++) {
			int x = i << 1;
			addr += 2 + ((buffer[x - 1] << 8) | (buffer[x] & 0xFF));
			offsets[i] = addr;
		}
	}
	// 这个很简单，因为读取header的时候，已经把第一个term读取了，所以这里仅仅是将其设置到term中
	private void readFirstTerm() throws IOException {
		term.length = firstTerm.length;
		System.arraycopy(firstTerm.bytes, firstTerm.offset, term.bytes, 0, term.length);
	}
        //读取下一个term，从小块的第二部分中读取
	private void readTerm(int offset) throws IOException {
		int start = input.readByte() & 0xFF;//共享前缀的长度
		System.arraycopy(firstTerm.bytes, firstTerm.offset, term.bytes, 0, start);//将本小块的第一个term的值，也就是共享前缀复制到当前term中
		int suffix = offsets[offset] - offsets[offset - 1] - 1;//找到自己的字符串的长度，也就是每个小块的后半段中，属于自己的后缀的长度，计算方式为自己的长度-1,减一说因为有一个byte记录共享前缀的长度。
		input.readBytes(term.bytes, start, suffix);//读取自己的后缀，
		term.length = start + suffix;//移动自己的指针。这样就形成了一个term。
	}
	//读取下一个byte[]，这里都叫做term，因为这个TermEnum类原先就是用来读取词典表的
	public BytesRef next() throws IOException {
		currentOrd++;
		if (currentOrd >= numValues) {
			return null;
		} else {
			int offset = (int) (currentOrd & INTERVAL_MASK);//找到小块，因为是按照小块存储的。
			if (offset == 0) {//正好是一个小块的开头
				// switch to next block
				readHeader();//读取头文件，包括一个新的byte[]，以及多个剩余的byte[]的除了共享前缀的长度
				readFirstTerm();//每个小块的第一个term已经读取了，这里只是将其复制到term中
			} else {
				readTerm(offset);//如果当前指针是在小块中，则读取下一个term
			}
			return term;
		}
	}

        //这个就是在写写入docValue的时候说的那个，在第一个部分的最后一个部分，写入byte[]的索引，用来缩小查询的范围的。但是他的查询范围很大，因为在写入的时候是每隔1024个term才会添加，所以他很不准确。这个返回的是较小的指针，返回的是high，如果返回的是low就是较大的了
	long binarySearchIndex(BytesRef text) throws IOException {
		long low = 0;
		long high = numReverseIndexValues - 1;
		while (low <= high) {
			long mid = (low + high) >>> 1;
			reverseTerms.fill(scratch, reverseAddresses.get(mid));
			int cmp = scratch.compareTo(text);
			if (cmp < 0) {
				low = mid + 1;
			} else if (cmp > 0) {
				high = mid - 1;
			} else {
				return mid;
			}
		}
		return high;
	}
	// binary search against first term in block range to find term's block
	long binarySearchBlock(BytesRef text, long low, long high) throws IOException {
		while (low <= high) {
			long mid = (low + high) >>> 1;
			input.seek(addresses.get(mid));
			term.length = input.readVInt();
			input.readBytes(term.bytes, 0, term.length);
			int cmp = term.compareTo(text);

			if (cmp < 0) {
				low = mid + 1;
			} else if (cmp > 0) {
				high = mid - 1;
			} else {
				return mid;
			}
		}
		return high;
	}

        //查找指定的byte[]，先使用大范围的查找，然后再使用小范围的块查找。
	@Override
	public SeekStatus seekCeil(BytesRef text) throws IOException {
		// locate block: narrow to block range with index, then search blocks
		final long block;
		long indexPos = binarySearchIndex(text);//他的意思是先使用范围更大的那个索引来查找，缩小查找的范围，返回的是较小（比text更小）的下表
		if (indexPos < 0) {
			block = 0;
		} else {
			long low = indexPos << BLOCK_INTERVAL_SHIFT;//原来是1024个才有一个，现在要回归到16个一个，也就是从之前的小块中查找
			long high = Math.min(numIndexValues - 1, low + BLOCK_INTERVAL_MASK);//
			block = Math.max(low, binarySearchBlock(text, low, high));
		}

		// position before block, then scan to term.
		input.seek(addresses.get(block));//然后在使用小块，精确查找。找到小块的开始
		currentOrd = (block << INTERVAL_SHIFT) - 1;//

		while (next() != null) {
			int cmp = term.compareTo(text);
			if (cmp == 0) {
				return SeekStatus.FOUND;
			} else if (cmp > 0) {
				return SeekStatus.NOT_FOUND;
			}
		}
		return SeekStatus.END;
	}

	@Override
	public void seekExact(long ord) throws IOException {
		long block = ord >>> INTERVAL_SHIFT;//找到是第几个block。
		if (block != currentOrd >>> INTERVAL_SHIFT) {//如果和当前的不是一个块儿
			// switch to different block
			input.seek(addresses.get(block));//切换到指定的块
			readHeader();
		}

		currentOrd = ord;

		int offset = (int) (ord & INTERVAL_MASK);
		if (offset == 0) {//如果是第一个，
			readFirstTerm();
		} else {//不是
			input.seek(currentBlockStart + offsets[offset - 1]);
			readTerm(offset);
		}
	}

	@Override
	public BytesRef term() throws IOException {
		return term;
	}

	@Override
	public long ord() throws IOException {
		return currentOrd;
	}

	@Override
	public int docFreq() throws IOException {
		throw new UnsupportedOperationException();
	}

	@Override
	public long totalTermFreq() throws IOException {
		return -1;
	}

	@Override
	public DocsEnum docs(Bits liveDocs, DocsEnum reuse, int flags) throws IOException {
		throw new UnsupportedOperationException();
	}

	@Override
	public DocsAndPositionsEnum docsAndPositions(Bits liveDocs, DocsAndPositionsEnum reuse, int flags)
			throws IOException {
		throw new UnsupportedOperationException();
	}

	@Override
	public Comparator<BytesRef> getComparator() {
		return BytesRef.getUTF8SortedAsUnicodeComparator();
	}
}

 上面就看完了最后生成的TermEnum，几乎所有的方法都需要这个类，在有了这个类以后，就可以查看最终返回SortedDocValue的方法了。如下：

public SortedDocValues getSorted(FieldInfo field) throws IOException {
	final int valueCount = (int) binaries.get(field.number).count;
	final BinaryDocValues binary = getBinary(field);//读取data中的第一大部分，也就是存储docValue的部分，先看一下这个方法，在下面，然后再回到这里。
	NumericEntry entry = ords.get(field.number);
	final LongValues ordinals = getNumeric(entry);//读取data中的第二大部分，也就是存储每个doc的次序的部分。这个和之前的读取是一样的，所以这里不再重复了。
	return new SortedDocValues() {
		@Override
		public int getOrd(int docID) {//获得一个doc的次序，也就是排序，之前doc的存储就是根据docid存储的次序，所以这个很容易就可以读取到
			return (int) ordinals.get(docID);
		}
		@Override
		public BytesRef lookupOrd(int ord) {//根据排序找到值。
			return binary.get(ord);
		}
		@Override
		public int getValueCount() {//所有的byte[]的个数
			return valueCount;
		}
		@Override
		public int lookupTerm(BytesRef key) {//检查一个byte[]是否存在。
			if (binary instanceof CompressedBinaryDocValues) {//使用的是这个。
				return (int) ((CompressedBinaryDocValues) binary).lookupTerm(key);//查找term，如果找了返回其排序，否则返回一个负数。里面也是根据上面说的TermEnum来查找的。
			} else {
				return super.lookupTerm(key);
			}
		}
		@Override
		public TermsEnum termsEnum() {//获得所有的byte[]，
			if (binary instanceof CompressedBinaryDocValues) {
				return ((CompressedBinaryDocValues) binary).getTermsEnum();
			} else {
				return super.termsEnum();
			}
		}
	};
	
}

这样就看完了排序的doValue，最重要的是他的排序的存储，在存储的时候和lucene的词典表是一样的，并且读取的时候也是使用的lucene的TermEnum进行的封装。有了SortedDocValue，就能很容的得到某个doc的排名了，估计以后会用的上吧。