|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjdbm.btree.BTree<K,V>
public class BTree<K,V>
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.
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 | ||
---|---|---|
void |
addRecordListener(RecordListener<K,V> listener)
add RecordListener which is notified about record changes |
|
BTreeSortedMap<K,V> |
asMap()
|
|
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. |
|
static
|
createInstance(RecordManager recman)
Create a new persistent BTree, with 16 entries per node. |
|
static
|
createInstance(RecordManager recman,
java.util.Comparator<K> comparator)
Create a new persistent BTree, with 16 entries per node. |
|
static
|
createInstance(RecordManager recman,
java.util.Comparator<K> comparator,
Serializer<K> keySerializer,
Serializer<V> valueSerializer)
Create a new persistent BTree, with 16 entries per node. |
|
static
|
createInstance(RecordManager recman,
java.util.Comparator<K> comparator,
Serializer<K> keySerializer,
Serializer<V> valueSerializer,
int pageSize)
Create a new persistent BTree with the given number of entries per node. |
|
void |
delete()
Deletes all BPages in this BTree, then deletes the tree from the record manager |
|
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()
|
|
Serializer<K> |
getKeySerializer()
|
|
java.util.concurrent.locks.ReadWriteLock |
getLock()
Get the ReadWriteLock associated with this BTree. |
|
long |
getRecid()
Return the persistent record identifier of the BTree. |
|
RecordManager |
getRecordManager()
|
|
Serializer<V> |
getValueSerializer()
|
|
V |
insert(K key,
V value,
boolean replace)
Insert an entry in the BTree. |
|
static
|
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. |
|
void |
removeRecordListener(RecordListener<K,V> listener)
remove RecordListener which is notified about record changes |
|
void |
setKeySerializer(Serializer<K> keySerializer)
|
|
void |
setValueSerializer(Serializer<V> valueSerializer)
|
|
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 |
---|
public static final int DEFAULT_SIZE
Constructor Detail |
---|
public BTree()
Method Detail |
---|
public Serializer<K> getKeySerializer()
public void setKeySerializer(Serializer<K> keySerializer)
public Serializer<V> getValueSerializer()
public void setValueSerializer(Serializer<V> valueSerializer)
public static <K,V> BTree<K,V> createInstance(RecordManager recman, java.util.Comparator<K> comparator) throws java.io.IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entries
java.io.IOException
public static <K extends java.lang.Comparable,V> BTree<K,V> createInstance(RecordManager recman) throws java.io.IOException
recman
- Record manager used for persistence.comparator
- Comparator used to order index entries
java.io.IOException
public static <K,V> BTree<K,V> createInstance(RecordManager recman, java.util.Comparator<K> comparator, Serializer<K> keySerializer, Serializer<V> 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 entries
java.io.IOException
public static <K,V> BTree<K,V> createInstance(RecordManager recman, java.util.Comparator<K> comparator, Serializer<K> keySerializer, Serializer<V> 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 <K,V> BTree<K,V> load(RecordManager recman, long recid) throws java.io.IOException
recman
- RecordManager used to store the persistent btreerecid
- Record id of the BTree
java.io.IOException
public java.util.concurrent.locks.ReadWriteLock getLock()
ReadWriteLock
associated with this BTree.
This should be used with browsing operations to ensure
consistency.
public V insert(K key, V 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 V remove(K key) throws java.io.IOException
key
- Removal key
java.io.IOException
public V find(K key) throws java.io.IOException
find
in interface JdbmBase<K,V>
key
- Lookup key.
java.io.IOException
public Tuple<K,V> findGreaterOrEqual(K key) throws java.io.IOException
key
- Lookup key.
java.io.IOException
public TupleBrowser<K,V> 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<K,V> browse(K 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
public BTreeSortedMap<K,V> asMap()
public void addRecordListener(RecordListener<K,V> listener)
addRecordListener
in interface JdbmBase<K,V>
listener
- public void removeRecordListener(RecordListener<K,V> listener)
removeRecordListener
in interface JdbmBase<K,V>
listener
- public RecordManager getRecordManager()
getRecordManager
in interface JdbmBase<K,V>
public java.util.Comparator<K> getComparator()
public void delete() throws java.io.IOException
java.io.IOException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |