haskey-btree-0.1.0.0: B+-tree implementation in Haskell.

Safe HaskellNone
LanguageHaskell2010

Data.BTree.Impure.Insert

Description

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

Synopsis

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)) Source #

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)) Source #

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)) Source #

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)) Source #

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

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) Source #

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) Source #

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.