btree.java

这是外国一个开源推理机

				}
			}

			rootNode.release();
		}

		return result;
	}

	/**
	 * Removes the value that matches the specified key from the tree starting
	 * at the specified node and returns the removed value.
	 *
	 * @param key A key that matches the value that should be removed from the B-Tree.
	 * @param node The root of the (sub) tree.
	 * @return The value that was removed from the B-Tree, or <tt>null</tt> if no
	 * matching value was found.
	 * @exception IOException If an I/O error occurred.
	 **/
	private byte[] _removeFromTree(byte[] key, Node node)
		throws IOException
	{
		byte[] value = null;

		// Search key
		int valueIdx = node.search(key);

		if (valueIdx >= 0) {
			// Found matching value in this node, remove it
			if (node.isLeaf()) {
				value = node.removeValueRight(valueIdx);
			}
			else {
				// Replace the matching value with the smallest value from the right child node
				value = node.getValue(valueIdx);

				Node rightChildNode = node.getChildNode(valueIdx + 1);
				byte[] smallestValue = _removeSmallestValueFromTree(rightChildNode);

				node.setValue(valueIdx, smallestValue);

				_balanceChildNode(node, rightChildNode, valueIdx + 1);

				rightChildNode.release();
			}
		}
		else if (!node.isLeaf()) {
			// Recurse into left child node
			valueIdx = -valueIdx - 1;
			Node childNode = node.getChildNode(valueIdx);
			value = _removeFromTree(key, childNode);

			_balanceChildNode(node, childNode, valueIdx);

			childNode.release();
		}

		return value;
	}

	/**
	 * Removes the smallest value from the tree starting at the specified node
	 * and returns the removed value.
	 *
	 * @param node The root of the (sub) tree.
	 * @return The value that was removed from the B-Tree, or <tt>null</tt> if
	 * the supplied node is empty.
	 * @exception IOException If an I/O error occurred.
	 **/
	private byte[] _removeSmallestValueFromTree(Node node)
		throws IOException
	{
		byte[] value = null;

		if (node.isLeaf() && !node.isEmpty()) {
			value = node.removeValueLeft(0);
		}
		else {
			// Recurse into left-most child node
			Node childNode = node.getChildNode(0);
			value = _removeSmallestValueFromTree(childNode);
			_balanceChildNode(node, childNode, 0);
			childNode.release();
		}

		return value;
	}

	private void _balanceChildNode(Node parentNode, Node childNode, int childIdx)
		throws IOException
	{
		if (childNode.getValueCount() < _minValueCount) {
			// Child node contains too few values, try to borrow one from its right sibling
			Node rightSibling = (childIdx < parentNode.getValueCount()) ? parentNode.getChildNode(childIdx+1) : null;

			if (rightSibling != null && rightSibling.getValueCount() > _minValueCount) {
				// Right sibling has enough values to give one up
				childNode.insertValueNodeIDPair(childNode.getValueCount(),
						parentNode.getValue(childIdx), rightSibling.getChildNodeID(0));
				parentNode.setValue(childIdx, rightSibling.removeValueLeft(0));
			}
			else {
				// Right sibling does not have enough values to give one up, try its left sibling
				Node leftSibling = (childIdx > 0) ? parentNode.getChildNode(childIdx - 1) : null;

				if (leftSibling != null && leftSibling.getValueCount() > _minValueCount) {
					// Left sibling has enough values to give one up
					childNode.insertNodeIDValuePair(0,
							leftSibling.getChildNodeID(leftSibling.getValueCount()),
							parentNode.getValue(childIdx-1));
					parentNode.setValue(childIdx-1, leftSibling.removeValueRight(leftSibling.getValueCount()-1));
				}
				else {
					// Both siblings contain the minimum amount of values,
					// merge the child node with its left or right sibling
					if (leftSibling != null) {
						leftSibling.mergeWithRightSibling(parentNode.removeValueRight(childIdx - 1), childNode);
					}
					else {
						childNode.mergeWithRightSibling(parentNode.removeValueRight(childIdx), rightSibling);
					}
				}

				if (leftSibling != null) {
					leftSibling.release();
				}
			}

			if (rightSibling != null) {
				rightSibling.release();
			}
		}
	}

	/**
	 * Removes all values from the B-Tree.
	 *
	 * @exception IOException If an I/O error occurred.
	 **/
	public void clear()
		throws IOException
	{
		synchronized (_nodesInUse) {
			_nodesInUse.clear();
		}
		synchronized (_mruNodes) {
			_mruNodes.clear();
		}
		_fileChannel.truncate(HEADER_LENGTH);

		_rootNodeID = 0;
		_maxNodeID = 0;
		_writeFileHeader();
	}

	private Node _createNewNode()
		throws IOException
	{
		Node node = new Node(++_maxNodeID);
		node.use();
		synchronized (_nodesInUse) {
			_nodesInUse.add(node);
		}
		return node;
	}

	private Node _readNode(int id)
		throws IOException
	{
		// Check _nodesInUse list
		synchronized (_nodesInUse) {
			Iterator iter = _nodesInUse.iterator();
			while (iter.hasNext()) {
				Node node = (Node)iter.next();

				if (node.getID() == id) {
					node.use();
					return node;
				}
			}

			// Check _mruNodes list
			synchronized (_mruNodes) {
				iter = _mruNodes.iterator();
				while (iter.hasNext()) {
					Node node = (Node)iter.next();

					if (node.getID() == id) {
						iter.remove();
						_nodesInUse.add(node);

						node.use();
						return node;
					}
				}
			}

			// Read node from disk
			Node node = new Node(id);
			node.read();
			_nodesInUse.add(node);

			node.use();
			return node;
		}
	}

	private void _releaseNode(Node node)
		throws IOException
	{
		synchronized (_nodesInUse) {
			_nodesInUse.remove(node);

			synchronized (_mruNodes) {
				if (_mruNodes.size() >= MRU_CACHE_SIZE) {
					// Remove least recently used node
					Node lruNode = (Node)_mruNodes.removeLast();
					if (lruNode.dataChanged()) {
						lruNode.write();
					}
				}
				_mruNodes.addFirst(node);
			}
		}
	}

	private long _nodeID2offset(int id) {
		return (long)_blockSize * id;
	}

	private int _offset2nodeID(long offset) {
		return (int)(offset / _blockSize);
	}

	private void _writeFileHeader()
		throws IOException
	{
		ByteBuffer buf = ByteBuffer.allocate(HEADER_LENGTH);
		buf.putInt(FILE_FORMAT_VERSION); // for backwards compatibility in future versions
		buf.putInt(_blockSize);
		buf.putInt(_valueSize);
		buf.putInt(_rootNodeID);

		buf.rewind();

		_fileChannel.write(buf, 0L);
	}

	private void _readFileHeader()
		throws IOException
	{
		ByteBuffer buf = ByteBuffer.allocate(HEADER_LENGTH);
		_fileChannel.read(buf, 0L);

		buf.rewind();

		int fileFormatVersion = buf.getInt(); // for backwards compatibility in future versions
		_blockSize = buf.getInt();
		_valueSize = buf.getInt();
		_rootNodeID = buf.getInt();
	}

/*-----------------+
| Inner class Node |
+-----------------*/

	private class Node {
		
		/** This node's ID. **/
		private int _id;

		/** The offset of this node in the file. **/
		private long _offset;

		/** This node's data. **/
		private byte[] _data;

		/** The number of values containined in this node. **/
		private int _valueCount;

		/** The number of objects currently 'using' this node. **/
		private int _usageCount;

		/** Flag indicating whether the contents of _data has changed. **/
		private boolean _dataChanged;

		/** The node's parent, if any. **/
		private Node _parent;

		/** The index of this node in its parent node. **/
		private int _indexInParent;

		public Node(int id) {
			_id = id;
			_offset = _nodeID2offset(_id);
			_valueCount = 0;
			_usageCount = 0;

			// Allocate enough room to store one more value and node ID;
			// this greatly simplifies the algorithm for splitting a node.
			_data = new byte[_nodeSize + _slotSize];
		}

		public int getID() {
			return _id;
		}

		public boolean isLeaf() {
			return ByteArrayUtil.getInt(_data, 4) == 0;
		}

		public void use() {
			_usageCount++;
		}

		public void release()
			throws IOException
		{
			_usageCount--;

			if (_usageCount == 0) {
				_releaseNode(this);
			}
		}

		public int getUsageCount() {
			return _usageCount;
		}

		public boolean dataChanged() {
			return _dataChanged;
		}

		public int getValueCount() {
			return _valueCount;
		}

		public boolean isEmpty() {
			return _valueCount == 0;
		}

		public boolean isFull() {
			return _valueCount == _branchFactor - 1;
		}

		public byte[] getValue(int valueIdx) {
			return ByteArrayUtil.get(_data, _valueIdx2offset(valueIdx), _valueSize);
		}

		public void setValue(int valueIdx, byte[] value) {
			ByteArrayUtil.put(value, _data, _valueIdx2offset(valueIdx));
			_dataChanged = true;
		}

		/**
		 * Removes the value that can be found at the specified valueIdx and the
		 * node ID directly to the right of it.
		 *
		 * @param valueIdx A legal value index.
		 * @return The value that was removed.
		 * @see #removeValueLeft
		 **/
		public byte[] removeValueRight(int valueIdx) {
			byte[] value = getValue(valueIdx);

			int endOffset = _valueIdx2offset(_valueCount);

			if (valueIdx < _valueCount - 1) {
				// Shift the rest of the data one slot to the left
				_shiftData(_valueIdx2offset(valueIdx+1), endOffset, -_slotSize);
			}

			// Clear last slot
			_clearData(endOffset - _slotSize, endOffset);

			_setValueCount(--_valueCount);

			_dataChanged = true;

			return value;
		}

		/**
		 * Removes the value that can be found at the specified valueIdx and the
		 * node ID directly to the left of it.
		 *
		 * @param valueIdx A legal value index.
		 * @return The value that was removed.
		 * @see #removeValueRight
		 **/
		public byte[] removeValueLeft(int valueIdx) {
			byte[] value = getValue(valueIdx);

			int endOffset = _valueIdx2offset(_valueCount);

			// Move the rest of the data one slot to the left
			_shiftData(_nodeIdx2offset(valueIdx+1), endOffset, -_slotSize);

			// Clear last slot
			_clearData(endOffset - _slotSize, endOffset);

			_setValueCount(--_valueCount);

			_dataChanged = true;

			return value;
		}

		public int getChildNodeID(int nodeIdx) {
			return ByteArrayUtil.getInt(_data, _nodeIdx2offset(nodeIdx));
		}

		public void setChildNodeID(int nodeIdx, int nodeID) {
			ByteArrayUtil.putInt(nodeID, _data, _nodeIdx2offset(nodeIdx));
			_dataChanged = true;
		}

		public Node getChildNode(int nodeIdx)
			throws IOException
		{
			int childNodeID = getChildNodeID(nodeIdx);
			Node childNode = _readNode(childNodeID);
			childNode._parent = this;
			childNode._indexInParent = nodeIdx;
			return childNode;
		}

		public Node getParentNode() {
			return _parent;
		}
		
		public int getIndexInParent() {
			return _indexInParent;
		}

		public void clearParentInfo() {
			_parent = null;
			_indexInParent = -1;
		}

		/**
		 * Searches the node for values that match the specified key and returns
		 * its index. If no such value can be found, the index of the first
		 * value that is larger is returned as a negative value by multiplying
		 * the index with -1 and substracting 1 (result = -index - 1). The index
		 * can be calculated from this negative value using the same function,
		 * i.e.: index = -result - 1.
		 **/
		public int search(byte[] key) {
			int low = 0;
			int high = _valueCount - 1;

			while (low <= high) {
				int mid = (low + high) >> 1;
				int diff = _comparator.compareBTreeValues(key, _data, _valueIdx2offset(mid), _valueSize);

				if (diff < 0) {
					// key smaller than middle value
					high = mid - 1;
				}
				else if (diff > 0) {
					// key larger than middle value
					low = mid + 1;
				}
				else {
					// key equal to middle value
					return mid;
				}
			}
			return -low - 1;
		}

		public void insertValueNodeIDPair(int valueIdx, byte[] value, int nodeID) {
			int offset = _valueIdx2offset(valueIdx);

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

			// Insert the new value-nodeID pair
			ByteArrayUtil.put(value, _data, offset);
			ByteArrayUtil.putInt(nodeID, _data, offset + _valueSize);

			// Raise the value count