4 - Mavibot B-tree operations

We will now list all the possible operations that can be applied on a B-tree. But first, let us understand the Cursor interface, as it is used for navigating a B-tree using various types of browse operations.

4.1 The Cursor interface

All the browse operations will return a Cursor instance. A Cursor allows navigating forward and backward on a B-tree. It starts at a specific position, and can be moved to a specific position too. The default position for a Cursor is before the very first element of the B-tree

It is important to understand that a Cursor returns tuples, not keys. A Key may be associated with many values, so a cursor may return many tuples with a given key (each one will have a different value though).

Here is the B-tree sample we will use for the following examples :

Sample B-tree

4.1.1 Cursor position management

4.1.1.1 afterLast

Moves the current position after the last element (last key and last value). The following schema shows the new position of the pointer after having called the afterLast() method :

After Last

As we can see, we are not pointing at any key.

4.1.1.2 beforeFirst

Moves the current position before the first element (first key and first value). The following schema shows the new position of the pointer after having called the beforeFirst() method :

Before First

In this case also cursor is not stationed at any key.

4.1.2 Cursor operations

When a cursor is used to browse Tuples it may return many tuples with the same key but different value, when used to browse keys a single tuple will be returned for each key with the value of the key (when multiple values are present only the first value will be returned).

4.1.2.1 hasNext

Tells if there is a next available tuple. This will always be true if we are before the first tuple, and always false if we are on the last tuple or after the last tuple. The following picture shows the returned value for calls in various cases :

Has Next

4.1.2.2 hasPrev

Returns true if there is a tuple available before the current tuple.

4.1.2.3 next

Moves to the next value of the current key or to the next key if all the values of the current key have been processed, and return the associated tuple.

4.1.2.4 prev

Moves to the previous value of the current key or to the previous key if all the values of the current key have been processed, and return the associated tuple.

4.1.2.5 hasNextKey

Tells if there is a key after the current key.

4.1.2.6 hasPrevKey

Tells if there is a previous key before the current key.

4.1.2.7 nextKey

Moves(jumps) to the next key, even if not all values of the current key are navigated.

4.1.2.8 prevKey

Moves(jumps) to the previous key, even if not all values of the current key are navigated.

4.1 Browse Operations

Now that we know what a Cursor is about, we can describe the various browse operations.

4.1.1 browse()

This method returns a cursor with the position set before the first key of the B-tree.