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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>
Type Parameters:
N - the type of Node used in the index
E - the type of Entry used in the index
Direct Known Subclasses:
MetricalIndexTree, SpatialIndexTree

public abstract class IndexTree<N extends Node<E>,E extends Entry>
extends Object

Abstract super class for all tree based index classes.


Field Summary
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.
private  PageFile<N> file
          The file storing the entries of this 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.
private  E rootEntry
          The entry representing the root node.
 
Constructor Summary
IndexTree(PageFile<N> pagefile)
          Constructor.
 
Method Summary
protected abstract  void createEmptyRoot(E exampleLeaf)
          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()
          Creates a new directory node with the specified capacity.
protected abstract  N createNewLeafNode()
          Creates a new leaf node with the specified capacity.
protected abstract  E createRootEntry()
          Creates an entry representing the root node.
protected  void deleteNode(N node)
          Delete a node from the backing storage.
protected  PageFile<N> getFile()
          Deprecated. 
protected abstract  Logging getLogger()
          Get the (STATIC) logger for this class.
 N getNode(E entry)
          Returns the node that is represented by the specified entry.
 N getNode(Integer nodeID)
          Returns the node with the specified id.
 PageFileStatistics getPageFileStatistics()
          Get the index file page access statistics.
protected  Integer getPageID(Entry entry)
          Convert a directory entry to its page id.
protected  int getPageSize()
          Get the page size of the backing storage.
 N getRoot()
          Reads the root node of this index from the file.
 E getRootEntry()
          Returns the entry representing the root if this index.
 Integer getRootID()
          Page ID of the root entry.
 IndexTreePath<E> getRootPath()
          Returns the path to the root of this tree.
 void initialize()
          Initialize the tree if the page file already existed.
protected  void initialize(E exampleLeaf)
          Initializes the index.
protected abstract  void initializeCapacities(E exampleLeaf)
          Determines the maximum and minimum number of entries in a node.
 void initializeFromFile(TreeIndexHeader header, PageFile<N> file)
          Initializes this index from an existing persistent file.
protected  boolean isRoot(N page)
          Test if a given ID is the root.
protected  void postDelete(E entry)
          Performs necessary operations after deleting the specified entry.
protected  void preInsert(E entry)
          Performs necessary operations before inserting the specified entry.
protected  void writeNode(N node)
          Write a node to the backing storage.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

file

private final PageFile<N extends Node<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

IndexTree

public IndexTree(PageFile<N> pagefile)
Constructor.

Parameters:
pagefile - page file to use
Method Detail

initialize

public void initialize()
Initialize the tree if the page file already existed.


getLogger

protected abstract Logging getLogger()
Get the (STATIC) logger for this class.

Returns:
the static logger

getRootEntry

public final E getRootEntry()
Returns the entry representing the root if this index.

Returns:
the entry representing the root if this index

getRootID

public final Integer getRootID()
Page ID of the root entry.

Returns:
page id

getRoot

public N getRoot()
Reads the root node of this index from the file.

Returns:
the root node of this index

isRoot

protected boolean isRoot(N page)
Test if a given ID is the root.

Parameters:
page - Page to test
Returns:
Whether the page ID is the root

getPageID

protected Integer getPageID(Entry entry)
Convert a directory entry to its page id.

Parameters:
entry - Entry
Returns:
Page ID

getNode

public N getNode(Integer 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

writeNode

protected void writeNode(N node)
Write a node to the backing storage.

Parameters:
node - Node to write

deleteNode

protected void deleteNode(N node)
Delete a node from the backing storage.

Parameters:
node - Node to delete

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(TreeIndexHeader header,
                               PageFile<N> file)
Initializes this index from an existing persistent file.


initialize

protected final void initialize(E exampleLeaf)
Initializes the index.

Parameters:
exampleLeaf - an object that will be stored in the index

getRootPath

public final IndexTreePath<E> getRootPath()
Returns the path to the root of this tree.

Returns:
the path to the root of this tree

initializeCapacities

protected abstract void initializeCapacities(E exampleLeaf)
Determines the maximum and minimum number of entries in a node.

Parameters:
exampleLeaf - an object that will be stored in the index

createEmptyRoot

protected abstract void createEmptyRoot(E exampleLeaf)
Creates an empty root node and writes it to file.

Parameters:
exampleLeaf - 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()
Creates a new leaf node with the specified capacity.

Returns:
a new leaf node

createNewDirectoryNode

protected abstract N createNewDirectoryNode()
Creates a new directory node with the specified capacity.

Returns:
a new directory node

preInsert

protected void preInsert(E entry)
Performs necessary operations before inserting the specified entry.

Parameters:
entry - the entry to be inserted

postDelete

protected void postDelete(E entry)
Performs necessary operations after deleting the specified entry.

Parameters:
entry - the entry that was removed

getPageFileStatistics

public PageFileStatistics getPageFileStatistics()
Get the index file page access statistics.

Returns:
access statistics

getPageSize

protected int getPageSize()
Get the page size of the backing storage.

Returns:
Page size

getFile

@Deprecated
protected PageFile<N> getFile()
Deprecated. 

Directly access the backing page file.

Returns:
the page file

Release 0.4.0 (2011-09-20_1324)