Safe Haskell	None
Language	Haskell2010

Data.BTree.Impure.Structures

Contents

Structures
Binary encoding
Casting

Description

Basic structures of an impure B+-tree.

Synopsis

Structures

data Tree key val where Source #

A B+-tree.

This is a simple wrapper around a root Node. The type-level height is existentially quantified, but a term-level witness is stores.

Constructors

Tree :: {..} -> Tree key val
Fields treeHeight :: Height height A term-level witness for the type-level height index. treeRootId :: Maybe (NodeId height key val) An empty tree is represented by `Nothing`. Otherwise it's `Just` a `NodeId` pointer the root.

Instances

(Show key, Show val) => Show (Tree key val) Source #
Methods showsPrec :: Int -> Tree key val -> ShowS # show :: Tree key val -> String # showList :: [Tree key val] -> ShowS #
Binary (Tree key val) Source #
Methods put :: Tree key val -> Put # get :: Get (Tree key val) # putList :: [Tree key val] -> Put #
(Value k, Value v) => Value (Tree k v) Source #
Methods fixedSize :: Proxy * (Tree k v) -> Maybe Int Source #

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.

Sub-trees are represented by a NodeId that are used to resolve the actual storage location of the sub-tree node.

Constructors

Idx :: {..} -> Node (S height) key val
Fields idxChildren :: Index key (NodeId height key val)
Leaf :: {..} -> Node Z key val
Fields leafItems :: LeafItems key val

Instances

(Eq key, Eq val) => Eq (Node height key val) Source #
Methods (==) :: Node height key val -> Node height key val -> Bool # (/=) :: Node height key val -> Node height key val -> Bool #
(Show key, Show val) => Show (Node height key val) Source #
Methods showsPrec :: Int -> Node height key val -> ShowS # show :: Node height key val -> String # showList :: [Node height key val] -> ShowS #

type LeafItems k v = Map k (LeafValue v) Source #

data LeafValue v Source #

Constructors

RawValue v
OverflowValue OverflowId

Instances

Eq v => Eq (LeafValue v) Source #
Methods (==) :: LeafValue v -> LeafValue v -> Bool # (/=) :: LeafValue v -> LeafValue v -> Bool #
Show v => Show (LeafValue v) Source #
Methods showsPrec :: Int -> LeafValue v -> ShowS # show :: LeafValue v -> String # showList :: [LeafValue v] -> ShowS #
Binary v => Binary (LeafValue v) Source #
Methods put :: LeafValue v -> Put # get :: Get (LeafValue v) # putList :: [LeafValue v] -> Put #

Binary encoding

putLeafNode :: (Binary key, Binary val) => Node Z key val -> Put Source #

Encode a Leaf Node.

getLeafNode :: (Ord key, Binary key, Binary val) => Height Z -> Get (Node Z key val) Source #

Decode a Leaf Node.

putIndexNode :: (Binary key, Binary val) => Node (S n) key val -> Put Source #

Encode an Idx Node.

getIndexNode :: (Binary key, Binary val) => Height (S n) -> Get (Node (S n) key val) Source #

Decode an Idx Node.

Casting

castNode Source #

Arguments

:: (Typeable key1, Typeable val1, Typeable key2, Typeable val2)
=> Height height1	Term-level witness for the source height.
-> Height height2	Term-level 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 drop-in replacement for cast.

castNode' Source #

Arguments

:: (Typeable k, Typeable v)
=> Height h	Term-level witness for the source height
-> n h k v	Node to cast.
-> Either (n Z k v) (n (S h) k v)

Cast a node to one of the available types.

castValue :: (Typeable v1, Typeable v2) => v1 -> Maybe v2 Source #

Cast a value to a different type.

Essentially this is just a drop-in replacement for cast.