jdbm.btree

## Class BTree<K,V>

- java.lang.Object
- - jdbm.btree.BTree<K,V>

All Implemented Interfaces:
  Externalizable, Serializable

    public class BTree<K,V>
    extends Object
    implements Externalizable

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

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
See Also:
  Serialized Form

### Field Summary

Fields
`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 Summary

Constructors
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.

### Method Summary

Methods
`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.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

### Field Detail

#### DEFAULT_SIZE

    public static final int DEFAULT_SIZE

Default page size (number of entries per node)

See Also:
  Constant Field Values

#### recordManager

    protected transient RecordManager recordManager

Page manager used to persist changes in BPages

#### keySerializer

    protected Serializer keySerializer

Serializer used to serialize index keys (optional)

#### valueSerializer

    protected Serializer valueSerializer

Serializer used to serialize index values (optional)

#### pageSize

    protected int pageSize

Number of entries in each BPage.

#### nbEntries

    protected AtomicInteger nbEntries

Total number of entries in the BTree

### Constructor Detail

#### BTree

    public BTree()

No-argument constructor used by serialization.

#### BTree

    public BTree(RecordManager recman,
         Comparator<K> comparator)
          throws IOException

Create a new persistent BTree, with 16 entries per node.

Parameters:
  `recman` - Record manager used for persistence.
  `comparator` - Comparator used to order index entries
Throws:
  `IOException`

#### BTree

    public BTree(RecordManager recman,
         Comparator<K> comparator,
         Serializer keySerializer,
         Serializer valueSerializer)
          throws IOException

Create a new persistent BTree, with 16 entries per node.

Parameters:
  `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
Throws:
  `IOException`

#### BTree

    public BTree(RecordManager recman,
         Comparator<K> comparator,
         Serializer keySerializer,
         Serializer valueSerializer,
         int pageSize)
          throws IOException

Create a new persistent BTree with the given number of entries per node.

Parameters:
  `recman` - Record manager used for persistence.
  `comparator` - Comparator used to order index entries
  `keySerializer` - Serializer used to serialize index keys (optional)
  `valueSerializer` - Serializer used to serialize index values (optional)
  `pageSize` - Number of entries per page (must be even).
Throws:
  `IOException`

### Method Detail

#### setPageSize

    public void setPageSize(int pageSize)

#### load

    public BTree<K,V> load(RecordManager recman,
                  long recid)
                    throws IOException

Load a persistent BTree.

Parameters:
  `recman` - RecordManager used to store the persistent btree
  `recid` - Record id of the BTree
Throws:
  `IOException`

#### insert

    public Object insert(K key,
                V value,
                boolean replace)
                  throws IOException

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
  `value` - Insert value
  `replace` - Set to true to replace an existing key-value pair.
Returns:
  Existing value, if any.
Throws:
  `IOException`

#### remove

    public V remove(K key)
             throws IOException

Remove an entry with the given key from the BTree.

Parameters:
  `key` - Removal key
Returns:
  Value associated with the key, or null if no entry with given key existed in the BTree.
Throws:
  `IOException`

#### find

    public V find(K key)
           throws IOException

Find the value associated with the given key.

Parameters:
  `key` - Lookup key.
Returns:
  Value associated with the key, or null if not found.
Throws:
  `IOException`

#### findGreaterOrEqual

    public Tuple<K,V> findGreaterOrEqual(K key)
                                  throws IOException

Find the value associated with the given key, or the entry immediately following this key in the ordered BTree.

Parameters:
  `key` - Lookup key.
Returns:
  Value associated with the key, or a greater entry, or null if no greater entry was found.
Throws:
  `IOException`

#### browse

    public TupleBrowser<K,V> browse()
                             throws IOException

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.

Returns:
  Browser positionned at the beginning of the BTree.
Throws:
  `IOException`

#### browse

    public TupleBrowser<K,V> browse(K key)
                             throws IOException

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 browsing results.

Parameters:
  `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)
Returns:
  Browser positioned just before the given key.
Throws:
  `IOException`

#### size

    public int size()

Return the number of entries (size) of the BTree.

#### getRecordId

    public long getRecordId()

Return the persistent record identifier of the BTree.

#### readExternal

    public void readExternal(ObjectInput in)
                      throws IOException,
                             ClassNotFoundException

Implement Externalizable interface.

Specified by:
  `readExternal` in interface `Externalizable`
Throws:
  `IOException`
  `ClassNotFoundException`

#### writeExternal

    public void writeExternal(ObjectOutput out)
                       throws IOException

Implement Externalizable interface.

Specified by:
  `writeExternal` in interface `Externalizable`
Throws:
  `IOException`

#### setValueSerializer

    public void setValueSerializer(Serializer valueSerializer)

#### getComparator

    public Comparator<K> getComparator()

Returns:
  the comparator

#### toString

    public String toString()

Overrides:
  `toString` in class `Object`