org.axiondb.util

Class BaseBTree

abstract class BaseBTree extends Object

A b-tree is a balanced, multi-way search tree that assumes its data is stored on disk. The b-tree structure is designed to minimize the number of disk accesses by storing data in a broad, short tree and reading each node in one gulp.

Each b-tree node (excluding the root) contains at least t -1 and at most 2 t -1 keys (and their associated values) (where t is the "minimization factor") in non-decreasing order. Associated with each key k(i) is a reference to a subtree containing all keys greater than k(i-1) and less than or equal to k(i) . An "extra" subtree reference contains all keys greater than the maximum key in this node.

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

Author: Chuck Burdick Dave Pekarek Krohn Rodney Waldhoff

Constructor Summary
protected BaseBTree(BTreeMetaData meta)
protected BaseBTree(File dir, String name, int minimizationFactor)
Method Summary
protected voidaddFileId(int fileId)
Add a reference to the given file id.
protected voidaddFileId(int index, int fileid)
Store a reference to the given file id at the specifed index.
protected voidaddFileIds(IntList fileIds)
Add the given specified file ids.
protected voidclearData()
Clear my values and file ids.
protected BTreeMetaDatagetBTreeMetaData()
protected IntListgetChildIds()
protected intgetFileId()
protected intgetFileIdForIndex(int index)
Get the file id for the specified index.
protected intgetKeyCapacity()
Return the maximum number of keys I can contain (2* minimizationFactor-1).
protected intgetMinimizationFactor()
protected intgetValue(int index)
protected IntListgetValues()
protected booleanisFull()
protected booleanisLeaf()
Returns true iff I don't contain any child nodes.
protected booleanisRoot()
Returns true iff I am the root node.
protected abstract voidread()
abstract voidsave()
voidsave(File dataDirectory)
Saves the tree.
voidsaveAfterTruncate()
protected voidsaveCounterIfRoot()
protected voidsetChildIds(IntList childIds)
protected voidsetFileId(int fileId)
protected voidsetValue(int index, int val)
protected voidsetValues(IntList vals)
abstract intsize()
protected Stringspace(int n)
Return a String comprised of 2*n spaces.
voidtruncate()
protected abstract voidwrite()

Constructor Detail

BaseBTree

protected BaseBTree(BTreeMetaData meta)

BaseBTree

protected BaseBTree(File dir, String name, int minimizationFactor)

Parameters: dir the directory to store my data files in name the name of this btree structure (used to generate data file names) minimizationFactor the minimization factor (often t ). Each node will contain at most 2 t -1 keys, and 2 t children. root the root of my tree (or null if this node is going to be the root).

Method Detail

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(IntList fileIds)
Add the given specified file ids. Flags me as dirty.

clearData

protected void clearData()
Clear my values and file ids. Flags me as dirty.

getBTreeMetaData

protected final BTreeMetaData getBTreeMetaData()

getChildIds

protected final 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 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.

read

protected abstract void read()

save

public abstract void save()

save

public void save(File dataDirectory)
Saves the tree. It saves the counter file and BaseBTrees any dirty nodes.

saveAfterTruncate

public void saveAfterTruncate()

saveCounterIfRoot

protected final void saveCounterIfRoot()

setChildIds

protected final void setChildIds(IntList childIds)

setFileId

protected final void setFileId(int fileId)

setValue

protected final void setValue(int index, int val)

setValues

protected final void setValues(IntList vals)

size

public abstract int size()

space

protected final String space(int n)
Return a String comprised of 2*n spaces.

truncate

public void truncate()

write

protected abstract void write()