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>

All Implemented Interfaces:

Index<O>, Loggable, 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 String	CACHE_SIZE_D Description for parameter cachesize.
static String	CACHE_SIZE_P Option string for parameter cachesize.
protected int	cacheSize The size of the cache in bytes.
static int	DEFAULT_CACHE_SIZE The default cachesize.
static int	DEFAULT_PAGE_SIZE The default pagesize.
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 String	FILE_NAME_D Description for parameter filename.
static String	FILE_NAME_P Option string for parameter fileName.
private String	fileName The name of the file for storing the index.
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 String	PAGE_SIZE_D Description for parameter filename.
static String	PAGE_SIZE_P Option string for parameter pagesize.
protected int	pageSize The size of a page in bytes.
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

Constructor Summary

TreeIndex()
Sets parameters file, pageSize and cacheSize.

Method Summary

void	close() Closes this index and the underlying file.
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.
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.
String	description() Returns a description of the class and the required parameters.
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 counters for page access.
String[]	setParameters(String[] args) Sets the attributes of the class accordingly to the given parameters.

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

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getAttributeSettings, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

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

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, 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, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription

Field Detail

FILE_NAME_P

public static final String FILE_NAME_P

Option string for parameter fileName.

See Also:

Constant Field Values

FILE_NAME_D

public static final String FILE_NAME_D

Description for parameter filename.

See Also:

Constant Field Values

DEFAULT_PAGE_SIZE

public static final int DEFAULT_PAGE_SIZE

The default pagesize.

See Also:

Constant Field Values

PAGE_SIZE_P

public static final String PAGE_SIZE_P

Option string for parameter pagesize.

See Also:

Constant Field Values

PAGE_SIZE_D

public static final String PAGE_SIZE_D

Description for parameter filename.

See Also:

Constant Field Values

DEFAULT_CACHE_SIZE

public static final int DEFAULT_CACHE_SIZE

The default cachesize.

See Also:

Constant Field Values

CACHE_SIZE_P

public static final String CACHE_SIZE_P

Option string for parameter cachesize.

See Also:

Constant Field Values

CACHE_SIZE_D

public static final String CACHE_SIZE_D

Description for parameter cachesize.

See Also:

Constant Field Values

fileName

private String fileName

The name of the file for storing the index.

pageSize

protected int pageSize

The size of a page in bytes.

cacheSize

protected int cacheSize

The size of the cache in bytes.

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

Sets parameters file, pageSize and cacheSize.

Method Detail

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from interface: Parameterizable

Sets the attributes of the class accordingly to the given parameters. Returns a new String array containing those entries of the given array that are neither expected nor used by this Parameterizable.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractParameterizable

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

description

public String description()

Returns a description of the class and the required parameters.

This description should be suitable for a usage description.

Specified by:

description in interface Parameterizable

Overrides:

description in class AbstractParameterizable

Returns:

String a description of the class and the required parameters

See Also:

Parameterizable.description()

getPhysicalReadAccess

public final long getPhysicalReadAccess()

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

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

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

Resets the counters for page access.

Specified by:

resetPageAccess in interface Index<O extends DatabaseObject>

close

public final void close()

Closes this index and the underlying file. If this index has a oersistent file, all entries are written to disk.

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. Subclasses may need to overwrite this method.

Returns:

a 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