btree.java

这是外国一个开源推理机

/*  Sesame - Storage and Querying architecture for RDF and RDF Schema
 *  Copyright (C) 2001-2005 Aduna
 *
 *  Contact: 
 *  	Aduna
 *  	Prinses Julianaplein 14 b
 *  	3817 CS Amersfoort
 *  	The Netherlands
 *  	tel. [phone]
 *  	fax. [phone]
 *
 *  	http://aduna.biz/
 *  	http://www.openrdf.org/
 *  
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package org.openrdf.sesame.sailimpl.nativerdf.btree;

import java.io.File;
import java.io.IOException;
import java.io.PrintStream;
import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

import org.openrdf.util.ByteArrayUtil;

/**
 * Implementation of an on-disk B-Tree using the <tt>java.nio</tt> classes that
 * are available in JDK 1.4 and newer. Documentation about B-Trees can be found
 * on-line at the following URLs:
 * <ul>
 * <li>http://cis.stvincent.edu/swd/btree/btree.html</li>,
 * <li>http://bluerwhite.org/btree/</li>, and
 * <li>http://semaphorecorp.com/btp/algo.html</li>.
 * </ul>
 * The first reference was used to implement this class.
 * <p>
 * TODO: clean up code, reuse discarded nodes
 *
 * @version $Revision: 1.15 $
 * @author Arjohn Kampman
 **/
public class BTree {

/*----------+
| Constants |
+----------*/

	private static final int FILE_FORMAT_VERSION = 1;
	private static final int HEADER_LENGTH = 16;
	private static final int MRU_CACHE_SIZE = 8;

/*----------+
| Variables |
+----------*/

	private File _file;
	private RandomAccessFile _raf;
	private FileChannel _fileChannel;

	private BTreeValueComparator _comparator;

	// Stored or specified properties:
	private int _blockSize;
	private int _valueSize;
	private int _rootNodeID;
	private int _maxNodeID;

	// Derived properties:
	private int _slotSize; // The size of a slot storing a node ID and a value
	private int _branchFactor; // The maximum number of outgoing branches for a node
	private int _minValueCount; // The minimum number of values for a node (except for the root)
	private int _nodeSize; // The size of a node in bytes

	/** List containing nodes that are currently "in use". **/
	private LinkedList _nodesInUse;

	/** List containing the most recently used nodes but that are no longer used anymore. **/
	private LinkedList _mruNodes;

/*-------------+
| Constructors |
+-------------*/

	/**
	 * Creates a new BTree that uses an instance of
	 * <tt>DefaultBTreeValueComparator</tt> to compare values.
	 *
	 * @param dataFile The file for the B-Tree.
	 * @param blockSize The size (in bytes) of a file block for a single node.
	 * Ideally, the size specified is the size of a block in the used file
	 * system.
	 * @param valueSize The size (in bytes) of the fixed-length values that are
	 * or will be stored in the B-Tree.
	 * @exception IOException In case the initialization of the B-Tree file
	 * failed.
	 *
	 * @see DefaultBTreeValueComparator
	 **/
	public BTree(File dataFile, int blockSize, int valueSize)
		throws IOException
	{
		this(dataFile, blockSize, valueSize, new DefaultBTreeValueComparator());
	}

	/**
	 * Creates a new BTree that uses the supplied <tt>BTreeValueComparator</tt>
	 * to compare the values that are or will be stored in the B-Tree.
	 *
	 * @param dataFile The file for the B-Tree.
	 * @param blockSize The size (in bytes) of a file block for a single node.
	 * Ideally, the size specified is the size of a block in the used file
	 * system.
	 * @param valueSize The size (in bytes) of the fixed-length values that are
	 * or will be stored in the B-Tree.
	 * @param comparator The <tt>BTreeValueComparator</tt> to use for
	 * determining whether one value is smaller, larger or equal to another.
	 * @exception IOException In case the initialization of the B-Tree file
	 * failed.
	 **/
	public BTree(File dataFile, int blockSize, int valueSize, BTreeValueComparator comparator)
		throws IOException
	{
		if (blockSize < HEADER_LENGTH) {
			throw new IllegalArgumentException("block size must be at least " + HEADER_LENGTH + " bytes");
		}
		if (valueSize <= 0) {
			throw new IllegalArgumentException("value size must be larger than 0");
		}
		if (blockSize < 3 * valueSize + 20) {
			throw new IllegalArgumentException("block size to small; must at least be able to store three values");
		}

		_file = dataFile;
		_comparator = comparator;

		// Make sure the file exists
		_file.createNewFile();

		_raf = new RandomAccessFile(_file, "rw");
		_fileChannel = _raf.getChannel();

		if (_fileChannel.size() == 0L) {
			// Empty file, initialize it with the specified parameters
			_blockSize = blockSize;
			_valueSize = valueSize;
			_rootNodeID = 0;
			_maxNodeID = 0;

			_writeFileHeader();
		}
		else {
			// Read parameters from file
			_readFileHeader();

			_maxNodeID = _offset2nodeID(_fileChannel.size() - _nodeSize);
		}

		// Calculate derived properties
		_slotSize = 4 + _valueSize;
		_branchFactor = 1 + (_blockSize-8) / _slotSize;
		_minValueCount = (_branchFactor-1) / 2; // bf=30 --> mvc=14; bf=29 --> mvc=14
		_nodeSize = 8 + (_branchFactor-1) * _slotSize;

		_nodesInUse = new LinkedList();
		_mruNodes = new LinkedList();

		/*
		System.out.println("blockSize="+_blockSize);
		System.out.println("valueSize="+_valueSize);
		System.out.println("slotSize="+_slotSize);
		System.out.println("branchFactor="+_branchFactor);
		System.out.println("minimum value count="+_minValueCount);
		System.out.println("nodeSize="+_nodeSize);
		*/
	}

/*--------+
| Methods |
+--------*/

	/**
	 * Closes any opened files and release any resources used by this B-Tree.
	 * Once the B-Tree has been closes, it can no longer be used.
	 **/
	public void close()
		throws IOException
	{
		synchronized (_nodesInUse) {
			_nodesInUse.clear();
		}
		synchronized (_mruNodes) {
			_mruNodes.clear();
		}

		_raf.close();

		_fileChannel = null;
		_raf = null;
		_file = null;
	}

	public void startTransaction()
		throws IOException
	{
	}

	public void commitTransaction()
		throws IOException
	{
		// Write any changed nodes that still reside in the cache to disk
		synchronized (_nodesInUse) {
			Iterator iter = _nodesInUse.iterator();
			while (iter.hasNext()) {
				Node node = (Node)iter.next();
				if (node.dataChanged()) {
					node.write();
				}
			}
		}

		synchronized (_mruNodes) {
			Iterator iter = _mruNodes.iterator();
			while (iter.hasNext()) {
				Node node = (Node)iter.next();
				if (node.dataChanged()) {
					node.write();
				}
			}
		}
	}

	/**
	 * Gets the value that matches the specified key.
	 *
	 * @param key A value that is equal to the value that should be
	 * retrieved, at least as far as the BTreeValueComparator of this
	 * BTree is concerned.
	 * @return The value matching the key, or <tt>null</tt> if no such
	 * value could be found.
	 **/
	public byte[] get(byte[] key)
		throws IOException
	{
		if (_rootNodeID == 0) {
			// Empty BTree
			return null;
		}

		Node node = _readNode(_rootNodeID);

		while (true) {
			int valueIdx = node.search(key);

			if (valueIdx >= 0) {
				// Return matching value
				byte[] result = node.getValue(valueIdx);
				node.release();
				return result;
			}
			else if (!node.isLeaf()) {
				// Returned index references the first value that is larger than
				// the key, search the child node just left of it (==same index).
				Node childNode = node.getChildNode(-valueIdx - 1);
				node.release();
				node = childNode;
			}
			else {
				// value not found
				node.release();
				return null;
			}
		}
	}

	/**
	 * Returns an iterator that iterates over all values in this B-Tree.
	 **/
	public BTreeIterator iterateAll() {
		return new SeqScanIterator(null, null);
	}

	/**
	 * Returns an iterator that iterates over all values between minValue and
	 * maxValue, inclusive.
	 **/
	public BTreeIterator iterateRange(byte[] minValue, byte[] maxValue) {
		return new RangeIterator(null, null, minValue, maxValue);
	}

	/**
	 * Returns an iterator that iterates over all values and returns the values
	 * that match the supplied searchKey after searchMask has been applied to
	 * the value.
	 **/
	public BTreeIterator iterateValues(byte[] searchKey, byte[] searchMask) {
		return new SeqScanIterator(searchKey, searchMask);
	}

	/**
	 * Returns an iterator that iterates over all values between minValue and
	 * maxValue (inclusive) and returns the values that match the supplied
	 * searchKey after searchMask has been applied to the value.
	 **/
	public BTreeIterator iterateValues(byte[] searchKey, byte[] searchMask, byte[] minValue, byte[] maxValue) {
		return new RangeIterator(searchKey, searchMask, minValue, maxValue);
	}

	/**
	 * Inserts the supplied value into the B-Tree. In case an equal value is
	 * already present in the B-Tree this value is overwritten with the new
	 * value and the old value is returned by this method.
	 *
	 * @param value The value to insert into the B-Tree.
	 * @return The old value that was replaced, if any.
	 * @exception IOException If an I/O error occurred.
	 **/
	public byte[] insert(byte[] value)
		throws IOException
	{
		Node rootNode = null;

		if (_rootNodeID == 0) {
			// Empty B-Tree, create a root node
			rootNode = _createNewNode();
			_rootNodeID = rootNode.getID();
			_writeFileHeader();
		}
		else {
			rootNode = _readNode(_rootNodeID);
		}

		InsertResult insertResult = _insertInTree(value, 0, rootNode);

		if (insertResult.overflowValue != null) {
			// Root node overflowed, create a new root node and insert overflow value-nodeID pair in it
			Node newRootNode = _createNewNode();
			newRootNode.setChildNodeID(0, rootNode.getID());
			newRootNode.insertValueNodeIDPair(0, insertResult.overflowValue, insertResult.overflowNodeID);

			_rootNodeID = newRootNode.getID();
			_writeFileHeader();
			newRootNode.release();
		}

		rootNode.release();

		return insertResult.oldValue;
	}

	private InsertResult _insertInTree(byte[] value, int nodeID, Node node)
		throws IOException
	{
		InsertResult insertResult = null;

		// Search value in node
		int valueIdx = node.search(value);

		if (valueIdx >= 0) {
			// Found an equal value, replace it
			insertResult = new InsertResult();
			insertResult.oldValue = node.getValue(valueIdx);

			// Do not replace the value if it's identical to the old
			// value to prevent possibly unnecessary disk writes
			if (!Arrays.equals(value, insertResult.oldValue)) {
				node.setValue(valueIdx, value);
			}
		}
		else {
			// valueIdx references the first value that is larger than the key
			valueIdx = -valueIdx - 1;

			if (node.isLeaf()) {
				// Leaf node, insert value here
				insertResult = _insertInNode(value, nodeID, valueIdx, node);
			}
			else {
				// Not a leaf node, insert value in the child node just left of
				// the found value (==same index)
				Node childNode = node.getChildNode(valueIdx);
				insertResult = _insertInTree(value, nodeID, childNode);
				childNode.release();

				if (insertResult.overflowValue != null) {
					// Child node overflowed, insert overflow in this node
					byte[] oldValue = insertResult.oldValue;
					insertResult = _insertInNode(insertResult.overflowValue, insertResult.overflowNodeID, valueIdx, node);
					insertResult.oldValue = oldValue;
				}
			}
		}

		return insertResult;
	}

	private InsertResult _insertInNode(byte[] value, int nodeID, int valueIdx, Node node)
		throws IOException
	{
		InsertResult insertResult = new InsertResult();

		if (node.isFull()) {
			// Leaf node is full and needs to be split
			Node newNode = _createNewNode();
			insertResult.overflowValue = node.splitAndInsert(value, nodeID, valueIdx, newNode);
			insertResult.overflowNodeID = newNode.getID();
			newNode.release();
		}
		else {
			// Leaf node is not full, simply add the value to it
			node.insertValueNodeIDPair(valueIdx, value, nodeID);
		}

		return insertResult;
	}

	/**
	 * struct-like class used to represent the result of an insert operation.
	 **/
	private static class InsertResult {

		/**
		 * The old value that has been replaced by the insertion of a new value.
		 **/
		byte[] oldValue = null;

		/**
		 * The value that was removed from a child node due to overflow.
		 **/
		byte[] overflowValue = null;

		/**
		 * The nodeID to the right of 'overflowValue' that was removed from a
		 * child node due to overflow.
		 **/
		int overflowNodeID = 0;
	}

	/**
	 * Removes the value that matches the specified key from the B-Tree.
	 *
	 * @param key A key that matches the value that should be removed from the B-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.
	 **/
	public byte[] remove(byte[] key)
		throws IOException
	{
		byte[] result = null;

		if (_rootNodeID != 0) {
			Node rootNode = _readNode(_rootNodeID);

			result = _removeFromTree(key, rootNode);

			if (result != null) {
				if (rootNode.isEmpty()) {
					// Collapse B-Tree one level
					Node newRootNode = rootNode.getChildNode(0);
					newRootNode.clearParentInfo();

					_rootNodeID = newRootNode.getID();
					_writeFileHeader();

					newRootNode.release();

					rootNode.setChildNodeID(0, 0);