Classes

A stateful editing interface for efficiently inserting/removing/updating a range of elements in a B-tree.

Creating a cursor over a tree takes exclusive ownership of it; the tree is in a transient invalid state while the cursor is active. (In particular, element counts are not finalized until the cursor is deactivated.)

The cursor always focuses on a particular spot on the tree: either a particular element, or the empty spot after the last element. There are methods to move the cursor to the next or previous element, to modify the currently focused element, to insert a new element before the current position, and to remove the currently focused element from the tree.

Note that the cursor does not verify that keys you insert/modify uphold tree invariants – it is your responsibility to guarantee keys remain in ascending order while you’re working with the cursor.

Creating a cursor takes O(log(n)) steps; once the cursor has been created, the complexity of most manipulations is amortized O(1). For example, appending k new elements without a cursor takes O(k * log(n)) steps; using a cursor to do the same only takes O(log(n) + k).

See more

public final class BTreeCursor<Key: Comparable, Value>