Safe Haskell | None |
---|---|
Language | Haskell2010 |
A pure in-memory B+-tree implementation.
Synopsis
- module Data.BTree.Pure.Setup
- data Tree key val where
- data Node (height :: Nat) key val where
- empty :: TreeSetup -> Tree key val
- singleton :: Key k => TreeSetup -> k -> v -> Tree k v
- fromList :: Key k => TreeSetup -> [(k, v)] -> Tree k v
- insert :: Key k => k -> v -> Tree k v -> Tree k v
- insertMany :: Key k => Map k v -> Tree k v -> Tree k v
- delete :: Key k => k -> Tree k v -> Tree k v
- lookup :: Key k => k -> Tree k v -> Maybe v
- findWithDefault :: Key k => v -> k -> Tree k v -> v
- member :: Key k => k -> Tree k v -> Bool
- notMember :: Key k => k -> Tree k v -> Bool
- null :: Tree k v -> Bool
- size :: Tree k v -> Int
- foldrWithKey :: forall k v w. (k -> v -> w -> w) -> w -> Tree k v -> w
- toList :: Tree k v -> [(k, v)]
Structures
module Data.BTree.Pure.Setup
data Tree key val where Source #
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.
Instances
Foldable (Tree key) Source # | Make a tree node foldable over its value. |
Defined in Data.BTree.Pure 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 # elem :: Eq a => a -> Tree key a -> Bool # maximum :: Ord a => Tree key a -> a # minimum :: Ord a => Tree key a -> a # | |
(Show key, Show val) => Show (Tree key val) Source # | |
data Node (height :: Nat) 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.
Instances
Foldable (Node height key) Source # | |
Defined in Data.BTree.Pure 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 # | |
(Show key, Show val) => Show (Node height key val) Source # | |
Manipulations
singleton :: Key k => TreeSetup -> k -> v -> Tree k v Source #
Construct a tree containg one element.
fromList :: Key k => TreeSetup -> [(k, v)] -> Tree k v Source #
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 Source #
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 Source #
Insert a bunch of key-value pairs simultaneously.
Lookup
findWithDefault :: Key k => v -> k -> Tree k v -> v Source #
Lookup a value in the tree, or return a default.
Properties
Folds
foldrWithKey :: forall k v w. (k -> v -> w -> w) -> w -> Tree k v -> w Source #
O(n). Fold key/value pairs in the B-tree.