Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by 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 AbstractLoggable
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  LongParameter CACHE_SIZE_PARAM
          Parameter to specify the size of the cache in bytes, must be an integer equal to or greater than 0.
protected  long 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.logging.AbstractLoggable
debug, logger
 
Constructor Summary
TreeIndex(Parameterization config)
          Constructor, adhering to Parameterizable
 
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.
 String getFileName()
           
 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.
protected abstract  Class<N> getNodeClass()
          Get the node class of this index
 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.
 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.
 
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
 

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 LongParameter 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 long 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(Parameterization config)
Constructor, adhering to Parameterizable

Parameters:
config - Parameterization
Method Detail

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

public 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

getNodeClass

protected abstract Class<N> getNodeClass()
Get the node class of this index

Returns:
node class

getFileName

public String getFileName()
Returns:
filename of the underlying persistence layer

Release 0.3 (2010-03-31_1612)