com.coyotegulch.jisp
Class BTreeIndex

java.lang.Object
  extended bycom.coyotegulch.jisp.BTreeShared
      extended bycom.coyotegulch.jisp.BTreePageFile
          extended bycom.coyotegulch.jisp.BTreeIndex
All Implemented Interfaces:
ObjectIndex

public class BTreeIndex
extends com.coyotegulch.jisp.BTreePageFile
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; an IndexedObjectDatabase, for example, stores a file pointer in reference, thus associating a key value with a serialized object stored in the database. You could 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.

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.

See Also:
ObjectIndex, IndexedObjectDatabase

Nested Class Summary
protected  class BTreeIndex.SearchResult
           
 
Field Summary
protected  IndexedObjectDatabase m_database
           
protected  com.coyotegulch.jisp.BTreePageFileHeader 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.
protected  ObjectDatabaseFile m_pagefile
          File containing B-tree pages
protected  com.coyotegulch.jisp.BTreePage m_root
           
 
Constructor Summary
BTreeIndex(java.lang.String name)
          Opens an existing file, name, as a BTreeIndex.
BTreeIndex(java.lang.String name, int order, boolean hasDupes)
          Creates the specified file as a BTreeIndex, using the given order
 
Method Summary
 void close()
          Closes an open BTreeIndex and empties the page cache to release memory.
 int count()
          Returns the number of keys stored in this index.
 void dumpTree(java.io.PrintStream output)
          Dumps the entire B-Tree to a print strem for analysis.
 void emptyPageCache()
          Empty the page cache.
 long[] findKey(OrderedObject key)
          Find the position of the object associated with a given key.
 long[] findKey(OrderedObject 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(OrderedObject key, long reference)
          Insert a key into the index, associating a "reference" value with the given key.
 void removeKey(OrderedObject key, long reference)
          Removes specified reference from the entry for the given key, and removes the key itself if it no longer has an references.
 void removeKeyAll(OrderedObject key)
          Removes the given key from the index, no matter how many references it might be associated with.
 boolean supportsDupes()
          Returns whether or not this index support duplicate keys.
 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_root

protected com.coyotegulch.jisp.BTreePage m_root

m_database

protected IndexedObjectDatabase m_database

m_header

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


m_pagefile

protected ObjectDatabaseFile m_pagefile
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,
                  boolean hasDupes)
           throws java.io.IOException,
                  java.lang.ClassNotFoundException
Creates the specified file as a BTreeIndex, using the given order

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.
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:
OrderedObject
Method Detail

close

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

Throws:
java.io.IOException

supportsDupes

public boolean supportsDupes()
Returns whether or not this index support duplicate keys.

Specified by:
supportsDupes in interface ObjectIndex
Returns:
true if the index supports duplicate keys; false if it does not

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(OrderedObject 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
DuplicateKeyException - when inserting a duplicate key into an index that does not support duplicates
See Also:
DuplicateKeyException, OrderedObject

findKey

public long[] findKey(OrderedObject 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
KeyNotFoundException - when the specified key can not be found in the index
See Also:
KeyNotFoundException, OrderedObject

findKey

public long[] findKey(OrderedObject 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
KeyNotFoundException - when the specified key can not be found in the index
See Also:
KeyNotFoundException, OrderedObject

removeKey

public void removeKey(OrderedObject key,
                      long reference)
               throws java.io.IOException,
                      java.lang.ClassNotFoundException
Removes specified reference from the entry for the given key, and removes the key itself if it no longer has an references. This method is used internally by IndexedObjectDatabase

Specified by:
removeKey in interface ObjectIndex
Parameters:
key - A key identifying the record to be read.
reference -
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
KeyNotFoundException - when the specified key can not be found in the index
See Also:
KeyNotFoundException, OrderedObject

removeKeyAll

public void removeKeyAll(OrderedObject key)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
Removes the given key from the index, no matter how many references it might be associated with.

Specified by:
removeKeyAll 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
KeyNotFoundException - when the specified key can not be found in the index
See Also:
KeyNotFoundException, OrderedObject

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.

Returns:
number of B-tree pages stored in cache

dumpTree

public void dumpTree(java.io.PrintStream output)
              throws java.io.IOException,
                     DuplicateKeyException,
                     java.lang.ClassNotFoundException
Dumps the entire B-Tree to a print strem for analysis. For diagnostic purposes only.

Parameters:
output - stream to which output is sent
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
DuplicateKeyException - when inserting a duplicate key into an index that does not support duplicates