Package elki.index.tree
Class IndexTree<N extends Node<E>,E>
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- Type Parameters:
N
- the type of Node used in the indexE
- 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.
-
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 ofTreeIndexHeader
.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.
-
-
-
Field Detail
-
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.
-
-
Method Detail
-
initialize
public void initialize()
Initialize the tree if the page file already existed.- Specified by:
initialize
in interfaceIndex
-
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 ofTreeIndexHeader
. 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 headerfile
- 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 interfaceIndex
-
getPageSize
protected int getPageSize()
Get the page size of the backing storage.- Returns:
- Page size
-
-