| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.BTree.Impure.Internal.Insert
Description
Algorithms related to inserting key-value pairs in an impure B+-tree.
Synopsis
- splitIndex :: forall m key val (height :: Nat). (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 :: Nat) 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 :: Nat) key val. (AllocM m, Key key, Value val) => Height height -> Map key val -> NodeId height key val -> m (Index key (NodeId height key val))
- insert :: (AllocM m, Key key, Value val) => key -> val -> Tree key val -> m (Tree key val)
- insertMany :: (AllocM m, Key key, Value val) => Map key val -> Tree key val -> m (Tree key val)
- fixUp :: forall m key val (height :: Nat). (AllocM m, Key key, Value val) => Height height -> Index key (NodeId height key val) -> m (Tree key val)
Documentation
splitIndex :: forall m key val (height :: Nat). (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 :: Nat) 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 :: Nat) 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 #
insert :: (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.
insertMany :: (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 :: forall m key val (height :: Nat). (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.