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 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(IntList fileIds) Add the given specified file ids.
protected void	clearData() Clear my values and file ids.
protected BTreeMetaData	getBTreeMetaData()
protected IntList	getChildIds()
protected int	getFileId()
protected int	getFileIdForIndex(int index) Get the file id for 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 IntList	getValues()
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 abstract void	read()
abstract void	save()
void	save(File dataDirectory) Saves the tree.
void	saveAfterTruncate()
protected void	saveCounterIfRoot()
protected void	setChildIds(IntList childIds)
protected void	setFileId(int fileId)
protected void	setValue(int index, int val)
protected void	setValues(IntList vals)
abstract int	size()
protected String	space(int n) Return a String comprised of 2*n spaces.
void	truncate()
protected abstract void	write()

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).