jdbm.btree
Class BTree

java.lang.Object
  extended by jdbm.btree.BTree
All Implemented Interfaces:
java.io.Externalizable, java.io.Serializable

public class BTree
extends java.lang.Object
implements java.io.Externalizable

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
 TupleBrowser browse()
          Get a browser initially positioned at the beginning of the BTree.
 TupleBrowser browse(java.lang.Object key)
          Get a browser initially positioned just before the given key.
static BTree createInstance(RecordManager recman, java.util.Comparator comparator)
          Create a new persistent BTree, with 16 entries per node.
static BTree createInstance(RecordManager recman, java.util.Comparator comparator, Serializer keySerializer, Serializer valueSerializer)
          Create a new persistent BTree, with 16 entries per node.
static BTree createInstance(RecordManager recman, java.util.Comparator comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize)
          Create a new persistent BTree with the given number of entries per node.
 java.lang.Object find(java.lang.Object key)
          Find the value associated with the given key.
 Tuple findGreaterOrEqual(java.lang.Object key)
          Find the value associated with the given key, or the entry immediately following this key in the ordered BTree.
 long getRecid()
          Return the persistent record identifier of the BTree.
 java.lang.Object insert(java.lang.Object key, java.lang.Object value, boolean replace)
          Insert an entry in the BTree.
static BTree load(RecordManager recman, long recid)
          Load a persistent BTree.
 void readExternal(java.io.ObjectInput in)
          Implement Externalizable interface.
 java.lang.Object remove(java.lang.Object key)
          Remove an entry with the given key from the BTree.
 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

createInstance

public static BTree createInstance(RecordManager recman,
                                   java.util.Comparator 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 BTree createInstance(RecordManager recman,
                                   java.util.Comparator comparator,
                                   Serializer keySerializer,
                                   Serializer 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 BTree createInstance(RecordManager recman,
                                   java.util.Comparator comparator,
                                   Serializer keySerializer,
                                   Serializer 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 BTree 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

insert

public java.lang.Object insert(java.lang.Object key,
                               java.lang.Object 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 java.lang.Object remove(java.lang.Object 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 java.lang.Object find(java.lang.Object key)
                      throws java.io.IOException
Find the value associated with the given key.

Parameters:
key - Lookup key.
Returns:
Value associated with the key, or null if not found.
Throws:
java.io.IOException

findGreaterOrEqual

public Tuple findGreaterOrEqual(java.lang.Object 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 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 browse(java.lang.Object 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


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