Safe Haskell  None 

Language  Haskell2010 
Basic structures of an impure B+tree.
 data Tree key val where
 data Node height key val where
 type LeafItems k v = Map k (LeafValue v)
 data LeafValue v
 putLeafNode :: (Binary key, Binary val) => Node Z key val > Put
 getLeafNode :: (Ord key, Binary key, Binary val) => Height Z > Get (Node Z key val)
 putIndexNode :: (Binary key, Binary val) => Node (S n) key val > Put
 getIndexNode :: (Binary key, Binary val) => Height (S n) > Get (Node (S n) key val)
 castNode :: forall n key1 val1 height1 key2 val2 height2. (Typeable key1, Typeable val1, Typeable key2, Typeable val2) => Height height1 > Height height2 > n height1 key1 val1 > Maybe (n height2 key2 val2)
 castNode' :: forall n h k v. (Typeable k, Typeable v) => Height h > n h k v > Either (n Z k v) (n (S h) k v)
 castValue :: (Typeable v1, Typeable v2) => v1 > Maybe v2
Structures
data Tree key val where Source #
A B+tree.
This is a simple wrapper around a root Node
. The typelevel height is
existentially quantified, but a termlevel witness is stores.
Tree :: {..} > Tree key val  

data Node height key val where Source #
A node in a B+tree.
Nodes are parameterized over the key and value types and are additionally indexed by their height. All paths from the root to the leaves have the same length. The height is the number of edges from the root to the leaves, i.e. leaves are at height zero and index nodes increase the height.
Subtrees are represented by a NodeId
that are used to resolve the actual
storage location of the subtree node.
Binary encoding
Casting
:: (Typeable key1, Typeable val1, Typeable key2, Typeable val2)  
=> Height height1  Termlevel witness for the source height. 
> Height height2  Termlevel witness for the target height. 
> n height1 key1 val1  Node to cast. 
> Maybe (n height2 key2 val2) 
Cast a node to a different type.
Essentially this is just a dropin replacement for cast
.