org.helidb.util.bplus
Class BPlusTree<K,V>

java.lang.Object
  org.helidb.util.bplus.BPlusTree<K,V>

Type Parameters:

K - The type of keys in the tree. If the keys are not Comparable, a Comparator must be used.

V - The type of values in the tree.

All Implemented Interfaces:

Iterable<Record<K,V>>

public class BPlusTree<K,V>
extends Object
implements Iterable<Record<K,V>>

This is a B+ Tree that stores data records (keys and values). B+ Trees provide fast key searches, record insertion and removal. For more information on B+ Tree properties, see this Wikipedia article.

Data is stored in nodes of configurable size. Leaf nodes contain the actual data records, and parent nodes contain information that makes it possible to search for records. Leaf nodes may optionally contain pointers to adjacent leaf nodes. In that case, iteration is enabled for the tree.

A NodeRepository is used for storing and retrieving the data nodes.

The size of the data nodes is determined by a NodeSizeStrategy.

The B+ Tree does not support null keys. It supports null values if the NodeRepository that it uses does so.

The B+ Tree is not safe for concurrent access by several threads. Clients must synchronize it externally.

Just like for a Map, take care if using mutable objects as keys and/or values. Modifying keys and values may have unpredictable consequences since the NodeRepository may have serialized the values to persistent storage, or it may have cached the values.

Implementation note for subclasses: The B+ Tree keeps track of key and value modifications by keeping a key and value revision number. This can be used to detect changes by iterators, for instance. See getCurrentKeyRevision() and getCurrentValueRevision().

Since:

1.0

Author:

Karl Gustafsson

See Also:

NodeRepository

In_jar:

helidb-core

Nested Class Summary

protected class	BPlusTree.AbstractBPlusTreeRecordIterator<T> This is the abstract base class for iterators that iterate over the tree's records.
protected class	BPlusTree.BPlusTreeKeyIterator An iterator over the tree's keys.
protected class	BPlusTree.BPlusTreeNodeIterator This is an Iterator over the B+ Tree's leaf nodes.
protected class	BPlusTree.BPlusTreeRecordIterator An iterator over the tree's records.
protected class	BPlusTree.BPlusTreeValueIterator An iterator over the tree's values.
protected static class	BPlusTree.NodeSearchResult<K,V> This simple value-only class is used to represent the search result when finding a node.

Constructor Summary

BPlusTree(NodeRepository<K> nr, Comparator<? super K> keyComparator, LogAdapterHolder lah)
Create a new B+ Tree.

BPlusTree(NodeRepository<K> nr, LogAdapterHolder lah)
Create a new B+ Tree that has Comparable keys.

Method Summary

protected void	assertNotClosed()
void	clear() Delete all records in the tree.
void	close() Close the tree.
boolean	compact() Defragment the tree to win back some disk space.
protected int	compareKeys(K k1, K k2) Compare the two keys.
boolean	containsKey(K key) Does the tree contain the supplied key?
V	delete(K key) Delete the record with the supplied key from the tree.
V	find(K key) Find the value for a key.
protected BPlusTreeLeafNode<K,V>	findLeftmostLeafNode() Find the leftmost leaf node in the tree.
protected BPlusTree.NodeSearchResult<K,V>	findNodeFor(K key, long searchPos, K keyOfFirstPointer, LinkedList<BPlusTreeNonLeafNode<K>> parentList) Find the leaf node where a record with the supplied key can be inserted.
KeyAndValue<K,V>	findRecord(K key, SearchMode mode) Find the record in the B+ Tree that matches the search key and the search mode most closely.
protected BPlusTreeLeafNode<K,V>	findRightmostLeafNode() Find the rightmost leaf node in the tree, i.e.
protected int	getCurrentKeyRevision() Get the current key revision.
protected int	getCurrentValueRevision() Get the current value revision.
KeyAndValue<K,V>	getFirstRecord() Get the tree's first record, i.e.
Comparator<? super K>	getKeyComparator() Get the Comparator used for establishing the ordering of the keys in the B+ Tree.
KeyAndValue<K,V>	getLastRecord() Get the tree's last record, i.e.
KeyAndValue<K,V>	getNextRecord(K key) Get the record after the record with the supplied key.
KeyAndValue<K,V>	getPreviousRecord(K key) Get the record before the record with the supplied key.
void	insert(K key, V value) Insert a new record into the tree.
boolean	insertOrReplace(K key, V value) If a record with the supplied key exists in the tree, update it with the new value, otherwise insert a new record.
boolean	isIteratorSupported() This method returns true if this B+ Tree supports iteration.
Iterator<Record<K,V>>	iterator() Get an Iterator for iterating over the tree's Record:s.
Iterator<K>	keyIterator() Get an Iterator for iterating over the tree's keys.
void	replace(K key, V newValue) Update a record with a new value.
void	replaceContentsWith(InputStream is, long dataSize) Replace the tree with contents read from the supplied InputStream .
int	size() Get the number of records in the tree.
String	toString()
Iterator<V>	valueIterator() Get an Iterator for iterating over the tree's values.
long	writeContentsTo(OutputStream os) Write the contents of the tree to the supplied OutputStream.

Methods inherited from class java.lang.Object

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

Constructor Detail

BPlusTree

public BPlusTree(NodeRepository<K> nr,
                 Comparator<? super K> keyComparator,
                 LogAdapterHolder lah)
          throws IllegalArgumentException

Create a new B+ Tree.

Parameters:

nr - The NodeRepository used for storing nodes to and retrieving nodes from the backing storage.

keyComparator - A Comparator for comparing keys. This must be set if the keys themselves are not Comparable. If they are, and this is set anyway, the Comparator is used.

lah - A log adapter holder.

Throws:

IllegalArgumentException - If the maximum number of records per leaf or non-leaf node, as reported by the node repository, is less than 2.

See Also:

BPlusTree(NodeRepository, LogAdapterHolder)

BPlusTree

public BPlusTree(NodeRepository<K> nr,
                 LogAdapterHolder lah)
          throws IllegalArgumentException

Create a new B+ Tree that has Comparable keys.

Parameters:

nr - The NodeRepository used for storing nodes to and retrieving nodes from the backing storage.

lah - A log adapter holder.

Throws:

IllegalArgumentException - If the maximum number of records per leaf or non-leaf node, as reported by the node repository, is less than 2.

See Also:

BPlusTree(NodeRepository, Comparator, LogAdapterHolder)

Method Detail

assertNotClosed

protected void assertNotClosed()
                        throws IllegalStateException

Throws:

IllegalStateException - If the B+ Tree has been closed.

See Also:

close()

getCurrentKeyRevision

protected int getCurrentKeyRevision()

Get the current key revision. The key revision is incremented every time one or several records are inserted in or deleted from the tree.

Returns:

The current key revision.

getCurrentValueRevision

protected int getCurrentValueRevision()

Get the current value revision. The value revision is incremented every time one or several records are inserted in, updated in or deleted from the tree.

Returns:

The current key revision.

getKeyComparator

public Comparator<? super K> getKeyComparator()

Get the Comparator used for establishing the ordering of the keys in the B+ Tree.

Returns:

The tree's Comparator, or null if the tree uses the natural ordering of the keys.

Since:

1.1

compareKeys

protected int compareKeys(K k1,
                          K k2)
                   throws NullPointerException

Compare the two keys. If the B+ Tree uses a Comparator, that is used. Otherwise, the keys are assumed to be Comparable.

Parameters:

k1 - The first key.

k2 - The second key.

Returns:

The comparison value. See Comparator.

Throws:

NullPointerException - If no Comparator is set for the tree and the keys are not Comparable.

findLeftmostLeafNode

protected BPlusTreeLeafNode<K,V> findLeftmostLeafNode()

Find the leftmost leaf node in the tree. The leftmost leaf node contains the key with the lowest value and is the starting point for all iterations over the tree.

Returns:

The tree's leftmost leaf node.

findRightmostLeafNode

protected BPlusTreeLeafNode<K,V> findRightmostLeafNode()

Find the rightmost leaf node in the tree, i.e. the tree node containing the highest key values.

Returns:

The tree's rightmost leaf node.

Since:

1.1

isIteratorSupported

public boolean isIteratorSupported()
                            throws IllegalStateException

This method returns true if this B+ Tree supports iteration. For it to do so, it is required that each leaf node has pointers to its two adjacent leaf nodes.

Throws:

IllegalStateException - If the tree is closed.

See Also:

keyIterator(), valueIterator(), iterator()

keyIterator

public Iterator<K> keyIterator()
                        throws IllegalStateException,
                               UnsupportedOperationException

Get an Iterator for iterating over the tree's keys. The keys are returned in increasing order based on the Comparator used by the tree, or in the keys' natural order if no Comparator is used.

Returns:

An iterator over the tree's keys.

Throws:

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If the tree does not support iteration. For it to support iteration, it is required that each leaf node stores pointers to its adjacent leaf nodes. This is configured in the tree's NodeRepository.

valueIterator

public Iterator<V> valueIterator()
                          throws IllegalStateException,
                                 UnsupportedOperationException

Get an Iterator for iterating over the tree's values. The values are returned in increasing order of their corresponding keys, based on the Comparator used by the tree, or the keys' natural order if no Comparator is used.

Returns:

An iterator over the tree's values.

Throws:

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If the tree does not support iteration. For it to support iteration, it is required that each leaf node stores pointers to its adjacent leaf nodes. This is configured in the tree's NodeRepository.

iterator

public Iterator<Record<K,V>> iterator()
                               throws IllegalStateException,
                                      UnsupportedOperationException

Get an Iterator for iterating over the tree's Record:s. The records are returned in increasing key order based on the Comparator used by the tree, or in the keys' natural order if no Comparator is used.

Specified by:

iterator in interface Iterable<Record<K,V>>

Returns:

An iterator over the tree's records.

Throws:

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If the tree does not support iteration. For it to support iteration, it is required that each leaf node stores pointers to its adjacent leaf nodes. This is configured in the tree's NodeRepository.

findNodeFor

protected BPlusTree.NodeSearchResult<K,V> findNodeFor(K key,
                                                      long searchPos,
                                                      K keyOfFirstPointer,
                                                      LinkedList<BPlusTreeNonLeafNode<K>> parentList)

Find the leaf node where a record with the supplied key can be inserted. The returned record may be full, in which case it needs to be split.

Parameters:

key - The key to insert.

searchPos - The position in the NodeRepository for the record to search from. Position 0 is the tree's root node.

keyOfFirstPointer - The key corresponding to the node's leftmost pointer (if any). For the root node, this is null.

parentList - A LinkedList (would have been a Deque in Java 6+) containing all parent nodes that the tree has had to traverse to find the current node it looks in. For the root node, this List is empty.

Returns:

A BPlusTree.NodeSearchResult.

insert

public void insert(K key,
                   V value)
            throws IllegalStateException,
                   KeyExistsException

Insert a new record into the tree.

Parameters:

key - The record's key.

value - The record's value.

Throws:

IllegalStateException - If the tree is closed.

KeyExistsException - If the key already exists in the tree.

replace

public void replace(K key,
                    V newValue)
             throws IllegalStateException,
                    KeyNotFoundException

Update a record with a new value.

Parameters:

key - The record's key.

newValue - The new value.

Throws:

IllegalStateException - If the tree is closed.

KeyNotFoundException - If there is no record with the supplied key in the tree.

insertOrReplace

public boolean insertOrReplace(K key,
                               V value)
                        throws IllegalStateException

If a record with the supplied key exists in the tree, update it with the new value, otherwise 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.

Throws:

IllegalStateException - If the tree is closed.

find

public V find(K key)
       throws IllegalStateException

Find the value for a key. If the key is not found, return null.

If the tree supports null values, use containsKey(Object) to determine if a key is set in the tree.

Be careful with modifying the values returned from this method. That may lead to unpredictable behavior from the tree.

Parameters:

key - The key to search for.

Returns:

The key's associated value, or null if the key was not found in the tree.

Throws:

IllegalStateException - If the tree is closed.

See Also:

getNextRecord(Object), getPreviousRecord(Object)

findRecord

public KeyAndValue<K,V> findRecord(K key,
                                   SearchMode mode)
                            throws IllegalStateException,
                                   UnsupportedOperationException

Find the record in the B+ Tree that matches the search key and the search mode most closely.

This method supports all search modes defined in SearchMode. If any of the CLOSEST_X methods are used, this tree must be iterable.

Parameters:

key - The search key.

mode - The search mode.

Returns:

The record in the B+ Tree that matches the search key and the search mode most closely. If no matching key is found, null is returned.

Throws:

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If an unsupported search mode is given.

Since:

1.1

See Also:

find(Object)

containsKey

public boolean containsKey(K key)
                    throws IllegalStateException

Does the tree contain the supplied key?

Parameters:

key - The key to search for.

Returns:

true if the tree contains the key.

Throws:

IllegalStateException - If the tree is closed.

delete

public V delete(K key)
         throws IllegalStateException

Delete the record with the supplied key from the tree. Return the record's value. If the key was not found, nothing is deleted and null is returned.

Parameters:

key - The key for the record to delete.

Returns:

The value for the deleted record, or null if the key was not found in the tree.

Throws:

IllegalStateException - If the tree is closed.

size

public int size()
         throws IllegalStateException

Get the number of records in the tree.

The first time that this method is called, the tree is traversed to count the records. The result is cached, so subsequent invocations should be much faster.

Returns:

The number of records in the tree.

Throws:

IllegalStateException - If the tree is closed.

clear

public void clear()
           throws IllegalStateException

Delete all records in the tree.

Throws:

IllegalStateException - If the tree is closed.

writeContentsTo

public long writeContentsTo(OutputStream os)
                     throws WrappedIOException,
                            IllegalStateException

Write the contents of the tree to the supplied OutputStream.

Parameters:

os - The stream to write to. The stream is not closed after writing.

Returns:

The number of bytes written.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

replaceContentsWith

public void replaceContentsWith(InputStream is,
                                long dataSize)
                         throws WrappedIOException,
                                IllegalStateException,
                                NotEnoughDataException

Replace the tree with contents read from the supplied InputStream .

Parameters:

is - The stream to read from. The stream is not closed after reading.

dataSize - The total number of bytes to read.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

NotEnoughDataException - If there is not enough data available in the stream.

getFirstRecord

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

Get the tree's first record, i.e. the record with the lowest key value.

Returns:

The leftmost record in the tree, or null if the tree is empty.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

Since:

1.1

See Also:

getLastRecord()

getLastRecord

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

Get the tree's last record, i.e. the record with the highest key value.

Returns:

The rightmost record in the tree, or null if the tree is empty.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

Since:

1.1

See Also:

getFirstRecord()

getNextRecord

public KeyAndValue<K,V> getNextRecord(K key)
                               throws WrappedIOException,
                                      IllegalStateException,
                                      UnsupportedOperationException

Get the record after the record with the supplied key. If the supplied record is not in the tree, return the record with the closest larger key value (if any) as determined by the key ordering in the tree.

This method requires that the tree is iterable.

Parameters:

key - The key to search for.

Returns:

The record after the record with the supplied key, if it exists in the tree, or the record with the closest larger key if the key does not exist in the tree. If there is no such record, null is returned.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If the tree does not support iteration.

Since:

1.1

See Also:

getPreviousRecord(Object)

getPreviousRecord

public KeyAndValue<K,V> getPreviousRecord(K key)
                                   throws WrappedIOException,
                                          IllegalStateException,
                                          UnsupportedOperationException

Get the record before the record with the supplied key. If the supplied record is not in the tree, return the record with the closest smaller key value (if any) as determined by the key ordering in the tree.

This method requires that the tree is iterable.

Parameters:

key - The key to search for.

Returns:

The record before the record with the supplied key, if it exists in the tree, or the record with the closest smaller key if the key does not exist in the tree. If there is no such record, null is returned.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the tree is closed.

UnsupportedOperationException - If the tree does not support iteration.

Since:

1.1

See Also:

getNextRecord(Object)

compact

public boolean compact()
                throws IllegalStateException

Defragment the tree to win back some disk space.

This operation involves traversing the whole tree, so it may be slow for large trees.

Returns:

true if the tree was compacted, or false if there was nothing to compact right now.

Throws:

IllegalStateException - If the tree is closed.

close

public void close()

Close the tree. This also closes the tree's NodeRepository.

This method can be called several times. All invocations after the first does nothing.

toString

public String toString()

Overrides:

toString in class Object