Class BTreeIndex

  • All Implemented Interfaces:
    ObjectIndex

    public class BTreeIndex
    extends java.lang.Object
    implements ObjectIndex
    Associates a key value with a long reference. In general, the reference is a file pointer that locates a serializable object associated with the key value; however, the index itself does not apply semantics to the reference. The user of index interprets the reference according to its design; an IndexedObjectDatabase, for example, uses the reference to record the file position of a Serializable object with a specific key.

    Use the IndexedObjectDatabase.attachIndex method to attach a BTreeIndex to a database. A database updates all attached indexes when it writes or removes objects from its file. This is the most common use of BTreeIndexes.

    It's important to realize that each key is associated with a long reference which is interpretted by the user. For example, the IndexedObjectDatabase class stores a file pointer in reference, thus associating a key value with a serialized object stored in the database. You can also use the reference as an index into an array, or in any other way appropriate to your application. It is even possible associate the same reference value with different keys.

    See Also:
    ObjectIndex, IndexedObjectDatabase
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected com.coyotegulch.jisp.PageFileHeader m_header
      Header data for a file containing B-Tree pages.
      protected java.util.HashMap m_pageCache
      A cache of pages that have already been loaded into memory.
    • Constructor Summary

      Constructors 
      Constructor Description
      BTreeIndex​(java.lang.String name)
      Opens an existing file, name, as a BTreeIndex.
      BTreeIndex​(java.lang.String name, int order, KeyObject nullKey, boolean hasDupes)
      Creates the specified file as a BTreeIndex, using the given order and null key value.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void close()
      Closes an open BTreeIndex and empties the page cache to release memory.
      static int computeOrder​(int numRecords, int maxHeight)
      Calculates a suggested value for a B-tree order, based on a given number of records and a maximum "height" for the B-tree structure.
      int count()
      Returns the number of keys stored in this index.
      void dumpTree​(java.io.PrintStream output)
      Dumps the entire B-Tree to System.out for analysis.
      void emptyPageCache()
      Empty the page cache.
      long findKey​(KeyObject key)
      Find the position of the object associated with a given key.
      long findKey​(KeyObject key, boolean allowNext)
      Find the position of an object associated with a given key, or its successor.
      int getPageCacheSize()
      Get the size of the page cache, in number of B-tree pages stored in memory.
      void insertKey​(KeyObject key, long reference)
      Insert a key into the index, associating a "reference" value with the given key.
      void removeKey​(KeyObject key)
      Removes the given key from the index.
      void replaceKey​(KeyObject key, long reference)
      Replaces the reference for the given key.
      void storeKey​(KeyObject key, long reference)
      Replaces or inserts the reference for the given key.
      long ticker()
      Returns the number of keys added to this index since its creation.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • m_header

        protected com.coyotegulch.jisp.PageFileHeader m_header
        Header data for a file containing B-Tree pages.
      • m_pageCache

        protected java.util.HashMap m_pageCache
        A cache of pages that have already been loaded into memory. As each page is read
    • Constructor Detail

      • BTreeIndex

        public BTreeIndex​(java.lang.String name)
                   throws java.io.IOException,
                          java.lang.ClassNotFoundException
        Opens an existing file, name, as a BTreeIndex.
        Parameters:
        name - name of the external index file to be opened.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
      • BTreeIndex

        public BTreeIndex​(java.lang.String name,
                          int order,
                          KeyObject nullKey,
                          boolean hasDupes)
                   throws java.io.IOException,
                          java.lang.ClassNotFoundException
        Creates the specified file as a BTreeIndex, using the given order and null key value. The null key is a "blank" key used in padding empty entries in B-tree pages. Obtain a null key for any key type by either invoking the default constructor or calling the KeyObject.makeNullKey method.
        Parameters:
        name - name of the external index file to be opened.
        order - order (page size) the the B-Tree. This should be an odd number greater than or equal to five (5). BTreeIndex will increment any even numbered order to the next consecutive odd number (if you specfy an order of 32, the index will actually have an order of 33). Also, an order less than 5 will be set to 5 automatically.
        nullKey - identifies a blank table entry and provides type-checking on new keys added to the index. All keys added to the index must have the same type as nullkey.
        hasDupes - Determines whether or not this index allows duplicate keys.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        See Also:
        KeyObject
    • Method Detail

      • computeOrder

        public static int computeOrder​(int numRecords,
                                       int maxHeight)
        Calculates a suggested value for a B-tree order, based on a given number of records and a maximum "height" for the B-tree structure.
        Parameters:
        numRecords - number of records expected in a B-tree index
        maxHeight - maximum allowable height for the B-tree (i.e., maximum number of pages to be read when searching for a key)
        Returns:
        a suggested value for oder, to be used in constructing a new BTreeIndex
        See Also:
        BTreeIndex
      • close

        public void close()
                   throws java.io.IOException
        Closes an open BTreeIndex and empties the page cache to release memory.
        Throws:
        java.io.IOException
      • count

        public int count()
        Returns the number of keys stored in this index. It is incremented when a new key is added, and decremented when a key is removed.
        Returns:
        the number of keys stored in this index
      • ticker

        public long ticker()
        Returns the number of keys added to this index since its creation. This value is incremented when a new key is added, but (unlike count, it is never decremented. In an index with a one-to-one correspondence between records and keys, this value provides a unique "record ID".
        Returns:
        the number of keys added to this index since its creation
      • insertKey

        public void insertKey​(KeyObject key,
                              long reference)
                       throws java.io.IOException,
                              java.lang.ClassNotFoundException
        Insert a key into the index, associating a "reference" value with the given key.
        Specified by:
        insertKey in interface ObjectIndex
        Parameters:
        key - identifies the record to be read
        reference - reference associated with key
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        DuplicateKey - when inserting a duplicate key into an index that does not support duplicates
        See Also:
        DuplicateKey, KeyObject
      • replaceKey

        public void replaceKey​(KeyObject key,
                               long reference)
                        throws java.io.IOException,
                               java.lang.ClassNotFoundException
        Replaces the reference for the given key. The method replaces the first occurrence of the key, if the index includes duplicates.
        Specified by:
        replaceKey in interface ObjectIndex
        Parameters:
        key - identifies the record being replaced
        reference - new reference to be associated with key
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        KeyNotFound - when the specified key can not be found in the index
        See Also:
        DuplicateKey, KeyObject
      • storeKey

        public void storeKey​(KeyObject key,
                             long reference)
                      throws java.io.IOException,
                             java.lang.ClassNotFoundException
        Replaces or inserts the reference for the given key. If the key exists, the reference associated with that key is replaced; if the key does not exist, a new key is inserted into the database with the given reference. If the index supports duplicate keys, the first-found occurence of the key will be replaced.
        Specified by:
        storeKey in interface ObjectIndex
        Parameters:
        key - identifies the record to be stored
        position - reference associated with key
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        See Also:
        KeyObject
      • findKey

        public long findKey​(KeyObject key)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException
        Find the position of the object associated with a given key.
        Specified by:
        findKey in interface ObjectIndex
        Parameters:
        key - a key to be sought in the index
        Returns:
        Position of the record associated with key.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        KeyNotFound - when the specified key can not be found in the index
        See Also:
        KeyNotFound, KeyObject
      • findKey

        public long findKey​(KeyObject key,
                            boolean allowNext)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException
        Find the position of an object associated with a given key, or its successor.
        Parameters:
        key - a key to be sought in the index
        allowNext - when true, findKey will return the reference associated with the key greater than or equal to key
        Returns:
        The reference associated with key.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        KeyNotFound - when the specified key can not be found in the index
        See Also:
        KeyNotFound, KeyObject
      • removeKey

        public void removeKey​(KeyObject key)
                       throws java.io.IOException,
                              java.lang.ClassNotFoundException
        Removes the given key from the index. If the index contains duplicates of key, the first key found will be deleted.
        Specified by:
        removeKey in interface ObjectIndex
        Parameters:
        key - A key identifying the record to be read.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        KeyNotFound - when the specified key can not be found in the index
        See Also:
        KeyNotFound, KeyObject
      • emptyPageCache

        public void emptyPageCache()
        Empty the page cache.
      • getPageCacheSize

        public int getPageCacheSize()
        Get the size of the page cache, in number of B-tree pages stored in memory.
      • dumpTree

        public void dumpTree​(java.io.PrintStream output)
                      throws java.io.IOException,
                             DuplicateKey,
                             java.lang.ClassNotFoundException
        Dumps the entire B-Tree to System.out for analysis. For diagnostic purposes only.
        Throws:
        java.io.IOException - when an I/O exception is thrown by an underlying java.io.* class
        java.lang.ClassNotFoundException - for a casting error, usually when a persistent object or index does match the expected type
        DuplicateKey - when inserting a duplicate key into an index that does not support duplicates