Package com.coyotegulch.jisp
Class BTreeIndex
java.lang.Object
com.coyotegulch.jisp.BTreeIndex
- All Implemented Interfaces:
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 BTreeIndex
es.
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:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected com.coyotegulch.jisp.PageFileHeader
Header data for a file containing B-Tree pages.protected HashMap
A cache of pages that have already been loaded into memory. -
Constructor Summary
ConstructorsConstructorDescriptionBTreeIndex
(String name) Opens an existing file,name
, as aBTreeIndex
.BTreeIndex
(String name, int order, KeyObject nullKey, boolean hasDupes) Creates the specified file as aBTreeIndex
, using the given order andnull
key value. -
Method Summary
Modifier and TypeMethodDescriptionvoid
close()
Closes an openBTreeIndex
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
(PrintStream output) Dumps the entire B-Tree toSystem.out
for analysis.void
Empty the page cache.long
Find the position of the object associated with a given key.long
Find the position of an object associated with a given key, or its successor.int
Get the size of the page cache, in number of B-tree pages stored in memory.void
Insert a key into the index, associating a "reference" value with the given key.void
Removes the given key from the index.void
replaceKey
(KeyObject key, long reference) Replaces the reference for the given key.void
Replaces or inserts the reference for the given key.long
ticker()
Returns the number of keys added to this index since its creation.
-
Field Details
-
m_header
protected com.coyotegulch.jisp.PageFileHeader m_headerHeader data for a file containing B-Tree pages. -
m_pageCache
A cache of pages that have already been loaded into memory. As each page is read
-
-
Constructor Details
-
BTreeIndex
Opens an existing file,name
, as aBTreeIndex
.- Parameters:
name
- name of the external index file to be opened.- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected type
-
BTreeIndex
public BTreeIndex(String name, int order, KeyObject nullKey, boolean hasDupes) throws IOException, ClassNotFoundException Creates the specified file as aBTreeIndex
, using the given order andnull
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 theKeyObject.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 asnullkey
.hasDupes
- Determines whether or not this index allows duplicate keys.- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected type- See Also:
-
-
Method Details
-
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 indexmaxHeight
- 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:
-
close
Closes an openBTreeIndex
and empties the page cache to release memory.- Throws:
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 (unlikecount, 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
Insert a key into the index, associating a "reference" value with the given key.- Specified by:
insertKey
in interfaceObjectIndex
- Parameters:
key
- identifies the record to be readreference
- reference associated with key- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeDuplicateKey
- when inserting a duplicate key into an index that does not support duplicates- See Also:
-
replaceKey
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 interfaceObjectIndex
- Parameters:
key
- identifies the record being replacedreference
- new reference to be associated with key- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeKeyNotFound
- when the specified key can not be found in the index- See Also:
-
storeKey
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 interfaceObjectIndex
- Parameters:
key
- identifies the record to be storedposition
- reference associated with key- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected type- See Also:
-
findKey
Find the position of the object associated with a given key.- Specified by:
findKey
in interfaceObjectIndex
- Parameters:
key
- a key to be sought in the index- Returns:
- Position of the record associated with
key
. - Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeKeyNotFound
- when the specified key can not be found in the index- See Also:
-
findKey
Find the position of an object associated with a given key, or its successor.- Parameters:
key
- a key to be sought in the indexallowNext
- whentrue
,findKey
will return the reference associated with the key greater than or equal tokey
- Returns:
- The reference associated with
key
. - Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeKeyNotFound
- when the specified key can not be found in the index- See Also:
-
removeKey
Removes the given key from the index. If the index contains duplicates ofkey
, the first key found will be deleted.- Specified by:
removeKey
in interfaceObjectIndex
- Parameters:
key
- A key identifying the record to be read.- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeKeyNotFound
- when the specified key can not be found in the index- See Also:
-
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
Dumps the entire B-Tree toSystem.out
for analysis. For diagnostic purposes only.- Throws:
IOException
- when an I/O exception is thrown by an underlying java.io.* classClassNotFoundException
- for a casting error, usually when a persistent object or index does match the expected typeDuplicateKey
- when inserting a duplicate key into an index that does not support duplicates
-