public class BTree<K,V> 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 |
---|---|
static int |
DEFAULT_SIZE
Default page size (number of entries per node)
|
protected Serializer |
keySerializer
Serializer used to serialize index keys (optional)
|
protected AtomicInteger |
nbEntries
Total number of entries in the BTree
|
protected int |
pageSize
Number of entries in each BPage.
|
protected RecordManager |
recordManager
Page manager used to persist changes in BPages
|
protected Serializer |
valueSerializer
Serializer used to serialize index values (optional)
|
Constructor and Description |
---|
BTree()
No-argument constructor used by serialization.
|
BTree(RecordManager recman,
Comparator<K> comparator)
Create a new persistent BTree, with 16 entries per node.
|
BTree(RecordManager recman,
Comparator<K> comparator,
Serializer keySerializer,
Serializer valueSerializer)
Create a new persistent BTree, with 16 entries per node.
|
BTree(RecordManager recman,
Comparator<K> comparator,
Serializer keySerializer,
Serializer valueSerializer,
int pageSize)
Create a new persistent BTree with the given number of entries per node.
|
Modifier and Type | Method and Description |
---|---|
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.
|
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.
|
Comparator<K> |
getComparator() |
long |
getRecordId()
Return the persistent record identifier of the BTree.
|
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(ObjectInput in)
Implement Externalizable interface.
|
V |
remove(K key)
Remove an entry with the given key from the BTree.
|
void |
setPageSize(int pageSize) |
void |
setValueSerializer(Serializer valueSerializer) |
int |
size()
Return the number of entries (size) of the BTree.
|
String |
toString() |
void |
writeExternal(ObjectOutput out)
Implement Externalizable interface.
|
public static final int DEFAULT_SIZE
protected transient RecordManager recordManager
protected Serializer keySerializer
protected Serializer valueSerializer
protected int pageSize
protected AtomicInteger nbEntries
public BTree()
public BTree(RecordManager recman, Comparator<K> comparator) throws IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entriesIOException
public BTree(RecordManager recman, Comparator<K> 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 BTree(RecordManager recman, Comparator<K> 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 void setPageSize(int pageSize)
public BTree<K,V> load(RecordManager recman, long recid) throws IOException
recman
- RecordManager used to store the persistent btreerecid
- Record id of the BTreeIOException
public Object insert(K key, V 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 V remove(K key) throws IOException
key
- Removal keyIOException
public V find(K key) throws IOException
key
- Lookup key.IOException
public Tuple<K,V> findGreaterOrEqual(K key) throws IOException
key
- Lookup key.IOException
public TupleBrowser<K,V> browse() throws IOException
WARNING: If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.
IOException
public TupleBrowser<K,V> browse(K key) throws IOException
WARNING: If you make structural modifications to the BTree during browsing, you will get inconsistent browsing results.
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)IOException
public int size()
public long getRecordId()
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<K> getComparator()
Copyright © 2017. All rights reserved.