org.jrdf.util.btree
Class BTree

java.lang.Object
  org.jrdf.util.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

Author:

Arjohn Kampman

Constructor Summary

BTree(File newDataFile, int newBlockSize, int newValueSize)
Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.

BTree(File newDataFile, int newBlockSize, int newValueSize, boolean newForceSync)
Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.

BTree(File newDataFile, int newBlockSize, int newValueSize, RecordComparator newComparator)
Creates a new BTree that uses the supplied RecordComparator to compare the values that are or will be stored in the B-Tree.

BTree(File newDataFile, int newBlockSize, int newValueSize, RecordComparator newComparator, boolean newForceSync)
Creates a new BTree that uses the supplied RecordComparator 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.
byte[]	get(byte[] key) Gets the value that matches the specified key.
File	getFile() Gets the file that this BTree operates on.
long	getValueCountEstimate() Returns an estimate for the number of values stored in this BTree.
byte[]	insert(byte[] value) Inserts the supplied value into the B-Tree.
RecordIterator	iterateAll() Returns an iterator that iterates over all values in this B-Tree.
RecordIterator	iterateRange(byte[] minValue, byte[] maxValue) Returns an iterator that iterates over all values between minValue and maxValue, inclusive.
RecordIterator	iterateRangedValues(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.
RecordIterator	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.
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	sync() Writes any changes that are cached in memory to disk.

Methods inherited from class java.lang.Object

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

Constructor Detail

BTree

public BTree(File newDataFile,
             int newBlockSize,
             int newValueSize)
      throws IOException

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

Parameters:

newDataFile - The file for the B-Tree.

newBlockSize - 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.

newValueSize - 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:

DefaultRecordComparator

BTree

public BTree(File newDataFile,
             int newBlockSize,
             int newValueSize,
             boolean newForceSync)
      throws IOException

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

Parameters:

newDataFile - The file for the B-Tree.

newBlockSize - 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.

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

newForceSync - Flag indicating whether updates should be synced to disk forcefully by calling FileChannel.force(boolean). This may have a severe impact on write performance.

Throws:

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

See Also:

DefaultRecordComparator

BTree

public BTree(File newDataFile,
             int newBlockSize,
             int newValueSize,
             RecordComparator newComparator)
      throws IOException

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

Parameters:

newDataFile - The file for the B-Tree.

newBlockSize - 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.

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

newComparator - The RecordComparator 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.

BTree

public BTree(File newDataFile,
             int newBlockSize,
             int newValueSize,
             RecordComparator newComparator,
             boolean newForceSync)
      throws IOException

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

Parameters:

newDataFile - The file for the B-Tree.

newBlockSize - 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.

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

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

newForceSync - Flag indicating whether updates should be synced to disk forcefully by calling FileChannel.force(boolean). This may have a severe impact on write performance.

Throws:

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

Method Detail

getFile

public File getFile()

Gets the file that this BTree operates on.

close

public void close()
           throws IOException

Closes any opened files and release any resources used by this B-Tree. Any pending changes will be synchronized to disk before closing. Once the B-Tree has been closes, it can no longer be used.

Throws:

IOException

sync

public void sync()
          throws IOException

Writes any changes that are cached in memory to disk.

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 RecordComparator of this BTree is concerned.

Returns:

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

Throws:

IOException

iterateAll

public RecordIterator iterateAll()

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

iterateRange

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

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

iterateValues

public RecordIterator 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.

iterateRangedValues

public RecordIterator iterateRangedValues(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.

getValueCountEstimate

public long getValueCountEstimate()
                           throws IOException

Returns an estimate for the number of values stored in this BTree.

Throws:

IOException

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