| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.BTree.Impure.Insert
Description
Algorithms related to inserting key-value pairs in an impure B+-tree.
- splitIndex :: (AllocM m, Key key, Value val) => Height (S height) -> Index key (NodeId height key val) -> m (Index key (Node (S height) key val))
- splitLeaf :: (AllocM m, Key key, Value val) => LeafItems key val -> m (Index key (Node Z key val))
- 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)
- insertTreeMany :: (AllocM m, Key key, Value val) => Map key val -> Tree key val -> m (Tree key val)
- fixUp :: (AllocM m, Key key, Value val) => Height height -> Index key (NodeId height key val) -> m (Tree key val)
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.