Safe Haskell | None |
---|---|

Language | Haskell2010 |

A pure in-memory B+-tree implementation.

- module Data.BTree.Pure.Setup
- data Tree key val where
- data Node height 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 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.

# 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.