jdbm.btree
Class BTree<K,V>

java.lang.Object
  extended by jdbm.btree.BTree<K,V>
All Implemented Interfaces:
java.io.Externalizable, java.io.Serializable, JdbmBase<K,V>

public class BTree<K,V>
extends java.lang.Object
implements java.io.Externalizable, JdbmBase<K,V>

B+Tree persistent indexing data structure. B+Trees are optimized for block-based, random I/O storage because they store multiple keys on one tree node (called BPage). In addition, the leaf nodes directly contain (inline) the values associated with the keys, allowing a single (or sequential) disk read of all the values on the page.

B+Trees are n-airy, yeilding log(N) search cost. They are self-balancing, preventing search performance degradation when the size of the tree grows.

Keys and associated values must be Serializable objects. The user is responsible to supply a serializable Comparator object to be used for the ordering of entries, which are also called Tuple. The B+Tree allows traversing the keys in forward and reverse order using a TupleBrowser obtained from the browse() methods.

This implementation does not directly support duplicate keys, but it is possible to handle duplicates by inlining or referencing an object collection as a value.

There is no limit on key size or value size, but it is recommended to keep both as small as possible to reduce disk I/O. This is especially true for the key size, which impacts all non-leaf BPage objects.

Version:
$Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $
Author:
Alex Boisvert
See Also:
Serialized Form

Field Summary
static int DEFAULT_SIZE
          Default page size (number of entries per node)
 
Constructor Summary
BTree()
          No-argument constructor used by serialization.
 
Method Summary
 void addRecordListener(RecordListener<K,V> listener)
          add RecordListener which is notified about record changes
 BTreeSortedMap<K,V> asMap()
           
 TupleBrowser<K,V> browse()
          Get a browser initially positioned at the beginning of the BTree.
 TupleBrowser<K,V> browse(K key)
          Get a browser initially positioned just before the given key.
static
<K extends java.lang.Comparable,V>
BTree<K,V>
createInstance(RecordManager recman)
          Create a new persistent BTree, with 16 entries per node.
static
<K,V> BTree<K,V>
createInstance(RecordManager recman, java.util.Comparator<K> comparator)
          Create a new persistent BTree, with 16 entries per node.
static
<K,V> BTree<K,V>
createInstance(RecordManager recman, java.util.Comparator<K> comparator, Serializer<K> keySerializer, Serializer<V> valueSerializer)
          Create a new persistent BTree, with 16 entries per node.
static
<K,V> BTree<K,V>
createInstance(RecordManager recman, java.util.Comparator<K> comparator, Serializer<K> keySerializer, Serializer<V> valueSerializer, int pageSize)
          Create a new persistent BTree with the given number of entries per node.
 void delete()
          Deletes all BPages in this BTree, then deletes the tree from the record manager
 V find(K key)
          Find the value associated with the given key.
 Tuple<K,V> findGreaterOrEqual(K key)
          Find the value associated with the given key, or the entry immediately following this key in the ordered BTree.
 java.util.Comparator<K> getComparator()
           
 Serializer<K> getKeySerializer()
           
 java.util.concurrent.locks.ReadWriteLock getLock()
          Get the ReadWriteLock associated with this BTree.
 long getRecid()
          Return the persistent record identifier of the BTree.
 RecordManager getRecordManager()
           
 Serializer<V> getValueSerializer()
           
 V insert(K key, V value, boolean replace)
          Insert an entry in the BTree.
static
<K,V> BTree<K,V>
load(RecordManager recman, long recid)
          Load a persistent BTree.
 void readExternal(java.io.ObjectInput in)
          Implement Externalizable interface.
 V remove(K key)
          Remove an entry with the given key from the BTree.
 void removeRecordListener(RecordListener<K,V> listener)
          remove RecordListener which is notified about record changes
 void setKeySerializer(Serializer<K> keySerializer)
           
 void setValueSerializer(Serializer<V> valueSerializer)
           
 int size()
          Return the number of entries (size) of the BTree.
 void writeExternal(java.io.ObjectOutput out)
          Implement Externalizable interface.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_SIZE

public static final int DEFAULT_SIZE
Default page size (number of entries per node)

See Also:
Constant Field Values
Constructor Detail

BTree

public BTree()
No-argument constructor used by serialization.

Method Detail

getKeySerializer

public Serializer<K> getKeySerializer()

setKeySerializer

public void setKeySerializer(Serializer<K> keySerializer)

getValueSerializer

public Serializer<V> getValueSerializer()

setValueSerializer

public void setValueSerializer(Serializer<V> valueSerializer)

createInstance

public static <K,V> BTree<K,V> createInstance(RecordManager recman,
                                              java.util.Comparator<K> comparator)
                                 throws java.io.IOException
Create a new persistent BTree, with 16 entries per node.

Parameters:
recman - Record manager used for persistence.
comparator - Comparator used to order index entries
Throws:
java.io.IOException

createInstance

public static <K extends java.lang.Comparable,V> BTree<K,V> createInstance(RecordManager recman)
                                                              throws java.io.IOException
Create a new persistent BTree, with 16 entries per node.

Parameters:
recman - Record manager used for persistence.
comparator - Comparator used to order index entries
Throws:
java.io.IOException

createInstance

public static <K,V> BTree<K,V> createInstance(RecordManager recman,
                                              java.util.Comparator<K> comparator,
                                              Serializer<K> keySerializer,
                                              Serializer<V> valueSerializer)
                                 throws java.io.IOException
Create a new persistent BTree, with 16 entries per node.

Parameters:
recman - Record manager used for persistence.
keySerializer - Serializer used to serialize index keys (optional)
valueSerializer - Serializer used to serialize index values (optional)
comparator - Comparator used to order index entries
Throws:
java.io.IOException

createInstance

public static <K,V> BTree<K,V> createInstance(RecordManager recman,
                                              java.util.Comparator<K> comparator,
                                              Serializer<K> keySerializer,
                                              Serializer<V> valueSerializer,
                                              int pageSize)
                                 throws java.io.IOException
Create a new persistent BTree with the given number of entries per node.

Parameters:
recman - Record manager used for persistence.
comparator - Comparator used to order index entries
keySerializer - Serializer used to serialize index keys (optional)
valueSerializer - Serializer used to serialize index values (optional)
pageSize - Number of entries per page (must be even).
Throws:
java.io.IOException

load

public static <K,V> BTree<K,V> load(RecordManager recman,
                                    long recid)
                       throws java.io.IOException
Load a persistent BTree.

Parameters:
recman - RecordManager used to store the persistent btree
recid - Record id of the BTree
Throws:
java.io.IOException

getLock

public java.util.concurrent.locks.ReadWriteLock getLock()
Get the ReadWriteLock associated with this BTree. This should be used with browsing operations to ensure consistency.

Returns:

insert

public V insert(K key,
                V value,
                boolean replace)
         throws java.io.IOException
Insert an entry in the BTree.

The BTree cannot store duplicate entries. An existing entry can be replaced using the replace flag. If an entry with the same key already exists in the BTree, its value is returned.

Parameters:
key - Insert key
value - Insert value
replace - Set to true to replace an existing key-value pair.
Returns:
Existing value, if any.
Throws:
java.io.IOException

remove

public V remove(K key)
         throws java.io.IOException
Remove an entry with the given key from the BTree.

Parameters:
key - Removal key
Returns:
Value associated with the key, or null if no entry with given key existed in the BTree.
Throws:
java.io.IOException

find

public V find(K key)
       throws java.io.IOException
Find the value associated with the given key.

Specified by:
find in interface JdbmBase<K,V>
Parameters:
key - Lookup key.
Returns:
Value associated with the key, or null if not found.
Throws:
java.io.IOException

findGreaterOrEqual

public Tuple<K,V> findGreaterOrEqual(K key)
                              throws java.io.IOException
Find the value associated with the given key, or the entry immediately following this key in the ordered BTree.

Parameters:
key - Lookup key.
Returns:
Value associated with the key, or a greater entry, or null if no greater entry was found.
Throws:
java.io.IOException

browse

public TupleBrowser<K,V> browse()
                         throws java.io.IOException
Get a browser initially positioned at the beginning of the BTree.

WARNING: �If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.

Returns:
Browser positionned at the beginning of the BTree.
Throws:
java.io.IOException

browse

public TupleBrowser<K,V> browse(K key)
                         throws java.io.IOException
Get a browser initially positioned just before the given key.

WARNING: �If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.

Parameters:
key - Key used to position the browser. If null, the browser will be positionned after the last entry of the BTree. (Null is considered to be an "infinite" key)
Returns:
Browser positionned just before the given key.
Throws:
java.io.IOException

size

public int size()
Return the number of entries (size) of the BTree.


getRecid

public long getRecid()
Return the persistent record identifier of the BTree.


readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
Implement Externalizable interface.

Specified by:
readExternal in interface java.io.Externalizable
Throws:
java.io.IOException
java.lang.ClassNotFoundException

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException
Implement Externalizable interface.

Specified by:
writeExternal in interface java.io.Externalizable
Throws:
java.io.IOException

asMap

public BTreeSortedMap<K,V> asMap()

addRecordListener

public void addRecordListener(RecordListener<K,V> listener)
add RecordListener which is notified about record changes

Specified by:
addRecordListener in interface JdbmBase<K,V>
Parameters:
listener -

removeRecordListener

public void removeRecordListener(RecordListener<K,V> listener)
remove RecordListener which is notified about record changes

Specified by:
removeRecordListener in interface JdbmBase<K,V>
Parameters:
listener -

getRecordManager

public RecordManager getRecordManager()
Specified by:
getRecordManager in interface JdbmBase<K,V>
Returns:
underlying record manager

getComparator

public java.util.Comparator<K> getComparator()

delete

public void delete()
            throws java.io.IOException
Deletes all BPages in this BTree, then deletes the tree from the record manager

Throws:
java.io.IOException


Cees de Groot (C) 2000. All rights reserved http://jdbm.sourceforge.net