|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.axiondb.util.IntBTree
public class IntBTree
A B-Tree for integers, based on the implementation described in "Introduction to Algorithms" by Cormen, Leiserson and Rivest (CLR).
Constructor Summary | |
---|---|
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(File idxDir,
String idxName,
int minimizationFactor)
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(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 |
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(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 String |
space(int n)
Return a String comprised of 2*n spaces. |
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 |
---|
public IntBTree(File idxDir, String idxName, int minimizationFactor) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected IntBTree(org.axiondb.util.BTreeMetaData meta) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected IntBTree(org.axiondb.util.BTreeMetaData meta, int fileId) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
Method Detail |
---|
public final void clearData()
public final boolean delete(int key, int rowid) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final Integer get(int key) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final org.apache.commons.collections.primitives.IntListIterator getAll(int key) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final org.apache.commons.collections.primitives.IntListIterator getAllExcludingNull() throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final org.apache.commons.collections.primitives.IntListIterator getAllFrom(int key) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final org.apache.commons.collections.primitives.IntListIterator getAllTo(int key) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public IntListIteratorChain inorderIterator() throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final void insert(int key, int value) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public final void replaceId(int key, int oldRowId, int newRowId) throws ClassNotFoundException, IOException
ClassNotFoundException
IOException
public final void save() throws IOException, ClassNotFoundException
save(File)
IOException
ClassNotFoundException
public final int size()
minimizationFactor
-1 and at most
2*minimizationFactor
-1 for all nodes except the
root (which may have fewer than minimizationFactor
-1 keys).
public final String toString()
toString
in class Object
public void truncate()
org.axiondb.util.BaseBTree#reset()
public org.apache.commons.collections.primitives.IntListIterator valueIterator() throws IOException
IOException
public org.apache.commons.collections.primitives.IntListIterator valueIteratorGreaterThan(int fromkey) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
public org.apache.commons.collections.primitives.IntListIterator valueIteratorGreaterThanOrEqualTo(int fromkey) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected final void addKeyValuePair(int key, int value, boolean setDirty)
protected IntBTree createNode(org.axiondb.util.BTreeMetaData meta) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected final int getKey(int index)
protected IntBTree loadNode(org.axiondb.util.BTreeMetaData meta, int fileId) throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected void read() throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected void write() throws IOException
IOException
public void save(File dataDirectory) throws IOException, ClassNotFoundException
write()
s any dirty nodes.
IOException
ClassNotFoundException
public void saveAfterTruncate() throws IOException, ClassNotFoundException
IOException
ClassNotFoundException
protected final void addFileId(int fileId)
protected final void addFileId(int index, int fileid)
protected final void addFileIds(org.apache.commons.collections.primitives.IntList fileIds)
protected final org.axiondb.util.BTreeMetaData getBTreeMetaData()
protected final org.apache.commons.collections.primitives.IntList getChildIds()
protected final int getFileId()
protected final int getFileIdForIndex(int index)
protected final int getKeyCapacity()
minimizationFactor
-1).
protected final int getMinimizationFactor()
protected final int getValue(int index)
protected final org.apache.commons.collections.primitives.IntList getValues()
protected final boolean isFull()
protected final boolean isLeaf()
true
iff I don't contain any child nodes.
protected final boolean isRoot()
true
iff I am the root node.
protected final void saveCounterIfRoot() throws IOException
IOException
protected final void setChildIds(org.apache.commons.collections.primitives.IntList childIds)
protected final void setFileId(int fileId)
protected final void setValue(int index, int val)
protected final void setValues(org.apache.commons.collections.primitives.IntList vals)
protected final String space(int n)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |