org.openrdf.sesame.sailimpl.nativerdf.btree
Class BTree

java.lang.Object
  org.openrdf.sesame.sailimpl.nativerdf.btree.BTree

public class BTree

extends Object

Implementation of an on-disk B-Tree using the java.nio classes that are available in JDK 1.4 and newer. Documentation about B-Trees can be found on-line at the following URLs:

• http://cis.stvincent.edu/swd/btree/btree.html
,
• http://bluerwhite.org/btree/
, and
• http://semaphorecorp.com/btp/algo.html
.

The first reference was used to implement this class.

TODO: clean up code, reuse discarded nodes

Version:

$Revision: 1.15.2.4 $

Author:

Arjohn Kampman

Constructor Summary

BTree(File dataFile, int blockSize, int valueSize)
Creates a new BTree that uses an instance of DefaultBTreeValueComparator to compare values.

BTree(File dataFile, int blockSize, int valueSize, BTreeValueComparator comparator)
Creates a new BTree that uses the supplied BTreeValueComparator to compare the values that are or will be stored in the B-Tree.

Method Summary

void	clear() Removes all values from the B-Tree.
void	close() Closes any opened files and release any resources used by this B-Tree.
void	commitTransaction()
byte[]	get(byte[] key) Gets the value that matches the specified key.
byte[]	insert(byte[] value) Inserts the supplied value into the B-Tree.
BTreeIterator	iterateAll() Returns an iterator that iterates over all values in this B-Tree.
BTreeIterator	iterateRange(byte[] minValue, byte[] maxValue) Returns an iterator that iterates over all values between minValue and maxValue, inclusive.
BTreeIterator	iterateValues(byte[] searchKey, byte[] searchMask) 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.
BTreeIterator	iterateValues(byte[] searchKey, byte[] searchMask, byte[] minValue, byte[] maxValue) 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.
static void	main(String[] args)
void	print(PrintStream out)
byte[]	remove(byte[] key) Removes the value that matches the specified key from the B-Tree.
static void	runDebugTest(String[] args)
static void	runPerformanceTest(String[] args)
void	startTransaction()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BTree

public BTree(File dataFile,
             int blockSize,
             int valueSize)
      throws IOException

Creates a new BTree that uses an instance of DefaultBTreeValueComparator to compare values.

Parameters:

dataFile - The file for the B-Tree.

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.

valueSize - The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.

Throws:

IOException - In case the initialization of the B-Tree file failed.

See Also:

DefaultBTreeValueComparator

BTree

public BTree(File dataFile,
             int blockSize,
             int valueSize,
             BTreeValueComparator comparator)
      throws IOException

Creates a new BTree that uses the supplied BTreeValueComparator to compare the values that are or will be stored in the B-Tree.

Parameters:

dataFile - The file for the B-Tree.

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.

valueSize - The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.

comparator - The BTreeValueComparator to use for determining whether one value is smaller, larger or equal to another.

Throws:

IOException - In case the initialization of the B-Tree file failed.

Method Detail

close

public void close()
           throws IOException

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.

Throws:

IOException

startTransaction

public void startTransaction()
                      throws IOException

Throws:

IOException

commitTransaction

public void commitTransaction()
                       throws IOException

Throws:

IOException

get

public byte[] get(byte[] key)
           throws IOException

Gets the value that matches the specified key.

Parameters:

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.

Returns:

The value matching the key, or null if no such value could be found.

Throws:

IOException

iterateAll

public BTreeIterator iterateAll()

Returns an iterator that iterates over all values in this B-Tree.

iterateRange

public BTreeIterator iterateRange(byte[] minValue,
                                  byte[] maxValue)

Returns an iterator that iterates over all values between minValue and maxValue, inclusive.

iterateValues

public BTreeIterator iterateValues(byte[] searchKey,
                                   byte[] searchMask)

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.

iterateValues

public BTreeIterator iterateValues(byte[] searchKey,
                                   byte[] searchMask,
                                   byte[] minValue,
                                   byte[] maxValue)

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.

insert

public byte[] insert(byte[] value)
              throws IOException

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.

Parameters:

value - The value to insert into the B-Tree.

Returns:

The old value that was replaced, if any.

Throws:

IOException - If an I/O error occurred.

remove

public byte[] remove(byte[] key)
              throws IOException

Removes the value that matches the specified key from the B-Tree.

Parameters:

key - A key that matches the value that should be removed from the B-Tree.

Returns:

The value that was removed from the B-Tree, or null if no matching value was found.

Throws:

IOException - If an I/O error occurred.

clear

public void clear()
           throws IOException

Removes all values from the B-Tree.

Throws:

IOException - If an I/O error occurred.

main

public static void main(String[] args)
                 throws Exception

Throws:

Exception

runPerformanceTest

public static void runPerformanceTest(String[] args)
                               throws Exception

Throws:

Exception

runDebugTest

public static void runDebugTest(String[] args)
                         throws Exception

Throws:

Exception

print

public void print(PrintStream out)
           throws IOException

Throws:

IOException