org.axiondb.util
Class ObjectBTree

java.lang.Object
  extended by org.axiondb.util.ObjectBTree
Direct Known Subclasses:
StringBTree

public class ObjectBTree
extends java.lang.Object

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 $

Constructor Summary
protected ObjectBTree(org.axiondb.util.BTreeMetaData meta, java.util.Comparator comp)
          Create a new, non-root node.
protected ObjectBTree(org.axiondb.util.BTreeMetaData meta, java.util.Comparator comp, int fileId)
          Create a non-root node by reading it from disk.
  ObjectBTree(java.io.File idxDir, java.lang.String idxName, int minimizationFactor, java.util.Comparator comp)
          Create or load a new root node.
 
Method Summary
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(java.lang.Object key, int value, boolean setDirty)
           
 void clearData()
          Clear my keys, values, and file ids.
protected  ObjectBTree createNode(org.axiondb.util.BTreeMetaData meta, java.util.Comparator comp)
          Create a new node.
 void delete(java.lang.Object key, int rowid)
          Optimized: Delete an arbitrary instance of the specified key and the specifiied rowid
 java.lang.Integer get(java.lang.Object key)
          Find some occurance of the given key.
 org.apache.commons.collections.primitives.IntListIterator getAll(java.lang.Object 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
protected  void getAllExcludingNull(IntListIteratorChain chain)
           
 org.apache.commons.collections.primitives.IntListIterator getAllFrom(java.lang.Object key)
          Obtain an iterator over all values greater than or equal to the given key.
 org.apache.commons.collections.primitives.IntListIterator getAllTo(java.lang.Object 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  java.lang.Object 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  java.lang.Object getNullKey()
           
protected  int getValue(int index)
           
protected  org.apache.commons.collections.primitives.IntList getValues()
           
 IntListIteratorChain inorderIterator()
           
 void insert(java.lang.Object 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  ObjectBTree loadNode(org.axiondb.util.BTreeMetaData meta, java.util.Comparator comp, int fileId)
          Read the node with the specified fileId from disk.
protected  void read()
          Reads in the node.
 void replaceId(java.lang.Object 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()
           
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

ObjectBTree

public ObjectBTree(java.io.File idxDir,
                   java.lang.String idxName,
                   int minimizationFactor,
                   java.util.Comparator comp)
            throws java.io.IOException,
                   java.lang.ClassNotFoundException
Create or load a new root node.

Throws:
java.io.IOException
java.lang.ClassNotFoundException

ObjectBTree

protected ObjectBTree(org.axiondb.util.BTreeMetaData meta,
                      java.util.Comparator comp)
               throws java.io.IOException,
                      java.lang.ClassNotFoundException
Create a new, non-root node.

Throws:
java.io.IOException
java.lang.ClassNotFoundException

ObjectBTree

protected ObjectBTree(org.axiondb.util.BTreeMetaData meta,
                      java.util.Comparator comp,
                      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 void delete(java.lang.Object key,
                         int rowid)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
Optimized: Delete an arbitrary instance of the specified key and the specifiied rowid

Throws:
java.io.IOException
java.lang.ClassNotFoundException

get

public final java.lang.Integer get(java.lang.Object 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(java.lang.Object 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(java.lang.Object 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(java.lang.Object 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(java.lang.Object 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(java.lang.Object 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()

addKeyValuePair

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

createNode

protected ObjectBTree createNode(org.axiondb.util.BTreeMetaData meta,
                                 java.util.Comparator comp)
                          throws java.io.IOException,
                                 java.lang.ClassNotFoundException
Create a new node.

Throws:
java.io.IOException
java.lang.ClassNotFoundException

getAllExcludingNull

protected void getAllExcludingNull(IntListIteratorChain chain)
                            throws java.io.IOException,
                                   java.lang.ClassNotFoundException
Throws:
java.io.IOException
java.lang.ClassNotFoundException

getKey

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


getNullKey

protected java.lang.Object getNullKey()

loadNode

protected ObjectBTree loadNode(org.axiondb.util.BTreeMetaData meta,
                               java.util.Comparator comp,
                               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.