Class IndexTree<N extends Node<E>,​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