org.axiondb.util

Class IntBTree

java.lang.Object

org.axiondb.util.IntBTree

public class IntBTree
extends java.lang.Object

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

Version:

$Revision: 1.14 $ $Date: 2005/12/20 18:32:42 $

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	IntBTree(org.axiondb.util.BTreeMetaData meta) Create a new, non-root node.
protected	IntBTree(org.axiondb.util.BTreeMetaData meta, int fileId) Create a non-root node by reading it from disk.
	IntBTree(java.io.File idxDir, java.lang.String idxName, int minimizationFactor) Create or load a new root node.

Method Summary

Modifier and Type	Method and Description
protected void	addFileId(int fileId) Add a reference to the given file id.
protected void	addFileId(int index, int fileid) Store a reference to the given file id at the specifed index.
protected void	addFileIds(org.apache.commons.collections.primitives.IntList fileIds) Add the given specified file ids.
protected void	addKeyValuePair(int key, int value, boolean setDirty)
void	clearData() Clear my keys, values, and file ids.
protected IntBTree	createNode(org.axiondb.util.BTreeMetaData meta) Create a new node.
boolean	delete(int key, int rowid) Delete an arbitrary instance of the specified key and the specified row
java.lang.Integer	get(int key) Find some occurance of the given key.
org.apache.commons.collections.primitives.IntListIterator	getAll(int key) Obtain an iterator over all values associated with the given key.
org.apache.commons.collections.primitives.IntListIterator	getAllExcludingNull() Obtain an iterator over all values excluding null key values
org.apache.commons.collections.primitives.IntListIterator	getAllFrom(int key) Obtain an iterator over all values greater than or equal to the given key.
org.apache.commons.collections.primitives.IntListIterator	getAllTo(int key) Obtain an iterator over all values strictly less than the given key.
protected org.axiondb.util.BTreeMetaData	getBTreeMetaData()
protected org.apache.commons.collections.primitives.IntList	getChildIds()
protected int	getFileId()
protected int	getFileIdForIndex(int index) Get the file id for the specified index.
protected int	getKey(int index) Obtain the key stored at the specified index.
protected int	getKeyCapacity() Return the maximum number of keys I can contain (2* minimizationFactor-1).
protected int	getMinimizationFactor()
protected int	getValue(int index)
protected org.apache.commons.collections.primitives.IntList	getValues()
IntListIteratorChain	inorderIterator()
void	insert(int key, int value) Insert the given key/value pair.
protected boolean	isFull()
protected boolean	isLeaf() Returns true iff I don't contain any child nodes.
protected boolean	isRoot() Returns true iff I am the root node.
protected IntBTree	loadNode(org.axiondb.util.BTreeMetaData meta, int fileId) Read the node with the specified fileId from disk.
protected void	read() Reads in the node.
void	replaceId(int key, int oldRowId, int newRowId) Replace any occurance of oldRowId associated with the given key with newRowId.
void	save() Deprecated. See save(File)
void	save(java.io.File dataDirectory) Saves the tree.
void	saveAfterTruncate()
protected void	saveCounterIfRoot()
protected void	setChildIds(org.apache.commons.collections.primitives.IntList childIds)
protected void	setFileId(int fileId)
protected void	setValue(int index, int val)
protected void	setValues(org.apache.commons.collections.primitives.IntList vals)
int	size() Returns the number of keys I currently contain.
protected java.lang.String	space(int n) Return a String comprised of 2*n spaces.
java.lang.String	toString() Obtain a String representation of this node, suitable for debugging.
void	truncate()
org.apache.commons.collections.primitives.IntListIterator	valueIterator()
org.apache.commons.collections.primitives.IntListIterator	valueIteratorGreaterThan(int fromkey)
org.apache.commons.collections.primitives.IntListIterator	valueIteratorGreaterThanOrEqualTo(int fromkey)
protected void	write() Writes the node file out.

Methods inherited from class java.lang.Object

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

Constructor Detail

IntBTree

public IntBTree(java.io.File idxDir,
                java.lang.String idxName,
                int minimizationFactor)
         throws java.io.IOException,
                java.lang.ClassNotFoundException

Create or load a new root node.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

IntBTree

protected IntBTree(org.axiondb.util.BTreeMetaData meta)
            throws java.io.IOException,
                   java.lang.ClassNotFoundException

Create a new, non-root node.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

IntBTree

protected IntBTree(org.axiondb.util.BTreeMetaData meta,
                   int fileId)
            throws java.io.IOException,
                   java.lang.ClassNotFoundException

Create a non-root node by reading it from disk.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

Method Detail

clearData

public final void clearData()

Clear my keys, values, and file ids. Flags me as dirty.

delete

public final boolean delete(int key,
                            int rowid)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException

Delete an arbitrary instance of the specified key and the specified row

Throws:

java.io.IOException

java.lang.ClassNotFoundException

get

public final java.lang.Integer get(int key)
                            throws java.io.IOException,
                                   java.lang.ClassNotFoundException

Find some occurance of the given key.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

getAll

public final org.apache.commons.collections.primitives.IntListIterator getAll(int key)
                                                                       throws java.io.IOException,
                                                                              java.lang.ClassNotFoundException

Obtain an iterator over all values associated with the given key.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

getAllExcludingNull

public final org.apache.commons.collections.primitives.IntListIterator getAllExcludingNull()
                                                                                    throws java.io.IOException,
                                                                                           java.lang.ClassNotFoundException

Obtain an iterator over all values excluding null key values

Throws:

java.io.IOException

java.lang.ClassNotFoundException

getAllFrom

public final org.apache.commons.collections.primitives.IntListIterator getAllFrom(int key)
                                                                           throws java.io.IOException,
                                                                                  java.lang.ClassNotFoundException

Obtain an iterator over all values greater than or equal to the given key.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

getAllTo

public final org.apache.commons.collections.primitives.IntListIterator getAllTo(int key)
                                                                         throws java.io.IOException,
                                                                                java.lang.ClassNotFoundException

Obtain an iterator over all values strictly less than the given key.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

inorderIterator

public IntListIteratorChain inorderIterator()
                                     throws java.io.IOException,
                                            java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

insert

public final void insert(int key,
                         int value)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException

Insert the given key/value pair.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

replaceId

public final void replaceId(int key,
                            int oldRowId,
                            int newRowId)
                     throws java.lang.ClassNotFoundException,
                            java.io.IOException

Replace any occurance of oldRowId associated with the given key with newRowId. It is assumed oldId occurs at most once in the tree.

Throws:

java.lang.ClassNotFoundException

java.io.IOException

save

public final void save()
                throws java.io.IOException,
                       java.lang.ClassNotFoundException

Deprecated. See save(File)

Save this tree and all of its children.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

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 java.lang.String toString()

Obtain a String representation of this node, suitable for debugging.

Overrides:

toString in class java.lang.Object

truncate

public void truncate()

See Also:

org.axiondb.util.BaseBTree#reset()

valueIterator

public org.apache.commons.collections.primitives.IntListIterator valueIterator()
                                                                        throws java.io.IOException

Throws:

java.io.IOException

valueIteratorGreaterThan

public org.apache.commons.collections.primitives.IntListIterator valueIteratorGreaterThan(int fromkey)
                                                                                   throws java.io.IOException,
                                                                                          java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

valueIteratorGreaterThanOrEqualTo

public org.apache.commons.collections.primitives.IntListIterator valueIteratorGreaterThanOrEqualTo(int fromkey)
                                                                                            throws java.io.IOException,
                                                                                                   java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

addKeyValuePair

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

createNode

protected IntBTree createNode(org.axiondb.util.BTreeMetaData meta)
                       throws java.io.IOException,
                              java.lang.ClassNotFoundException

Create a new node.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

getKey

protected final int getKey(int index)

Obtain the key stored at the specified index.

loadNode

protected IntBTree loadNode(org.axiondb.util.BTreeMetaData meta,
                            int fileId)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException

Read the node with the specified fileId from disk.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

read

protected void read()
             throws java.io.IOException,
                    java.lang.ClassNotFoundException

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

Throws:

java.io.IOException

java.lang.ClassNotFoundException

write

protected void write()
              throws java.io.IOException

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

Throws:

java.io.IOException

save

public void save(java.io.File dataDirectory)
          throws java.io.IOException,
                 java.lang.ClassNotFoundException

Saves the tree. It saves the counter file and write()s any dirty nodes.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

saveAfterTruncate

public void saveAfterTruncate()
                       throws java.io.IOException,
                              java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

addFileId

protected final void addFileId(int fileId)

Add a reference to the given file id. Flags me as dirty.

addFileId

protected final void addFileId(int index,
                               int fileid)

Store a reference to the given file id at the specifed index. Flags me as dirty.

addFileIds

protected final void addFileIds(org.apache.commons.collections.primitives.IntList fileIds)

Add the given specified file ids. Flags me as dirty.

getBTreeMetaData

protected final org.axiondb.util.BTreeMetaData getBTreeMetaData()

getChildIds

protected final org.apache.commons.collections.primitives.IntList getChildIds()

getFileId

protected final int getFileId()

getFileIdForIndex

protected final int getFileIdForIndex(int index)

Get the file id for the specified index.

getKeyCapacity

protected final int getKeyCapacity()

Return the maximum number of keys I can contain (2* minimizationFactor-1).

getMinimizationFactor

protected final int getMinimizationFactor()

getValue

protected final int getValue(int index)

getValues

protected final org.apache.commons.collections.primitives.IntList getValues()

isFull

protected final boolean isFull()

isLeaf

protected final boolean isLeaf()

Returns true iff I don't contain any child nodes.

isRoot

protected final boolean isRoot()

Returns true iff I am the root node.

saveCounterIfRoot

protected final void saveCounterIfRoot()
                                throws java.io.IOException

Throws:

java.io.IOException

setChildIds

protected final void setChildIds(org.apache.commons.collections.primitives.IntList childIds)

setFileId

protected final void setFileId(int fileId)

setValue

protected final void setValue(int index,
                              int val)

setValues

protected final void setValues(org.apache.commons.collections.primitives.IntList vals)

space

protected final java.lang.String space(int n)

Return a String comprised of 2*n spaces.