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

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

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