IndexTree (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- 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

All Implemented Interfaces:

Index, Result

Direct Known Subclasses:

MetricalIndexTree, SpatialIndexTree
```
public abstract class IndexTree<N extends Node<E>,E extends Entry>
extends java.lang.Object
implements Index
```
Abstract super class for all tree based index classes.

Since:

0.1

Author:

Elke Achtert

Field Summary

Fields
Modifier and Type	Field and Description
`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

Constructors
Constructor and Description

IndexTree(PageFile<N> pagefile)
Constructor.

Constructors
Constructor and Description
`IndexTree(PageFile<N> pagefile)` Constructor.

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods Deprecated Methods
Modifier and Type	Method and Description
`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.
`int`	`getDirMinimum()` Get the minimum fill of a directory page (except root).
`protected PageFile<N>`	`getFile()` Deprecated.
`int`	`getLeafMinimum()` Get the minimum fill of a leaf page (except root).
`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(int nodeID)` Returns the node with the specified id.
`protected int`	`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.
`int`	`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.
`void`	`logStatistics()` Log some statistics, if enabled.
`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

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result
getLongName, getShortName

- 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.
    
    Specified by:
    
    initialize in interface Index
  - 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 int 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 int getPageID(Entry entry)
```
    Convert a directory entry to its page id.
    
    Parameters:
    
    entry - Entry
    
    Returns:
    
    Page ID
  - 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
  - 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.
    
    Parameters:
    
    header - File header
    
    file - Page 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
  - logStatistics
```
public void logStatistics()
```
    Log some statistics, if enabled.
    
    Specified by:
    
    logStatistics in interface Index
  - getPageSize
```
protected int getPageSize()
```
    Get the page size of the backing storage.
    
    Returns:
    
    Page size
  - getDirMinimum
```
public int getDirMinimum()
```
    Get the minimum fill of a directory page (except root).
    
    Returns:
    
    Minimum fill
  - getLeafMinimum
```
public int getLeafMinimum()
```
    Get the minimum fill of a leaf page (except root).
    
    Returns:
    
    Minimum fill
  - getFile
```
@Deprecated
protected PageFile<N> getFile()
```
    Deprecated.
    
    Directly access the backing page file.
    
    Returns:
    
    the page file

Class IndexTree<N extends Node<E>,E extends Entry>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface de.lmu.ifi.dbs.elki.result.Result

Field Detail

file

initialized

dirCapacity

leafCapacity

dirMinimum

leafMinimum

rootEntry

Constructor Detail

IndexTree

Method Detail

initialize

getLogger

getRootEntry

getRootID

getRoot

isRoot

getPageID

getNode

getNode

writeNode

deleteNode

createHeader

initializeFromFile

initialize

getRootPath

initializeCapacities

createEmptyRoot

createRootEntry

createNewLeafNode

createNewDirectoryNode

preInsert

postDelete

logStatistics

getPageSize

getDirMinimum

getLeafMinimum

getFile