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

Direct Known Subclasses:

AbstractRStarTree, MetricalIndexTree
```
public abstract class IndexTree<N extends Node<E>,E>
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	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 Description

IndexTree(PageFile<N> pagefile)
Constructor.

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods Deprecated Methods
Modifier and Type	Method	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.
`protected PageFile<N>`	`getFile()`	Deprecated.
`protected abstract Logging`	`getLogger()`	Get the (STATIC) logger for this class.
`N`	`getNode(int nodeID)`	Returns the node with the specified id.
`N`	`getNode(E entry)`	Returns the node that is represented by the specified entry.
`protected int`	`getPageID(E entry)`	Convert a directory entry to its page id.
`protected int`	`getPageSize()`	Get the page size of the backing storage.
`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()`	Send statistics to the logger, 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

- 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 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
  - 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(E 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 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()
```
    Description copied from interface: Index
    
    Send statistics to the logger, if enabled.
    Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.
    
    Specified by:
    
    logStatistics in interface Index
  - 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, still used by the old xtree code.
    
    Returns:
    
    the page file

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

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

file

initialized

dirCapacity

leafCapacity

dirMinimum

leafMinimum

rootEntry

Constructor Detail

IndexTree

Method Detail

initialize

getLogger

getRootEntry

getRootID

isRoot

getPageID

getNode

getNode

writeNode

deleteNode

createHeader

initializeFromFile

initialize

getRootPath

initializeCapacities

createEmptyRoot

createRootEntry

createNewLeafNode

createNewDirectoryNode

preInsert

postDelete

logStatistics

getPageSize

getFile

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