| java.lang.Object
 jdbm.btree.BTree
| BTree | | public class BTree implements Externalizable(Code) | | 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.
author:
Alex Boisvert
version:
$Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $ |
| Constructor Summary | |
| public | BTree()
No-argument constructor used by serialization. |
| Method Summary | |
| public synchronized TupleBrowser | browse()
Get a browser initially positioned at the beginning of the BTree. | | public synchronized TupleBrowser | browse(Object key)
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 browing results.
Parameters:
key - Key used to position the browser. | | public static BTree | createInstance(RecordManager recman, Comparator comparator)
Create a new persistent BTree, with 16 entries per node. | | public static BTree | createInstance(RecordManager recman, Comparator comparator, Serializer keySerializer, Serializer valueSerializer)
Create a new persistent BTree, with 16 entries per node. | | public 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. | | public synchronized Object | find(Object key)
Find the value associated with the given key.
Parameters:
key - Lookup key. | | public synchronized Tuple | findGreaterOrEqual(Object key)
Find the value associated with the given key, or the entry immediately
following this key in the ordered BTree.
Parameters:
key - Lookup key. | | public long | getRecid()
Return the persistent record identifier of the BTree. | | public synchronized Object | insert(Object key, Object value, boolean replace)
Insert an entry in the BTree.
The BTree cannot store duplicate entries. | | public static BTree | load(RecordManager recman, long recid)
Load a persistent BTree. | | public void | readExternal(ObjectInput in)
Implement Externalizable interface. | | public synchronized Object | remove(Object key)
Remove an entry with the given key from the BTree. | | public synchronized int | size()
Return the number of entries (size) of the BTree. | | public void | writeExternal(ObjectOutput out)
Implement Externalizable interface. |
| DEFAULT_SIZE | | final public static int DEFAULT_SIZE(Code) | | Default page size (number of entries per node)
|
| _comparator | | protected Comparator _comparator(Code) | | Comparator used to index entries.
|
| _entries | | protected int _entries(Code) | | Total number of entries in the BTree
|
| _keySerializer | | protected Serializer _keySerializer(Code) | | Serializer used to serialize index keys (optional)
|
| _pageSize | | protected int _pageSize(Code) | | Number of entries in each BPage.
|
| _recman | | protected transient RecordManager _recman(Code) | | Page manager used to persist changes in BPages
|
| _valueSerializer | | protected Serializer _valueSerializer(Code) | | Serializer used to serialize index values (optional)
|
| serialVersionUID | | final static long serialVersionUID(Code) | | Version id for serialization.
|
| BTree | | public BTree()(Code) | | No-argument constructor used by serialization.
|
| browse | | public synchronized TupleBrowser browse() throws IOException(Code) | | 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.
Browser positionned at the beginning of the BTree. |
| browse | | public synchronized TupleBrowser browse(Object key) throws IOException(Code) | | 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 browing results.
Parameters:
key - Key used to position the browser. If null, the browserwill be positionned after the last entry of the BTree.(Null is considered to be an "infinite" key) Browser positionned just before the given key. |
| createInstance | | public static BTree createInstance(RecordManager recman, Comparator comparator) throws IOException(Code) | | Create a new persistent BTree, with 16 entries per node.
Parameters:
recman - Record manager used for persistence.
Parameters:
comparator - Comparator used to order index entries |
| createInstance | | public static BTree createInstance(RecordManager recman, Comparator comparator, Serializer keySerializer, Serializer valueSerializer) throws IOException(Code) | | Create a new persistent BTree, with 16 entries per node.
Parameters:
recman - Record manager used for persistence.
Parameters:
keySerializer - Serializer used to serialize index keys (optional)
Parameters:
valueSerializer - Serializer used to serialize index values (optional)
Parameters:
comparator - Comparator used to order index entries |
| createInstance | | public static BTree createInstance(RecordManager recman, Comparator comparator, Serializer keySerializer, Serializer valueSerializer, int pageSize) throws IOException(Code) | | Create a new persistent BTree with the given number of entries per node.
Parameters:
recman - Record manager used for persistence.
Parameters:
comparator - Comparator used to order index entries
Parameters:
keySerializer - Serializer used to serialize index keys (optional)
Parameters:
valueSerializer - Serializer used to serialize index values (optional)
Parameters:
pageSize - Number of entries per page (must be even). |
| find | | public synchronized Object find(Object key) throws IOException(Code) | | Find the value associated with the given key.
Parameters:
key - Lookup key. Value associated with the key, or null if not found. |
| findGreaterOrEqual | | public synchronized Tuple findGreaterOrEqual(Object key) throws IOException(Code) | | Find the value associated with the given key, or the entry immediately
following this key in the ordered BTree.
Parameters:
key - Lookup key. Value associated with the key, or a greater entry, or null if nogreater entry was found. |
| getRecid | | public long getRecid()(Code) | | Return the persistent record identifier of the BTree.
|
| insert | | public synchronized Object insert(Object key, Object value, boolean replace) throws IOException(Code) | | 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
Parameters:
value - Insert value
Parameters:
replace - Set to true to replace an existing key-value pair. Existing value, if any. |
| load | | public static BTree load(RecordManager recman, long recid) throws IOException(Code) | | Load a persistent BTree.
Parameters:
recman - RecordManager used to store the persistent btree
Parameters:
recid - Record id of the BTree |
| remove | | public synchronized Object remove(Object key) throws IOException(Code) | | Remove an entry with the given key from the BTree.
Parameters:
key - Removal key Value associated with the key, or null if no entry with givenkey existed in the BTree. |
| size | | public synchronized int size()(Code) | | Return the number of entries (size) of the BTree.
|
|
|