Data.BTree.Impure.Insert

Algorithms related to inserting key-value pairs in an impure B+-tree.

Documentation

splitIndex :: (AllocM m, Key key, Value val) => Height (S height) -> Index key (NodeId height key val) -> m (Index key (Node (S height) key val))

Split an index node.

This function is partial. It fails when the original index cannot be split, because it does not contain enough elements (underflow).

splitLeaf :: (AllocM m, Key key, Value val) => LeafItems key val -> m (Index key (Node Z key val))

Split a leaf node.

This function is partial. It fails when the original leaf cannot be split, because it does not contain enough elements (underflow).

insertRec :: forall m height key val. (AllocM m, Key key, Value val) => key -> val -> Height height -> NodeId height key val -> m (Index key (NodeId height key val))

insertRecMany :: forall m height key val. (AllocM m, Key key, Value val) => Height height -> Map key val -> NodeId height key val -> m (Index key (NodeId height key val))

insertTree :: (AllocM m, Key key, Value val) => key -> val -> Tree key val -> m (Tree key val)

Insert a key-value pair in an impure B+-tree.

You are responsible to make sure the key is smaller than maxKeySize, otherwise a KeyTooLargeError can (but not always will) be thrown.

insertTreeMany :: (AllocM m, Key key, Value val) => Map key val -> Tree key val -> m (Tree key val)

Bulk insert a bunch of key-value pairs in an impure B+-tree.

You are responsible to make sure all keys is smaller than maxKeySize, otherwise a KeyTooLargeError can (but not always will) be thrown.

fixUp :: (AllocM m, Key key, Value val) => Height height -> Index key (NodeId height key val) -> m (Tree key val)

Fix up the root node of a tree.

Fix up the root node of a tree, where all other nodes are valid, but the root node may contain more items than allowed. Do this by repeatedly splitting up the root node.