Data.BTree.Pure

A pure in-memory B+-tree implementation.

Structures

module Data.BTree.Pure.Setup

data Tree key val where

A pure B+-tree.

This is a simple wrapper around a root Node. An empty tree is represented by Nothing. Otherwise it's Just the root. The height is existentially quantified.

Constructors

Tree :: !TreeSetup -> Maybe (Node height key val) -> Tree key val

Instances

Foldable (Tree key)

Make a tree node foldable over its value.

Methods

fold :: Monoid m => Tree key m -> m

foldMap :: Monoid m => (a -> m) -> Tree key a -> m

foldr :: (a -> b -> b) -> b -> Tree key a -> b

foldr' :: (a -> b -> b) -> b -> Tree key a -> b

foldl :: (b -> a -> b) -> b -> Tree key a -> b

foldl' :: (b -> a -> b) -> b -> Tree key a -> b

foldr1 :: (a -> a -> a) -> Tree key a -> a

foldl1 :: (a -> a -> a) -> Tree key a -> a

toList :: Tree key a -> [a]

null :: Tree key a -> Bool

length :: Tree key a -> Int

elem :: Eq a => a -> Tree key a -> Bool

maximum :: Ord a => Tree key a -> a

minimum :: Ord a => Tree key a -> a

sum :: Num a => Tree key a -> a

product :: Num a => Tree key a -> a

(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

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.

Constructors

Idx :: {..} -> Node (S height) key val

Fields

• idxChildren :: Index key (Node height key val)

Leaf :: {..} -> Node Z key val

Fields

• leafItems :: Map key val

Instances

Foldable (Node height key)

Methods

fold :: Monoid m => Node height key m -> m

foldMap :: Monoid m => (a -> m) -> Node height key a -> m

foldr :: (a -> b -> b) -> b -> Node height key a -> b

foldr' :: (a -> b -> b) -> b -> Node height key a -> b

foldl :: (b -> a -> b) -> b -> Node height key a -> b

foldl' :: (b -> a -> b) -> b -> Node height key a -> b

foldr1 :: (a -> a -> a) -> Node height key a -> a

foldl1 :: (a -> a -> a) -> Node height key a -> a

toList :: Node height key a -> [a]

null :: Node height key a -> Bool

length :: Node height key a -> Int

elem :: Eq a => a -> Node height key a -> Bool

maximum :: Ord a => Node height key a -> a

minimum :: Ord a => Node height key a -> a

sum :: Num a => Node height key a -> a

product :: Num a => Node height key a -> a

(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

Manipulations

empty :: TreeSetup -> Tree key val

The empty tree.

singleton :: Key k => TreeSetup -> k -> v -> Tree k v

Construct a tree containg one element.

fromList :: Key k => TreeSetup -> [(k, v)] -> Tree k v

O(n*log n). Construct a B-tree from a list of key/value pairs.

If the list contains duplicate keys, the last pair for a duplicate key is kept.

insert :: Key k => k -> v -> Tree k v -> Tree k v

Insert a key-value pair into a tree.

When inserting a new entry, the leaf it is inserted to and the index nodes on the path to the leaf potentially need to be split. Instead of returning the outcome, 1 node or 2 nodes (with a discriminating key), we return an Index of these nodes.

If the key already existed in the tree, it is overwritten.

insertMany :: Key k => Map k v -> Tree k v -> Tree k v

Insert a bunch of key-value pairs simultaneously.

delete :: Key k => k -> Tree k v -> Tree k v

Delete a key-value pair from the tree.

Lookup

lookup :: Key k => k -> Tree k v -> Maybe v

Lookup a value in the tree.

findWithDefault :: Key k => v -> k -> Tree k v -> v

Lookup a value in the tree, or return a default.

member :: Key k => k -> Tree k v -> Bool

Check whether a key is present in the tree.

notMember :: Key k => k -> Tree k v -> Bool

Check whether a key is not present in the tree.

Properties

null :: Tree k v -> Bool

Check whether the tree is empty.

size :: Tree k v -> Int

The size of a tree.

Folds

foldrWithKey :: forall k v w. (k -> v -> w -> w) -> w -> Tree k v -> w

O(n). Fold key/value pairs in the B-tree.

toList :: Tree k v -> [(k, v)]

O(n). Convert the B-tree to a sorted list of key/value pairs.