org.helidb.backend.bpluscrs
Class ConstantRecordSizeBPlusTreeBackend<K,V>

java.lang.Object
  org.helidb.backend.AbstractDatabaseBackend<K,V,KeyAndValue<K,V>>
      org.helidb.backend.bpluscrs.ConstantRecordSizeBPlusTreeBackend<K,V>

Type Parameters:

K - The types of keys in the backend. The keys must be of a fixed size when serialized.

V - The types of values in the backend. The values must be of a fixed size when serialized.

All Implemented Interfaces:

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

public class ConstantRecordSizeBPlusTreeBackend<K,V>
extends AbstractDatabaseBackend<K,V,KeyAndValue<K,V>>

This DatabaseBackend uses a B+ Tree for storing its records. Its keys and values must be of a fixed size when serialized. Keys must either be Comparable with each other, or a separate key Comparator must be supplied when creating the backend.

This implementation provides fast retrieval, updating and deleting of its data.

Cursor:s, key, value and record iterators created by this backend return records in the order defined by the key Comparator used, or in the keys' natural order if no Comparator is used. (See Comparable.) This behavior may be modified if an index is used with the database.

Since:

1.0

Author:

Karl Gustafsson

See Also:

Comparable, Comparator, ConstantRecordSizeBPlusTreeBackendFactory

In_jar:

helidb-crs_bplus_backend

Constructor Summary

ConstantRecordSizeBPlusTreeBackend(NodeRepository<K> nr, boolean readOnly, Comparator<? super K> cmp, LogAdapterHolder lah)
Constructor.

ConstantRecordSizeBPlusTreeBackend(NodeRepository<K> nr, boolean readOnly, LogAdapterHolder lah)
Constructor.

Method Summary

protected void	assertNotClosed() Subclasses implement this to throw an IllegalStateException if the database backend is closed.
void	clear() Wipe out the entire database.
void	close() Close this database backend and release all resources associated with it (close files and release locks, for instance).
boolean	compact() Compact the backing database file if it has become fragmented.
boolean	delete(K key) Delete the record with the supplied key, if it exists.
protected void	finalize() Close the backend before discarding the object.
KeyAndValue<K,V>	find(Comparable<K> key, SearchMode mode) If the B+ Tree uses the natural ordering of its (Comparable) keys (i.e.
KeyAndValue<K,V>	find(K key) Find the position of the record with the supplied key in the database backend.
KeyAndValue<K,V>	find(K key, SearchMode mode, Comparator<? super K> cmp) If the supplied Comparator is equal to the Comparator used by the B+ Tree, the tree's fast find method is used.
void	forEachKey(ForEachKeyCallback<K,KeyAndValue<K,V>> callback) For each key in the database, call the callback object.
KeyAndValue<K,V>	getFirstPosition() Get the position of the "first" record in the backend.
Set<K>	getKeys() Return an immutable Set containing all keys in the database.
KeyAndValue<K,V>	getLastPosition() Get the position of the "last" record in the backend.
KeyAndValue<K,V>	getNextPosition(KeyAndValue<K,V> pos) Get the position of the "next" record in the backend, relative to the record at the supplied position.
KeyAndValue<K,V>	getPreviousPosition(KeyAndValue<K,V> pos) Get the position of the "previous" record in the backend, relative to the record at the supplied position.
Set<Record<K,V>>	getRecords() Return an immutable Set containing all database records (keys and values).
V	getValueFor(K key) Get the value for the record with the supplied key.
Collection<V>	getValues() Return an immutable Collection containing all values in the database.
KeyAndValue<K,V>	insert(K key, V value) Insert a new record in the database.
KeyAndValue<K,V>	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<Record<K,V>>	iterator()
Iterator<K>	keyIterator() Get an iterator for all keys in the database.
K	readKeyAt(KeyAndValue<K,V> pos) Read the key at the supplied position.
Record<K,V>	readRecordAt(KeyAndValue<K,V> pos) Read the record (key and value) at the specified position.
V	readValueAt(KeyAndValue<K,V> 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(KeyAndValue<K,V> 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<KeyAndValue<K,V>>	update(K key, V value) Update an existing record with a new value.
KeyAndValue<K,V>	updateAt(KeyAndValue<K,V> pos, K key, V value) Update the record at the supplied position with the new value.
Iterator<V>	valueIterator() Get an iterator for all the values in the database.
long	writeContentsTo(RandomAccess ra) Write the contents of the entire database to the current position in the supplied RandomAccess.

Methods inherited from class org.helidb.backend.AbstractDatabaseBackend

addRecordMoveListener, getContentsVersion, hasRecordMoveListeners, notifyRecordMoveListeners, removeRecordMoveListener, updateContentsVersion

Methods inherited from class java.lang.Object

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

Constructor Detail

ConstantRecordSizeBPlusTreeBackend

public ConstantRecordSizeBPlusTreeBackend(NodeRepository<K> nr,
                                          boolean readOnly,
                                          LogAdapterHolder lah)
                                   throws IllegalArgumentException

Constructor.

Parameters:

nr - A NodeRepository for the B+ Tree.

readOnly - Should the backend be used read only?

lah - A log adapter holder.

Throws:

IllegalArgumentException - If the NodeRepository does not support iteration.

ConstantRecordSizeBPlusTreeBackend

public ConstantRecordSizeBPlusTreeBackend(NodeRepository<K> nr,
                                          boolean readOnly,
                                          Comparator<? super K> cmp,
                                          LogAdapterHolder lah)
                                   throws IllegalArgumentException

Constructor.

Parameters:

nr - A NodeRepository for the B+ Tree.

readOnly - Should the backend be used read only?

cmp - A Comparator for establishing the key ordering.

lah - A log adapter holder.

Throws:

IllegalArgumentException - If the NodeRepository does not support iteration.

Since:

1.1

Method Detail

assertNotClosed

protected void assertNotClosed()
                        throws IllegalStateException

Description copied from class: AbstractDatabaseBackend

Subclasses implement this to throw an IllegalStateException if the database backend is closed.

Specified by:

assertNotClosed in class AbstractDatabaseBackend<K,V,KeyAndValue<K,V>>

Throws:

IllegalStateException - Thrown if the database backend is closed.

iterator

public Iterator<Record<K,V>> iterator()

keyIterator

public Iterator<K> keyIterator()

Description copied from interface: DatabaseBackend

Get an iterator for all keys in the database. The iterator may or may not return the keys in a specific order. See the backend implementation documentation.

If the database is modified after calling this method, the methods of the Iterator returned will throw ConcurrentModificationException

Returns:

An Iterator over the database's keys.

valueIterator

public Iterator<V> valueIterator()

Description copied from interface: DatabaseBackend

Get an iterator for all the values in the database.

If the database is modified after calling this method, the methods of the Iterator returned will throw ConcurrentModificationException

Returns:

An Iterator over the database's values.

forEachKey

public void forEachKey(ForEachKeyCallback<K,KeyAndValue<K,V>> callback)

Description copied from interface: DatabaseBackend

For each key in the database, call the callback object.

This can for instance be used for building indices for the database.

Parameters:

callback - The callback object to call for each key.

find

public KeyAndValue<K,V> 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 KeyAndValue<K,V> find(Comparable<K> key,
                             SearchMode mode)

If the B+ Tree uses the natural ordering of its (Comparable) keys (i.e. it does not use a custom Comparator), this method uses the fast find methods of the B+ Tree. Otherwise it uses the slower inherited method.

Specified by:

find in interface DatabaseBackend<K,V,KeyAndValue<K,V>>

Overrides:

find in class AbstractDatabaseBackend<K,V,KeyAndValue<K,V>>

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 KeyAndValue<K,V> find(K key,
                             SearchMode mode,
                             Comparator<? super K> cmp)

If the supplied Comparator is equal to the Comparator used by the B+ Tree, the tree's fast find method is used. Otherwise the slower inherited method is used.

Specified by:

find in interface DatabaseBackend<K,V,KeyAndValue<K,V>>

Overrides:

find in class AbstractDatabaseBackend<K,V,KeyAndValue<K,V>>

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.

readValueAt

public V readValueAt(KeyAndValue<K,V> 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)

insert

public KeyAndValue<K,V> 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 KeyAndValue<K,V> 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.

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.

update

public Pair<KeyAndValue<K,V>> 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).

removeAt

public void removeAt(KeyAndValue<K,V> 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.

updateAt

public KeyAndValue<K,V> updateAt(KeyAndValue<K,V> 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.

getRecords

public Set<Record<K,V>> getRecords()

Description copied from interface: DatabaseBackend

Return an immutable Set containing all database records (keys and values).

Returns:

An immutable Set containing all database records. If the database is empty, this method returns an empty Set.

getKeys

public Set<K> getKeys()

Description copied from interface: DatabaseBackend

Return an immutable Set containing all keys in the database.

Returns:

An immutable Set containing all keys in the database. If the database is empty, this method returns an empty Set.

getValues

public Collection<V> getValues()

Description copied from interface: DatabaseBackend

Return an immutable Collection containing all values in the database.

Returns:

An immutable Collection containing all values in the database. If the database is empty, this method returns an empty Collection.

clear

public void clear()

Description copied from interface: DatabaseBackend

Wipe out the entire database.

compact

public boolean compact()

Description copied from interface: DatabaseBackend

Compact the backing database file if it has become fragmented.

Returns:

true if the backend was modified, false if not.

writeContentsTo

public long writeContentsTo(RandomAccess ra)

Description copied from interface: DatabaseBackend

Write the contents of the entire database to the current position in the supplied RandomAccess.

After writing, the current position of the RandomAccess should be at the end of the written data.

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.

getFirstPosition

public KeyAndValue<K,V> getFirstPosition()
                                  throws WrappedIOException,
                                         IllegalStateException

Description copied from interface: DatabaseBackend

Get the position of the "first" record in the backend. The meaning of "first" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the first key in the sorted set of keys.

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 KeyAndValue<K,V> getLastPosition()
                                 throws WrappedIOException,
                                        IllegalStateException

Description copied from interface: DatabaseBackend

Get the position of the "last" record in the backend. The meaning of "last" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the last key in the sorted set of keys.

Some backend implementations do not support this method. They let this method throw an UnsupportedOperationException.

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 KeyAndValue<K,V> getNextPosition(KeyAndValue<K,V> pos)
                                 throws WrappedIOException,
                                        IllegalStateException

Description copied from interface: DatabaseBackend

Get the position of the "next" record in the backend, relative to the record at the supplied position. The meaning of "next" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the next key, relative to the key at the supplied position.

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 KeyAndValue<K,V> getPreviousPosition(KeyAndValue<K,V> pos)
                                     throws WrappedIOException,
                                            IllegalStateException,
                                            UnsupportedOperationException

Description copied from interface: DatabaseBackend

Get the position of the "previous" record in the backend, relative to the record at the supplied position. The meaning of "previous" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the previous key, relative to the key at the supplied position.

Some backend implementations do not support this method. They let this method throw an UnsupportedOperationException.

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)

readKeyAt

public K readKeyAt(KeyAndValue<K,V> 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)

readRecordAt

public Record<K,V> readRecordAt(KeyAndValue<K,V> 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)

close

public void close()

Description copied from interface: DatabaseBackend

Close this database backend and release all resources associated with it (close files and release locks, for instance).

finalize

protected void finalize()
                 throws Throwable

Close the backend before discarding the object.

Overrides:

finalize in class Object

Throws:

Throwable