jdbm.btree

Class BTree<K,V>

java.lang.Object

jdbm.btree.BTree<K,V>

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable

public class BTree<K,V>
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

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.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) class	BTree.EmptyBrowser PRIVATE INNER CLASS Browser returning no element.
(package private) class	BTree.MetaRoot Used to point to the root page that the reader needs based on the reader's read action context.

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.concurrent.locks.Lock	bigLock Big lock snychronizing all actions
private BPage<K,V>	bpageSerializer Serializer used for BPages of this tree
(package private) int	bTreeHeight Height of the B+Tree.
(package private) java.util.Comparator<K>	comparator Comparator used to index entries.
private static boolean	DEBUG
static int	DEFAULT_SIZE Default page size (number of entries per node)
private boolean	isActionCapable TRUE if underlying record manager is snapshot capable
protected Serializer	keySerializer Serializer used to serialize index keys (optional)
private BTree.MetaRoot	metaRoot Meta root used to access versions of Btree root
protected java.util.concurrent.atomic.AtomicInteger	nbEntries Total number of entries in the BTree
protected int	pageSize Number of entries in each BPage.
private long	recordId This BTree's record ID in the PageManager.
protected RecordManager	recordManager Page manager used to persist changes in BPages
private long	rootId Record id of the root BPage
(package private) static long	serialVersionUID Version id for serialization.
protected Serializer	valueSerializer Serializer used to serialize index values (optional)

Constructor Summary

Constructors

Constructor and Description
BTree() No-argument constructor used by serialization.
BTree(RecordManager recman, java.util.Comparator<K> comparator) Create a new persistent BTree, with 16 entries per node.
BTree(RecordManager recman, java.util.Comparator<K> comparator, Serializer keySerializer, Serializer valueSerializer) Create a new persistent BTree, with 16 entries per node.
BTree(RecordManager recman, java.util.Comparator<K> comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize) Create a new persistent BTree with the given number of entries per node.

Method Summary

Modifier and Type	Method and Description
(package private) void	abortAction(ActionContext context)
(package private) ActionContext	beginAction(boolean readOnly, java.lang.String whoStarted)
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.
(package private) BPage<K,V>	copyOnWrite(BPage<K,V> page)
private BTree.MetaRoot	copyOnWrite(BTree.MetaRoot oldMetaRoot)
private void	createInstance(RecordManager recordManager, java.util.Comparator<K> comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize) The real BTree constructor.
(package private) void	endAction(ActionContext context)
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()
(package private) BTree.MetaRoot	getMetaRoot() Returns the meta root that can be used to fetch the root page
long	getRecordId() Return the persistent record identifier of the BTree.
(package private) BPage<K,V>	getRoot()
(package private) BPage<K,V>	getRoot(BTree.MetaRoot meta)
java.lang.Object	insert(K key, V value, boolean replace) Insert an entry in the BTree.
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.
(package private) void	setAsCurrentAction(ActionContext context)
void	setPageSize(int pageSize)
void	setValueSerializer(Serializer valueSerializer)
int	size() Return the number of entries (size) of the BTree.
java.lang.String	toString()
(package private) void	unsetAsCurrentAction(ActionContext context)
private void	updateMetaRoot(long newRootId, int newTreeHeight)
void	writeExternal(java.io.ObjectOutput out) Implement Externalizable interface.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

serialVersionUID

static final long serialVersionUID

Version id for serialization.

See Also:

Constant Field Values

DEFAULT_SIZE

public static final int DEFAULT_SIZE

Default page size (number of entries per node)

See Also:

Constant Field Values

recordManager

protected transient RecordManager recordManager

Page manager used to persist changes in BPages

recordId

private transient long recordId

This BTree's record ID in the PageManager.

comparator

java.util.Comparator<K> comparator

Comparator used to index entries.

keySerializer

protected Serializer keySerializer

Serializer used to serialize index keys (optional)

valueSerializer

protected Serializer valueSerializer

Serializer used to serialize index values (optional)

bTreeHeight

int bTreeHeight

Height of the B+Tree. This is the number of BPages you have to traverse to get to a leaf BPage, starting from the root.

rootId

private long rootId

Record id of the root BPage

pageSize

protected int pageSize

Number of entries in each BPage.

nbEntries

protected java.util.concurrent.atomic.AtomicInteger nbEntries

Total number of entries in the BTree

bpageSerializer

private transient BPage<K,V> bpageSerializer

Serializer used for BPages of this tree

isActionCapable

private transient boolean isActionCapable

TRUE if underlying record manager is snapshot capable

bigLock

private transient java.util.concurrent.locks.Lock bigLock

Big lock snychronizing all actions

metaRoot

private transient BTree.MetaRoot metaRoot

Meta root used to access versions of Btree root

Constructor Detail

BTree

public BTree()

No-argument constructor used by serialization.

BTree

public BTree(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

BTree

public BTree(RecordManager recman,
             java.util.Comparator<K> 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

BTree

public BTree(RecordManager recman,
             java.util.Comparator<K> 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

Method Detail

createInstance

private void createInstance(RecordManager recordManager,
                            java.util.Comparator<K> comparator,
                            Serializer keySerializer,
                            Serializer valueSerializer,
                            int pageSize)
                     throws java.io.IOException

The real BTree constructor.

Throws:

java.io.IOException

setPageSize

public void setPageSize(int pageSize)

load

public 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

insert

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

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 browsing results.

Parameters:

key - Key used to position the browser. If null, the browser will be positioned after the last entry of the BTree. (Null is considered to be an "infinite" key)

Returns:

Browser positioned just before the given key.

Throws:

java.io.IOException

size

public int size()

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

getRecordId

public long getRecordId()

Return the persistent record identifier of the BTree.

getRoot

BPage<K,V> getRoot()
            throws java.io.IOException

Returns:

the root BPage, or null if it doesn't exist.

Throws:

java.io.IOException

getRoot

BPage<K,V> getRoot(BTree.MetaRoot meta)
            throws java.io.IOException

Parameters:

meta - The root to search for

Returns:

the root BPage, or null if it doesn't exist.

Throws:

java.io.IOException

getMetaRoot

BTree.MetaRoot getMetaRoot()
                    throws java.io.IOException

Returns the meta root that can be used to fetch the root page

Returns:

meta root The meta root to search for

Throws:

java.io.IOException - If we had an exception during the fetch operation

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

setValueSerializer

public void setValueSerializer(Serializer valueSerializer)

getComparator

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

Returns:

the comparator

setAsCurrentAction

void setAsCurrentAction(ActionContext context)

unsetAsCurrentAction

void unsetAsCurrentAction(ActionContext context)

beginAction

ActionContext beginAction(boolean readOnly,
                          java.lang.String whoStarted)

endAction

void endAction(ActionContext context)

abortAction

void abortAction(ActionContext context)

copyOnWrite

BPage<K,V> copyOnWrite(BPage<K,V> page)
                throws java.io.IOException

Throws:

java.io.IOException

copyOnWrite

private BTree.MetaRoot copyOnWrite(BTree.MetaRoot oldMetaRoot)

updateMetaRoot

private void updateMetaRoot(long newRootId,
                            int newTreeHeight)
                     throws java.io.IOException

Throws:

java.io.IOException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object