public class BTree
extends java.lang.Object
implements java.io.Externalizable
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.
Modifier and Type | Class and Description |
---|---|
(package private) static class |
BTree.EmptyBrowser
PRIVATE INNER CLASS
Browser returning no element.
|
Modifier and Type | Field and Description |
---|---|
protected java.util.Comparator |
_comparator
Comparator used to index entries.
|
protected int |
_entries
Total number of entries in the BTree
|
protected Serializer |
_keySerializer
Serializer used to serialize index keys (optional)
|
protected int |
_pageSize
Number of entries in each BPage.
|
protected RecordManager |
_recman
Page manager used to persist changes in BPages
|
protected Serializer |
_valueSerializer
Serializer used to serialize index values (optional)
|
static int |
DEFAULT_SIZE
Default page size (number of entries per node)
|
(package private) static long |
serialVersionUID
Version id for serialization.
|
Constructor and Description |
---|
BTree()
No-argument constructor used by serialization.
|
Modifier and Type | Method and Description |
---|---|
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.
|
static final long serialVersionUID
public static final int DEFAULT_SIZE
protected transient RecordManager _recman
protected java.util.Comparator _comparator
protected Serializer _keySerializer
protected Serializer _valueSerializer
protected int _pageSize
protected int _entries
public static BTree createInstance(RecordManager recman, java.util.Comparator comparator) throws java.io.IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entriesjava.io.IOException
public static BTree createInstance(RecordManager recman, java.util.Comparator comparator, Serializer keySerializer, Serializer valueSerializer) throws java.io.IOException
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 entriesjava.io.IOException
public static BTree createInstance(RecordManager recman, java.util.Comparator comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize) throws java.io.IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entrieskeySerializer
- Serializer used to serialize index keys (optional)valueSerializer
- Serializer used to serialize index values (optional)pageSize
- Number of entries per page (must be even).java.io.IOException
public static BTree load(RecordManager recman, long recid) throws java.io.IOException
recman
- RecordManager used to store the persistent btreerecid
- Record id of the BTreejava.io.IOException
public java.lang.Object insert(java.lang.Object key, java.lang.Object value, boolean replace) throws java.io.IOException
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.
key
- Insert keyvalue
- Insert valuereplace
- Set to true to replace an existing key-value pair.java.io.IOException
public java.lang.Object remove(java.lang.Object key) throws java.io.IOException
key
- Removal keyjava.io.IOException
public java.lang.Object find(java.lang.Object key) throws java.io.IOException
key
- Lookup key.java.io.IOException
public Tuple findGreaterOrEqual(java.lang.Object key) throws java.io.IOException
key
- Lookup key.java.io.IOException
public TupleBrowser browse() throws java.io.IOException
WARNING: If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.
java.io.IOException
public TupleBrowser browse(java.lang.Object key) throws java.io.IOException
WARNING: If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.
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)java.io.IOException
public int size()
public long getRecid()
public void readExternal(java.io.ObjectInput in) throws java.io.IOException, java.lang.ClassNotFoundException
readExternal
in interface java.io.Externalizable
java.io.IOException
java.lang.ClassNotFoundException
public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException
writeExternal
in interface java.io.Externalizable
java.io.IOException
Cees de Groot (C) 2000-2001. All rights reserved http://jdbm.sourceforge.net