de.lmu.ifi.dbs.elki.index.tree
Class TreeIndex<O extends DatabaseObject,N extends Node<N,E>,E extends Entry>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>

Type Parameters:

O - the type of DatabaseObject to be stored in the index

N - the type of Node used in the index

E - the type of Entry used in the index

All Implemented Interfaces:

Index<O>, Parameterizable

Direct Known Subclasses:

MetricalIndex, SpatialIndex

public abstract class TreeIndex<O extends DatabaseObject,N extends Node<N,E>,E extends Entry>
extends AbstractParameterizable
implements Index<O>

Abstract super class for all tree based index classes.

Author:

Elke Achtert

Field Summary

static OptionID	CACHE_SIZE_ID OptionID for CACHE_SIZE_PARAM
private IntParameter	CACHE_SIZE_PARAM Parameter to specify the size of the cache in bytes, must be an integer equal to or greater than 0.
protected int	cacheSize Holds the value of CACHE_SIZE_PARAM.
protected int	dirCapacity The capacity of a directory node (= 1 + maximum number of entries in a directory node).
protected int	dirMinimum The minimum number of entries in a directory node.
protected PageFile<N>	file The file storing the entries of this index.
static OptionID	FILE_ID OptionID for FILE_PARAM
private FileParameter	FILE_PARAM Optional parameter that specifies the name of the file storing the index.
private String	fileName Holds the name of the file storing the index specified by FILE_PARAM, null if FILE_PARAM is not specified.
protected boolean	initialized True if this index is already initialized.
protected int	leafCapacity The capacity of a leaf node (= 1 + maximum number of entries in a leaf node).
protected int	leafMinimum The minimum number of entries in a leaf node.
static OptionID	PAGE_SIZE_ID OptionID for PAGE_SIZE_PARAM
private IntParameter	PAGE_SIZE_PARAM Parameter to specify the size of a page in bytes, must be an integer greater than 0.
protected int	pageSize Holds the value of PAGE_SIZE_PARAM.
private E	rootEntry The entry representing the root node.

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

TreeIndex()
Adds parameters FILE_PARAM, PAGE_SIZE_PARAM, and CACHE_SIZE_PARAM to the option handler additionally to parameters of super class.

Method Summary

void	close() Closes this index.
protected abstract void	createEmptyRoot(O object) Creates an empty root node and writes it to file.
protected TreeIndexHeader	createHeader() Creates a header for this index structure which is an instance of TreeIndexHeader.
protected abstract N	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected abstract N	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
protected abstract E	createRootEntry() Creates an entry representing the root node.
long	getLogicalPageAccess() Returns the logical page access of this index.
N	getNode(E entry) Returns the node that is represented by the specified entry.
N	getNode(int nodeID) Returns the node with the specified id.
long	getPhysicalReadAccess() Returns the physical read access of this index.
long	getPhysicalWriteAccess() Returns the physical write access of this index.
protected N	getRoot() Reads the root node of this index from the file.
E	getRootEntry() Returns the entry representing the root if this index.
protected TreeIndexPath<E>	getRootPath() Returns the path to the root of this tree.
protected void	initialize(O object) Initializes the index.
protected abstract void	initializeCapacities(O object, boolean verbose) Determines the maximum and minimum number of entries in a node.
protected void	initializeFromFile() Initializes this index from an existing persistent file.
protected abstract void	postDelete(O o) Performs necessary operations after deleting the specified object.
protected abstract void	preInsert(E entry) Performs necessary operations before inserting the specified entry.
void	resetPageAccess() Resets the three counters for page access, i.e., the counters for physical read and write access, and the counter for logical page access.
List<String>	setParameters(List<String> args) Calls the super method AbstractParameterizable#setParameters(args)} and sets additionally the values of the parameters FILE_PARAM, PAGE_SIZE_PARAM.

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

delete, insert, insert, setDatabase

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

Field Detail

FILE_ID

public static final OptionID FILE_ID

OptionID for FILE_PARAM

FILE_PARAM

private final FileParameter FILE_PARAM

Optional parameter that specifies the name of the file storing the index. If this parameter is not set the index is hold in the main memory.

Key: -treeindex.file

fileName

private String fileName

Holds the name of the file storing the index specified by FILE_PARAM, null if FILE_PARAM is not specified.

PAGE_SIZE_ID

public static final OptionID PAGE_SIZE_ID

OptionID for PAGE_SIZE_PARAM

PAGE_SIZE_PARAM

private final IntParameter PAGE_SIZE_PARAM

Parameter to specify the size of a page in bytes, must be an integer greater than 0.

Default value: 4000

Key: -treeindex.pagesize

pageSize

protected int pageSize

Holds the value of PAGE_SIZE_PARAM.

CACHE_SIZE_ID

public static final OptionID CACHE_SIZE_ID

OptionID for CACHE_SIZE_PARAM

CACHE_SIZE_PARAM

private final IntParameter CACHE_SIZE_PARAM

Parameter to specify the size of the cache in bytes, must be an integer equal to or greater than 0.

Default value: Integer.MAX_VALUE

Key: -treeindex.cachesize

cacheSize

protected int cacheSize

Holds the value of CACHE_SIZE_PARAM.

file

protected PageFile<N extends Node<N,E>> file

The file storing the entries of this index.

initialized

protected boolean initialized

True if this index is already initialized.

dirCapacity

protected int dirCapacity

The capacity of a directory node (= 1 + maximum number of entries in a directory node).

leafCapacity

protected int leafCapacity

The capacity of a leaf node (= 1 + maximum number of entries in a leaf node).

dirMinimum

protected int dirMinimum

The minimum number of entries in a directory node.

leafMinimum

protected int leafMinimum

The minimum number of entries in a leaf node.

rootEntry

private E extends Entry rootEntry

The entry representing the root node.

Constructor Detail

TreeIndex

public TreeIndex()

Adds parameters FILE_PARAM, PAGE_SIZE_PARAM, and CACHE_SIZE_PARAM to the option handler additionally to parameters of super class.

Method Detail

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException

Calls the super method AbstractParameterizable#setParameters(args)} and sets additionally the values of the parameters FILE_PARAM, PAGE_SIZE_PARAM.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractParameterizable

Parameters:

args - parameters to set the attributes accordingly to

Returns:

a list containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

getPhysicalReadAccess

public final long getPhysicalReadAccess()

Description copied from interface: Index

Returns the physical read access of this index.

Specified by:

getPhysicalReadAccess in interface Index<O extends DatabaseObject>

Returns:

the number of pages read from hard disk since the last call of resetPageAccess.

getPhysicalWriteAccess

public final long getPhysicalWriteAccess()

Description copied from interface: Index

Returns the physical write access of this index.

Specified by:

getPhysicalWriteAccess in interface Index<O extends DatabaseObject>

Returns:

the number of pages written to hard disk since the last call of resetPageAccess.

getLogicalPageAccess

public final long getLogicalPageAccess()

Description copied from interface: Index

Returns the logical page access of this index.

Specified by:

getLogicalPageAccess in interface Index<O extends DatabaseObject>

Returns:

the overall number of pages accesses (including e.g. cache operations like put or remove) since the last call of resetPageAccess.

resetPageAccess

public final void resetPageAccess()

Description copied from interface: Index

Resets the three counters for page access, i.e., the counters for physical read and write access, and the counter for logical page access.

Specified by:

resetPageAccess in interface Index<O extends DatabaseObject>

close

public final void close()

Description copied from interface: Index

Closes this index.

Specified by:

close in interface Index<O extends DatabaseObject>

getRootEntry

public final E getRootEntry()

Returns the entry representing the root if this index.

Returns:

the entry representing the root if this index

getNode

public final N getNode(int nodeID)

Returns the node with the specified id.

Parameters:

nodeID - the page id of the node to be returned

Returns:

the node with the specified id

getNode

public final N getNode(E entry)

Returns the node that is represented by the specified entry.

Parameters:

entry - the entry representing the node to be returned

Returns:

the node that is represented by the specified entry

createHeader

protected TreeIndexHeader createHeader()

Creates a header for this index structure which is an instance of TreeIndexHeader. Subclasses may need to overwrite this method if they need a more specialized header.

Returns:

a new header for this index structure

initializeFromFile

protected void initializeFromFile()

Initializes this index from an existing persistent file.

initialize

protected final void initialize(O object)

Initializes the index.

Parameters:

object - an object that will be stored in the index

getRootPath

protected final TreeIndexPath<E> getRootPath()

Returns the path to the root of this tree.

Returns:

the path to the root of this tree

getRoot

protected N getRoot()

Reads the root node of this index from the file.

Returns:

the root node of this index

initializeCapacities

protected abstract void initializeCapacities(O object,
                                             boolean verbose)

Determines the maximum and minimum number of entries in a node.

Parameters:

object - an object that will be stored in the index

verbose - flag to allow verbose messages

createEmptyRoot

protected abstract void createEmptyRoot(O object)

Creates an empty root node and writes it to file.

Parameters:

object - an object that will be stored in the index

createRootEntry

protected abstract E createRootEntry()

Creates an entry representing the root node.

Returns:

an entry representing the root node

createNewLeafNode

protected abstract N createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected abstract N createNewDirectoryNode(int capacity)

Creates a new directory node with the specified capacity.

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

preInsert

protected abstract void preInsert(E entry)

Performs necessary operations before inserting the specified entry.

Parameters:

entry - the entry to be inserted

postDelete

protected abstract void postDelete(O o)

Performs necessary operations after deleting the specified object.

Parameters:

o - the object to be deleted