org.helidb.backend.index.bplus
Class BPlusTreeIndexBackend<K,V,H extends Comparable<H>,P>

java.lang.Object
  org.helidb.backend.AbstractDatabaseBackendProxy<K,V,P>
      org.helidb.backend.index.bplus.BPlusTreeIndexBackend<K,V,H,P>

Type Parameters:

K - The type of keys in the database.

V - The type of values in the database.

H - The type of the hashed keys.

P - The type of positions in the indexed backend.

All Implemented Interfaces:

Iterable<Record<K,V>>, DatabaseBackend<K,V,P>

public class BPlusTreeIndexBackend<K,V,H extends Comparable<H>,P>
extends AbstractDatabaseBackendProxy<K,V,P>

This DatabaseBackend provides a B+ Tree index for the keys of another, proxied DatabaseBackend. If searching that backend is slow, the B+ Tree index can be used to speed it up.

The keys of the index B+ Tree are hashes of the database keys, created by running the keys through a Hasher object. The key hash has the following properties

• Unique keys give unique hashes.
• The hash is of a constant length regardless of the size of the input.

If the keys themselves are of constant size, a value-preserving Hasher such as the IntegerToIntegerHasher or the ConstantSizeValueHasher can be used.

If the database should support null keys, the Hasher must support hashing null values.

If the key Hasher is value-preserving, this index modifies the behavior of the database's key iterator and its Cursor to return the keys/records in the natural order of the keys (the order determined by the keys' implementation of Comparable.compareTo(Object)). The behaviors of the other iterators are not modified.

The values in the index B+ Tree are the positions of the indexed records in the proxied backend. This backend registers a RecordMoveListener with the proxied backend, so it is able to cope with records moving around in the proxied backend.

Since:

1.0

Author:

Karl Gustafsson

See Also:

BPlusTreeIndexBackendFactory, BPlusTreeIndexBackendBuilder

In_jar:

helidb-bplus_index_backend

Constructor Summary

BPlusTreeIndexBackend(DatabaseBackend<K,V,P> backend, boolean readOnly, BPlusTree<H,P> tree, Hasher<K,H> keyHasher, LogAdapterHolder lah)
Constructor.

Method Summary

void	clear() Wipe out the entire database.
void	close() Subclasses overriding this method must call super.close().
boolean	compact() Call compact on the proxied backend.
boolean	delete(K key) Delete the record with the supplied key, if it exists.
protected void	finalize()
P	find(Comparable<K> key, SearchMode mode) If the B+ Tree uses a value-preserving Hasher and the natural ordering of its (Comparable) keys (i.e., not a custom key Comparator), use the tree's fast find method.
P	find(K key) Find the position of the record with the supplied key in the database backend.
P	find(K key, SearchMode mode, Comparator<? super K> cmp) If the B+ Tree uses a value-preserving Hasher and a key Comparator that is equal to the supplied Comparator, use the tree's efficient find method.
void	forEachKey(ForEachKeyCallback<K,P> callback) Call the proxied backend's forEachKey method.
P	getFirstPosition() Call getFirstPosition on the proxied backend.
P	getLastPosition() Call getLastPosition on the proxied backend.
P	getNextPosition(P pos) Call getNextPosition on the proxied backend.
P	getPreviousPosition(P pos) Call getPreviousPosition on the proxied backend.
V	getValueFor(K key) Get the value for the record with the supplied key.
P	insert(K key, V value) Insert a new record in the database.
P	insertCheckKeyUnique(K key, V value) Insert a new record in the database after verifying that the key is unique within the database.
boolean	insertOrUpdate(K key, V value) If a record with the supplied key exists, update its value.
Iterator<K>	keyIterator() Get a key iterator from the proxied backend.
K	readKeyAt(P pos) Read the key at the supplied position.
Record<K,V>	readRecordAt(P pos) Read the record (key and value) at the specified position.
V	readValueAt(P pos) Read the value at the specified position.
V	remove(K key) Delete the record with the supplied key and return its value.
void	removeAt(P pos, K key) Delete the record at the supplied position.
void	replaceContentsWith(RandomAccess ra, long dataSize) Replace the contents of the database with content read from the supplied RandomAccess.
Pair<P>	update(K key, V value) Update an existing record with a new value.
P	updateAt(P pos, K key, V value) Update the record at the supplied position with the new value.
long	writeContentsTo(RandomAccess ra) Call writeContentsTo on the proxied backend.

Methods inherited from class org.helidb.backend.AbstractDatabaseBackendProxy

addRecordMoveListener, assertNotClosed, assertNotReadOnly, getContentsVersion, getKeys, getProxied, getRecords, getValues, isClosed, isReadOnly, iterator, removeRecordMoveListener, valueIterator

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BPlusTreeIndexBackend

public BPlusTreeIndexBackend(DatabaseBackend<K,V,P> backend,
                             boolean readOnly,
                             BPlusTree<H,P> tree,
                             Hasher<K,H> keyHasher,
                             LogAdapterHolder lah)

Constructor.

The supplied B+ Tree must contain a valid index for the database backend. This is trivially true if both are empty.

The BPlusTreeIndexBackendBuilder may be more convenient to use than this constructor.

Parameters:

backend - The database backend that should be indexed.

readOnly - Should the database backend be read only?

tree - A B+ Tree containing the index for the database backend. The keys of the B+ Tree are the hashes of the database keys, and the values are the positions of each record in the proxied backend.

keyHasher - Hasher for hashing keys.

lah - A log adapter holder.

Method Detail

forEachKey

public void forEachKey(ForEachKeyCallback<K,P> callback)

Description copied from class: AbstractDatabaseBackendProxy

Call the proxied backend's forEachKey method.

Specified by:

forEachKey in interface DatabaseBackend<K,V,P>

Overrides:

forEachKey in class AbstractDatabaseBackendProxy<K,V,P>

Parameters:

callback - The callback object to call for each key.

insert

public P insert(K key,
                V value)

Description copied from interface: DatabaseBackend

Insert a new record in the database.

Parameters:

key - The key. It is not verified that this key is unique. Inserting duplicate keys will result in unspecified behavior from the backend.

value - The value.

Returns:

The position of the new record.

insertCheckKeyUnique

public P insertCheckKeyUnique(K key,
                              V value)

Description copied from interface: DatabaseBackend

Insert a new record in the database after verifying that the key is unique within the database.

Parameters:

key - The key.

value - The value.

Returns:

The position of the new record.

updateAt

public P updateAt(P pos,
                  K key,
                  V value)

Description copied from interface: DatabaseBackend

Update the record at the supplied position with the new value. The new key is always the same as the previous key.

It is up to the implementation to decide exactly how this is done. It is not required that the record should be located at the same position in the backend after the update. One strategy for implementing this method is to delete the old record and insert a new record with the updated values.

Parameters:

pos - The position of the record to update.

key - The record's key. The key is not modified by the update.

value - The new value.

Returns:

The new position of the record.

update

public Pair<P> update(K key,
                      V value)

Description copied from interface: DatabaseBackend

Update an existing record with a new value.

It is up to the implementation to decide exactly how this is done. It is not required that the record should be located at the same position in the backend after the update. One strategy for implementing this method is to delete the old record and insert a new record with the updated values.

Parameters:

key - The record's key.

value - The record's new value.

Returns:

The record's old position (the first object in the pair) and the new position (the second object in the pair).

insertOrUpdate

public boolean insertOrUpdate(K key,
                              V value)

Description copied from interface: DatabaseBackend

If a record with the supplied key exists, update its value. If not, insert a new record.

Parameters:

key - The key.

value - The value.

Returns:

true if an existing record was updated, false if a new record was inserted.

find

public P find(K key)

Description copied from interface: DatabaseBackend

Find the position of the record with the supplied key in the database backend.

Parameters:

key - The key to find.

Returns:

The position of the key, or null if not found.

See Also:

DatabaseBackend.find(Comparable, SearchMode), DatabaseBackend.find(Object, SearchMode, Comparator)

find

public P find(Comparable<K> key,
              SearchMode mode)

If the B+ Tree uses a value-preserving Hasher and the natural ordering of its (Comparable) keys (i.e., not a custom key Comparator), use the tree's fast find method. Otherwise, use the find method of the proxied backend.

Parameters:

key - The key to find.

mode - The search mode. The backend implementation must support the SearchMode.EXACT_MATCH mode (which makes this method behave exactly like DatabaseBackend.find(Object)). The backend may also support SearchMode.CLOSEST_ABOVE, SearchMode.CLOSEST_BELOW and SearchMode.CLOSEST_MATCH. If not, this method should throw an UnsupportedOperationException when called with any of those search modes. The backend implementation may also invent its own search modes.

The closest match is defined as the match that gives the lowest positive (SearchMode.CLOSEST_ABOVE), negative ( SearchMode.CLOSEST_BELOW) or absolute ( SearchMode.CLOSEST_MATCH) value from the supplied key's Comparable.compareTo(Object) method when comparing the keys in the database with the key to search for.

Returns:

The position of the record that matches the search criteria, or null if no record matching the search criteria is found.

Since:

1.1

See Also:

DatabaseBackend.find(Object), DatabaseBackend.find(Object, SearchMode, Comparator)

find

public P find(K key,
              SearchMode mode,
              Comparator<? super K> cmp)

If the B+ Tree uses a value-preserving Hasher and a key Comparator that is equal to the supplied Comparator, use the tree's efficient find method. Otherwise, use the find method of the proxied backend.

Parameters:

key - The key to find.

mode - The search mode. The backend implementation must support the SearchMode.EXACT_MATCH mode (which makes this method behave exactly like DatabaseBackend.find(Object)). The backend may also support SearchMode.CLOSEST_ABOVE, SearchMode.CLOSEST_BELOW and SearchMode.CLOSEST_MATCH. If not, this method should throw an UnsupportedOperationException when called with any of those search modes. The backend implementation may also invent its own search modes.

The closest match is defined as the match that gives the lowest positive (SearchMode.CLOSEST_ABOVE), negative ( SearchMode.CLOSEST_BELOW) or absolute ( SearchMode.CLOSEST_MATCH) value from the comparator when comparing the keys in the database with the key to search for.

cmp - The Comparator used to compare keys.

Returns:

The position of the record that matches the search criteria, or null if no record matching the search criteria is found.

Since:

1.1

See Also:

DatabaseBackend.find(Object), DatabaseBackend.find(Comparable, SearchMode)

getValueFor

public V getValueFor(K key)

Description copied from interface: DatabaseBackend

Get the value for the record with the supplied key.

Parameters:

key - The record's key.

Returns:

The record's value or null if no record in the database has the supplied key.

removeAt

public void removeAt(P pos,
                     K key)

Description copied from interface: DatabaseBackend

Delete the record at the supplied position.

Parameters:

pos - The position of the record to delete.

key - The key for the record to remove.

remove

public V remove(K key)

Description copied from interface: DatabaseBackend

Delete the record with the supplied key and return its value.

Parameters:

key - The record's key.

Returns:

The record's value or null if no record in the database has the supplied key.

delete

public boolean delete(K key)

Description copied from interface: DatabaseBackend

Delete the record with the supplied key, if it exists.

Parameters:

key - The record's key.

Returns:

true if a record was deleted.

readKeyAt

public K readKeyAt(P pos)
            throws WrappedIOException,
                   IllegalStateException

Description copied from interface: DatabaseBackend

Read the key at the supplied position.

Parameters:

pos - The position of the record containing the key. This must be a valid position in the backend. It it is not, the behavior of this method is unspecified.

Returns:

The key.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.readValueAt(Object), DatabaseBackend.readRecordAt(Object)

readValueAt

public V readValueAt(P pos)

Description copied from interface: DatabaseBackend

Read the value at the specified position.

Parameters:

pos - The position of the record containing the value. This must be a valid position in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The value.

See Also:

DatabaseBackend.readKeyAt(Object), DatabaseBackend.readRecordAt(Object)

readRecordAt

public Record<K,V> readRecordAt(P pos)
                         throws WrappedIOException,
                                IllegalStateException

Description copied from interface: DatabaseBackend

Read the record (key and value) at the specified position.

Parameters:

pos - The position of the record. This must be a valid position in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The record.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.readKeyAt(Object), DatabaseBackend.readValueAt(Object)

keyIterator

public Iterator<K> keyIterator()

Description copied from class: AbstractDatabaseBackendProxy

Get a key iterator from the proxied backend.

Specified by:

keyIterator in interface DatabaseBackend<K,V,P>

Overrides:

keyIterator in class AbstractDatabaseBackendProxy<K,V,P>

Returns:

An Iterator over the database's keys.

getFirstPosition

public P getFirstPosition()
                   throws WrappedIOException,
                          IllegalStateException

Description copied from class: AbstractDatabaseBackendProxy

Call getFirstPosition on the proxied backend.

Specified by:

getFirstPosition in interface DatabaseBackend<K,V,P>

Overrides:

getFirstPosition in class AbstractDatabaseBackendProxy<K,V,P>

Returns:

The position of the first record in the backend, or null if the backend is empty.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getLastPosition(), DatabaseBackend.getNextPosition(Object), DatabaseBackend.getPreviousPosition(Object)

getLastPosition

public P getLastPosition()
                  throws WrappedIOException,
                         IllegalStateException

Description copied from class: AbstractDatabaseBackendProxy

Call getLastPosition on the proxied backend.

Specified by:

getLastPosition in interface DatabaseBackend<K,V,P>

Overrides:

getLastPosition in class AbstractDatabaseBackendProxy<K,V,P>

Returns:

The position of the last record in the backend, or null if the backend is empty.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getNextPosition(Object), DatabaseBackend.getPreviousPosition(Object)

getNextPosition

public P getNextPosition(P pos)
                  throws WrappedIOException,
                         IllegalStateException

Description copied from class: AbstractDatabaseBackendProxy

Call getNextPosition on the proxied backend.

Specified by:

getNextPosition in interface DatabaseBackend<K,V,P>

Overrides:

getNextPosition in class AbstractDatabaseBackendProxy<K,V,P>

Parameters:

pos - The position to search from. This must be the position of a record in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The position of the next key in the database backend, or null if the supplied position references the last record in the backend (the position returned from DatabaseBackend.getLastPosition()).

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getLastPosition(), DatabaseBackend.getPreviousPosition(Object)

getPreviousPosition

public P getPreviousPosition(P pos)
                      throws WrappedIOException,
                             IllegalStateException,
                             UnsupportedOperationException

Description copied from class: AbstractDatabaseBackendProxy

Call getPreviousPosition on the proxied backend.

Specified by:

getPreviousPosition in interface DatabaseBackend<K,V,P>

Overrides:

getPreviousPosition in class AbstractDatabaseBackendProxy<K,V,P>

Parameters:

pos - The position to search from. This must be the position of a record in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The position of the previous key in the database backend, or null if the supplied position references the first record in the backend (the position returned from DatabaseBackend.getFirstPosition()).

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

UnsupportedOperationException - If this method is not supported by the backend implementation.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getLastPosition(), DatabaseBackend.getNextPosition(Object)

clear

public void clear()

Description copied from interface: DatabaseBackend

Wipe out the entire database.

compact

public boolean compact()

Description copied from class: AbstractDatabaseBackendProxy

Call compact on the proxied backend.

Specified by:

compact in interface DatabaseBackend<K,V,P>

Overrides:

compact in class AbstractDatabaseBackendProxy<K,V,P>

Returns:

true if the backend was modified, false if not.

writeContentsTo

public long writeContentsTo(RandomAccess ra)

Description copied from class: AbstractDatabaseBackendProxy

Call writeContentsTo on the proxied backend.

Specified by:

writeContentsTo in interface DatabaseBackend<K,V,P>

Overrides:

writeContentsTo in class AbstractDatabaseBackendProxy<K,V,P>

Parameters:

ra - The RandomAccess to write to. It is not closed after writing.

Returns:

The size of the contents in bytes.

replaceContentsWith

public void replaceContentsWith(RandomAccess ra,
                                long dataSize)

Description copied from interface: DatabaseBackend

Replace the contents of the database with content read from the supplied RandomAccess. The database contents start at the RandomAccess' current position.

Parameters:

ra - The RandomAccess to read data from. It should not be closed after reading.

dataSize - The total size of the database data in bytes.

close

public void close()

Description copied from class: AbstractDatabaseBackendProxy

Subclasses overriding this method must call super.close().

Specified by:

close in interface DatabaseBackend<K,V,P>

Overrides:

close in class AbstractDatabaseBackendProxy<K,V,P>

finalize

protected void finalize()
                 throws Throwable

Overrides:

finalize in class AbstractDatabaseBackendProxy<K,V,P>

Throws:

Throwable