Data.BTree.Impure.Structures

Basic structures of an impure B+-tree.

Structures

data Tree key val where

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)

Methods

showsPrec :: Int -> Tree key val -> ShowS

show :: Tree key val -> String

showList :: [Tree key val] -> ShowS

Binary (Tree key val)

Methods

put :: Tree key val -> Put

get :: Get (Tree key val)

putList :: [Tree key val] -> Put

(Value k, Value v) => Value (Tree k v)

Methods

fixedSize :: Proxy * (Tree k v) -> Maybe Int

data Node height key val where

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)

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)

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)

data LeafValue v

Constructors

RawValue v

OverflowValue OverflowId

Instances

Eq v => Eq (LeafValue v)

Methods

(==) :: LeafValue v -> LeafValue v -> Bool

(/=) :: LeafValue v -> LeafValue v -> Bool

Show v => Show (LeafValue v)

Methods

showsPrec :: Int -> LeafValue v -> ShowS

show :: LeafValue v -> String

showList :: [LeafValue v] -> ShowS

Binary v => Binary (LeafValue v)

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

Encode a Leaf Node.

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

Decode a Leaf Node.

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

Encode an Idx Node.

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

Decode an Idx Node.

Casting

castNode

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'

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

Cast a value to a different type.

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