org.axiondb.util

Class ObjectBTree

public class ObjectBTree extends BaseBTree

A B-Tree for Objects, based on the implementation described in "Introduction to Algorithms" by Cormen, Leiserson and Rivest (CLR).

Version: $Revision: 1.53 $ $Date: 2005/12/20 18:32:42 $

Author: Chuck Burdick Dave Pekarek Krohn Rodney Waldhoff Charles Ye Ahimanikya Satapathy

Constructor Summary
ObjectBTree(File idxDir, String idxName, int minimizationFactor, Comparator comp)
Create or load a new root node.
protected ObjectBTree(BTreeMetaData meta, Comparator comp)
Create a new, non-root node.
protected ObjectBTree(BTreeMetaData meta, Comparator comp, int fileId)
Create a non-root node by reading it from disk.
Method Summary
protected voidaddKeyValuePair(Object key, int value, boolean setDirty)
voidclearData()
Clear my keys, values, and file ids.
protected ObjectBTreecreateNode(BTreeMetaData meta, Comparator comp)
Create a new node.
voiddelete(Object key, int rowid)
Optimized: Delete an arbitrary instance of the specified key and the specifiied rowid
Integerget(Object key)
Find some occurance of the given key.
IntListIteratorgetAll(Object key)
Obtain an iterator over all values associated with the given key.
IntListIteratorgetAllExcludingNull()
Obtain an iterator over all values excluding null key values
protected voidgetAllExcludingNull(IntListIteratorChain chain)
IntListIteratorgetAllFrom(Object key)
Obtain an iterator over all values greater than or equal to the given key.
IntListIteratorgetAllTo(Object key)
Obtain an iterator over all values strictly less than the given key.
protected ObjectgetKey(int index)
Obtain the key stored at the specified index.
protected ObjectgetNullKey()
IntListIteratorChaininorderIterator()
voidinsert(Object key, int value)
Insert the given key/value pair.
protected ObjectBTreeloadNode(BTreeMetaData meta, Comparator comp, int fileId)
Read the node with the specified fileId from disk.
protected voidread()
Reads in the node.
voidreplaceId(Object key, int oldRowId, int newRowId)
Replace any occurance of oldRowId associated with the given key with newRowId.
voidsave()
Save this tree and all of its children.
intsize()
Returns the number of keys I currently contain.
StringtoString()
Obtain a String representation of this node, suitable for debugging.
voidtruncate()
protected voidwrite()
Writes the node file out.

Constructor Detail

ObjectBTree

public ObjectBTree(File idxDir, String idxName, int minimizationFactor, Comparator comp)
Create or load a new root node.

ObjectBTree

protected ObjectBTree(BTreeMetaData meta, Comparator comp)
Create a new, non-root node.

ObjectBTree

protected ObjectBTree(BTreeMetaData meta, Comparator comp, int fileId)
Create a non-root node by reading it from disk.

Method Detail

addKeyValuePair

protected final void addKeyValuePair(Object key, int value, boolean setDirty)

clearData

public final void clearData()
Clear my keys, values, and file ids. Flags me as dirty.

createNode

protected ObjectBTree createNode(BTreeMetaData meta, Comparator comp)
Create a new node.

delete

public final void delete(Object key, int rowid)
Optimized: Delete an arbitrary instance of the specified key and the specifiied rowid

get

public final Integer get(Object key)
Find some occurance of the given key.

getAll

public final IntListIterator getAll(Object key)
Obtain an iterator over all values associated with the given key.

getAllExcludingNull

public final IntListIterator getAllExcludingNull()
Obtain an iterator over all values excluding null key values

getAllExcludingNull

protected void getAllExcludingNull(IntListIteratorChain chain)

getAllFrom

public final IntListIterator getAllFrom(Object key)
Obtain an iterator over all values greater than or equal to the given key.

getAllTo

public final IntListIterator getAllTo(Object key)
Obtain an iterator over all values strictly less than the given key.

getKey

protected final Object getKey(int index)
Obtain the key stored at the specified index.

getNullKey

protected Object getNullKey()

inorderIterator

public IntListIteratorChain inorderIterator()

insert

public final void insert(Object key, int value)
Insert the given key/value pair.

loadNode

protected ObjectBTree loadNode(BTreeMetaData meta, Comparator comp, int fileId)
Read the node with the specified fileId from disk.

read

protected void read()
Reads in the node. This doesn't read in the entire subtree, which happens incrementally as files are needed.

replaceId

public final void replaceId(Object key, int oldRowId, int newRowId)
Replace any occurance of oldRowId associated with the given key with newRowId. It is assumed oldId occurs at most once in the tree.

save

public final void save()

Deprecated: See ObjectBTree

Save this tree and all of its children.

size

public final int size()
Returns the number of keys I currently contain. Note that by construction, this will be at least minimizationFactor-1 and at most 2*minimizationFactor-1 for all nodes except the root (which may have fewer than minimizationFactor -1 keys).

toString

public final String toString()
Obtain a String representation of this node, suitable for debugging.

truncate

public void truncate()

write

protected void write()
Writes the node file out. This is differentiated from save in that it doesn't save the entire tree or the counter file.