btree.java

这是外国一个开源推理机

			_setValueCount(++_valueCount);

			_dataChanged = true;
		}

		public void insertNodeIDValuePair(int nodeIdx, int nodeID, byte[] value) {
			int offset = _nodeIdx2offset(nodeIdx);

			// Shift values right of <offset> to the right
			_shiftData(offset, _valueIdx2offset(_valueCount), _slotSize);

			// Insert the new slot
			ByteArrayUtil.putInt(nodeID, _data, offset);
			ByteArrayUtil.put(value, _data, offset + 4);

			// Raise the value count
			_setValueCount(++_valueCount);

			_dataChanged = true;
		}

		/**
		 * Splits the node, moving half of its values to the supplied new node,
		 * inserting the supplied value-nodeID pair and returning the median
		 * value. The behaviour of this method when called on a node that isn't
		 * full is not specified and can produce unexpected results!
		 **/
		public byte[] splitAndInsert(byte[] newValue, int newNodeID, int newValueIdx, Node newNode) {
			// First store the new value-node pair in _data, then split it. This can
			// be done because _data got one spare slot when it was allocated.
			insertValueNodeIDPair(newValueIdx, newValue, newNodeID);

			// Node now contains exactly [_branchFactor] values. The median
			// value at index [_branchFactor/2] is moved to the parent
			// node, the values left of the median stay in this node, the
			// values right of the median are moved to the new node.
			int medianIdx = _branchFactor / 2;
			int medianOffset = _valueIdx2offset(medianIdx);
			int splitOffset = medianOffset + _valueSize;

			// Move all data (including the spare slot) to the right of <splitOffset> to the new node
			System.arraycopy(_data, splitOffset, newNode._data, 4, _data.length - splitOffset);

			// Get the median value
			byte[] medianValue = getValue(medianIdx);

			// Clear the right half of the data in this node
			_clearData(medianOffset, _data.length);

			// Update the value counts
			_setValueCount(medianIdx);
			newNode._setValueCount(_branchFactor - medianIdx - 1);
			newNode._dataChanged = true;

			// Return the median value; it should be inserted into the parent node
			return medianValue;
		}

		public void mergeWithRightSibling(byte[] medianValue, Node rightSibling) {
			// Append median value from parent node
			setValue(_valueCount, medianValue);

			// Append all values and node references from right sibling
			System.arraycopy(
					rightSibling._data, 4,
					_data, _nodeIdx2offset(_valueCount+1),
					_valueIdx2offset(rightSibling._valueCount) - 4);

			_setValueCount(_valueCount + 1 + rightSibling._valueCount);

			rightSibling._clearData(4, _valueIdx2offset(rightSibling._valueCount));
			rightSibling._setValueCount(0);
			rightSibling._dataChanged = true;
		}

		public void read()
			throws IOException
		{
			ByteBuffer buf = ByteBuffer.wrap(_data);
			// Don't fill the spare slot in _data:
			buf.limit(_nodeSize);
			_fileChannel.read(buf, _offset);

			_valueCount = ByteArrayUtil.getInt(_data, 0);
		}

		public void write()
			throws IOException
		{
			ByteBuffer buf = ByteBuffer.wrap(_data);
			// Don't write the spare slot in _data to the file:
			buf.limit(_nodeSize);
			_fileChannel.write(buf, _offset);
			_dataChanged = false;
		}

		/**
		 * Shifts the data between <tt>startOffset</tt> (inclusive) and
		 * <tt>endOffset</tt> (exclusive) <tt>shift</tt> positions to the right.
		 * Negative shift values can be used to shift data to the left.
		 **/
		private void _shiftData(int startOffset, int endOffset, int shift) {
			System.arraycopy(_data, startOffset, _data, startOffset + shift, endOffset - startOffset);
		}

		/**
		 * Clears the data between <tt>startOffset</tt> (inclusive) and
		 * <tt>endOffset</tt> (exclusive). All bytes in this range will be set
		 * to 0.
		 **/
		private void _clearData(int startOffset, int endOffset) {
			Arrays.fill(_data, startOffset, endOffset, (byte)0);
		}

		private void _setValueCount(int valueCount) {
			_valueCount = valueCount;
			ByteArrayUtil.putInt(_valueCount, _data, 0);
		}

		private int _valueIdx2offset(int id) {
			return 8 + id * _slotSize;
		}
		
		private int _nodeIdx2offset(int id) {
			return 4 + id * _slotSize;
		}
	}

/*----------------------------+
| Inner class SeqScanIterator |
+----------------------------*/

	private class SeqScanIterator implements BTreeIterator {

		private byte[] _searchKey;
		private byte[] _searchMask;

		private int _currentNodeID;
		private Node _currentNode;
		private int _currentIdx;

		public SeqScanIterator(byte[] searchKey, byte[] searchMask) {
			_searchKey = searchKey;
			_searchMask = searchMask;
		}

		public byte[] next()
			throws IOException
		{
			while (_currentNodeID <= _maxNodeID) {
				if (_currentNode == null) {
					// Read first node
					_currentNodeID = 1;
					_currentNode = _readNode(_currentNodeID);
					_currentIdx = 0;
				}

				while (_currentIdx < _currentNode.getValueCount()) {
					byte[] value = _currentNode.getValue(_currentIdx++);

					if (_searchKey == null || ByteArrayUtil.matchesPattern(value, _searchMask, _searchKey)) {
						// Found a matches value
						return value;
					}
				}

				_currentNode.release();

				_currentNodeID++;
				_currentNode = (_currentNodeID <= _maxNodeID) ? _readNode(_currentNodeID) : null;
				_currentIdx = 0;
			}

			return null;
		}

		public void close()
			throws IOException
		{
			if (_currentNode != null) {
				_currentNodeID = _maxNodeID + 1;

				_currentNode.release();
				_currentNode = null;
			}
		}
	}

/*--------------------------+
| Inner class RangeIterator |
+--------------------------*/

	private class RangeIterator implements BTreeIterator {

		private byte[] _searchKey;
		private byte[] _searchMask;

		private byte[] _minValue;
		private byte[] _maxValue;

		private boolean _started;

		private Node _currentNode;
		private int _currentIdx;

		public RangeIterator(byte[] searchKey, byte[] searchMask, byte[] minValue, byte[] maxValue) {
			_searchKey = searchKey;
			_searchMask = searchMask;
			_minValue = minValue;
			_maxValue = maxValue;
			_started = false;
		}

		public byte[] next()
			throws IOException
		{
			if (!_started) {
				_started = true;
				_findMinimum();
			}

			byte[] value = _findNext(false);
			while (value != null) {
				if (_maxValue != null && _comparator.compareBTreeValues(_maxValue, value, 0, value.length) < 0) {
					// Reached maximum value, stop iterating
					while (_currentNode != null) {
						Node parentNode = _currentNode.getParentNode();
						_currentNode.release();
						_currentNode = parentNode;
					}
					value = null;
					break;
				}
				else if (_searchKey != null && !ByteArrayUtil.matchesPattern(value, _searchMask, _searchKey)) {
					// Value doesn't match search key/mask
					value = _findNext(false);
					continue;
				}
				else {
					// Matching value found
					break;
				}
			}

			return value;
		}

		private void _findMinimum()
			throws IOException
		{
			if (_rootNodeID == 0) {
				// Empty BTree
				return;
			}

			_currentNode = _readNode(_rootNodeID);

			// Search first value >= _minValue, or the left-most value in case _minValue is null
			while (true) {
				if (_minValue != null) {
					_currentIdx = _currentNode.search(_minValue);

					if (_currentIdx >= 0) {
						// Found exact match with minimum value
						break;
					}
					else {
						// _currentIdx indicates the first value larger than the minimum value
						_currentIdx = -_currentIdx - 1;
					}
				}

				if (_currentNode.isLeaf()) {
					break;
				}
				else {
					_currentNode = _currentNode.getChildNode(_currentIdx);
					_currentIdx = 0;
				}
			}
		}

		private byte[] _findNext(boolean returnedFromRecursion)
			throws IOException
		{
			if (_currentNode == null) {
				return null;
			}

			if (returnedFromRecursion || _currentNode.isLeaf()) {
				if (_currentIdx >= _currentNode.getValueCount()) {
					// No more values in this node, continue with parent node
					Node parentNode = _currentNode.getParentNode();
					_currentIdx = _currentNode.getIndexInParent();
					_currentNode.release();
					_currentNode = parentNode;
					return _findNext(true);
				}
				else {
					return _currentNode.getValue(_currentIdx++);
				}
			}
			else {
				_currentNode = _currentNode.getChildNode(_currentIdx);
				_currentIdx = 0;
				return _findNext(false);
			}
		}

		public void close()
			throws IOException
		{
			if (_currentNode != null) {
				_currentNode.release();
				_currentNode = null;
			}
		}
	}

/*-------------+
| Test methods |
+-------------*/

	public static void main(String[] args)
		throws Exception
	{
		System.out.println("Running BTree test...");
		if (args.length > 1) {
			runPerformanceTest(args);
		}
		else {
			runDebugTest(args);
		}
		System.out.println("Done.");
	}

	public static void runPerformanceTest(String[] args)
		throws Exception
	{
		File dataFile = new File(args[0]);
		int valueCount = Integer.parseInt(args[1]);
		BTreeValueComparator comparator = new DefaultBTreeValueComparator();
		BTree btree = new BTree(dataFile, 501, 13, comparator);

		java.util.Random random = new java.util.Random(0L);
		byte[] value = new byte[13];

		long startTime = System.currentTimeMillis();
		for (int i = 1; i <= valueCount; i++) {
			random.nextBytes(value);
			btree.insert(value);
			if (i % 50000 == 0) {
				System.out.println("Inserted " + i + " values in " + (System.currentTimeMillis()-startTime) + " ms");
			}
		}

		System.out.println("Iterating over all values in sequential order...");
		startTime = System.currentTimeMillis();
		BTreeIterator iter = btree.iterateAll();
		value = iter.next();
		int count = 0;
		while (value != null) {
			count++;
			value = iter.next();
		}
		System.out.println("Iteration over " + count + " items finished in " + (System.currentTimeMillis()-startTime) + " ms");
	}

	public static void runDebugTest(String[] args)
		throws Exception
	{
		File dataFile = new File(args[0]);
		BTree btree = new BTree(dataFile, 28, 1);

		btree.print(System.out);

/*
		System.out.println("Adding values...");
		btree.startTransaction();
		btree.insert("C".getBytes());
		btree.insert("N".getBytes());
		btree.insert("G".getBytes());
		btree.insert("A".getBytes());
		btree.insert("H".getBytes());
		btree.insert("E".getBytes());
		btree.insert("K".getBytes());
		btree.insert("Q".getBytes());
		btree.insert("M".getBytes());
		btree.insert("F".getBytes());
		btree.insert("W".getBytes());
		btree.insert("L".getBytes());
		btree.insert("T".getBytes());
		btree.insert("Z".getBytes());
		btree.insert("D".getBytes());
		btree.insert("P".getBytes());
		btree.insert("R".getBytes());
		btree.insert("X".getBytes());
		btree.insert("Y".getBytes());
		btree.insert("S".getBytes());
		btree.commitTransaction();
		btree.print(System.out);

		System.out.println("Removing values...");

		System.out.println("Removing H...");
		btree.remove("H".getBytes());
		btree.commitTransaction();
		btree.print(System.out);

		System.out.println("Removing T...");
		btree.remove("T".getBytes());
		btree.commitTransaction();
		btree.print(System.out);

		System.out.println("Removing R...");
		btree.remove("R".getBytes());
		btree.commitTransaction();
		btree.print(System.out);

		System.out.println("Removing E...");
		btree.remove("E".getBytes());
		btree.commitTransaction();
		btree.print(System.out);

		System.out.println("Values from I to U:");
		BTreeIterator iter = btree.iterateRange("I".getBytes(), "V".getBytes());
		byte[] value = iter.next();
		while (value != null) {
			System.out.print(new String(value) + " ");
			value = iter.next();
		}
		System.out.println();
		*/
	}

	public void print(PrintStream out)
		throws IOException
	{
		out.println("---contents of BTree file---");
		out.println("Stored parameters:");
		out.println("block size   = " + _blockSize);
		out.println("value size   = " + _valueSize);
		out.println("root node ID = " + _rootNodeID);
		out.println();
		out.println("Derived parameters:");
		out.println("slot size       = " + _slotSize);
		out.println("branch factor   = " + _branchFactor);
		out.println("min value count = " + _minValueCount);
		out.println("node size       = " + _nodeSize);
		out.println("max node ID     = " + _maxNodeID);
		out.println();

		ByteBuffer buf = ByteBuffer.allocate(_nodeSize);
		for (long offset = _blockSize; offset < _fileChannel.size(); offset += _blockSize) {
			_fileChannel.read(buf, offset);
			buf.rewind();

			int nodeID = _offset2nodeID(offset);
			int count = buf.getInt();
			out.print("node " + nodeID + ": ");
			out.print("count="+count+ " ");

			byte[] value = new byte[_valueSize];

			for (int i = 0; i < count; i++) {
				// node ID
				out.print(buf.getInt());

				// value
				buf.get(value);
				out.print("["+ByteArrayUtil.toHexString(value)+"]");
				//out.print("["+new String(value)+"]");
			}

			// last node ID
			out.println(buf.getInt());

			buf.clear();
		}
		out.println("---end of BTree file---");
	}
}