jdbm.btree
Class BTree

java.lang.Object
  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