public class BTree extends Object implements 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 | Field and Description |
---|---|
protected 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)
|
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(Object key)
Get a browser initially positioned just before the given key.
|
static BTree |
createInstance(RecordManager recman,
Comparator comparator)
Create a new persistent BTree, with 16 entries per node.
|
static BTree |
createInstance(RecordManager recman,
Comparator comparator,
Serializer keySerializer,
Serializer valueSerializer)
Create a new persistent BTree, with 16 entries per node.
|
static BTree |
createInstance(RecordManager recman,
Comparator comparator,
Serializer keySerializer,
Serializer valueSerializer,
int pageSize)
Create a new persistent BTree with the given number of entries per node.
|
Object |
find(Object key)
Find the value associated with the given key.
|
Tuple |
findGreaterOrEqual(Object key)
Find the value associated with the given key, or the entry immediately
following this key in the ordered BTree.
|
Comparator |
getComparator() |
long |
getRecid()
Return the persistent record identifier of the BTree.
|
Object |
insert(Object key,
Object value,
boolean replace)
Insert an entry in the BTree.
|
static BTree |
load(RecordManager recman,
long recid)
Load a persistent BTree.
|
void |
readExternal(ObjectInput in)
Implement Externalizable interface.
|
Object |
remove(Object key)
Remove an entry with the given key from the BTree.
|
void |
setValueSerializer(Serializer valueSerializer) |
int |
size()
Return the number of entries (size) of the BTree.
|
void |
writeExternal(ObjectOutput out)
Implement Externalizable interface.
|
public static final int DEFAULT_SIZE
protected transient RecordManager _recman
protected Comparator _comparator
protected Serializer _keySerializer
protected Serializer _valueSerializer
protected int _pageSize
protected int _entries
public static BTree createInstance(RecordManager recman, Comparator comparator) throws IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entriesIOException
public static BTree createInstance(RecordManager recman, Comparator comparator, Serializer keySerializer, Serializer valueSerializer) throws 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 entriesIOException
public static BTree createInstance(RecordManager recman, Comparator comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize) throws 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).IOException
public static BTree load(RecordManager recman, long recid) throws IOException
recman
- RecordManager used to store the persistent btreerecid
- Record id of the BTreeIOException
public Object insert(Object key, Object value, boolean replace) throws 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.IOException
public Object remove(Object key) throws IOException
key
- Removal keyIOException
public Object find(Object key) throws IOException
key
- Lookup key.IOException
public Tuple findGreaterOrEqual(Object key) throws IOException
key
- Lookup key.IOException
public TupleBrowser browse() throws IOException
WARNING: �If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.
IOException
public TupleBrowser browse(Object key) throws 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)IOException
public int size()
public long getRecid()
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
readExternal
in interface Externalizable
IOException
ClassNotFoundException
public void writeExternal(ObjectOutput out) throws IOException
writeExternal
in interface Externalizable
IOException
public void setValueSerializer(Serializer valueSerializer)
public Comparator getComparator()
Copyright © 2003-2012 Apache Software Foundation. All Rights Reserved.