BTree

Basic types

data BLeaf k e

A tree leaf (e.g. key/value pair)

Constructors

BLeaf !k !e

Instances

Eq k => Eq (BLeaf k e)

This only compares on the keys

Ord k => Ord (BLeaf k e)

This only compares on the keys

(Show k, Show e) => Show (BLeaf k e)

Generic (BLeaf k e)

(Binary k, Binary e) => Binary (BLeaf k e)

type Rep (BLeaf k e)

type Size = Word64

The number of entries in a B-tree

type Order = Word64

The maximum number of children of a B-tree inner node

Building trees

fromOrderedToFile

Arguments

:: (MonadIO m, Binary e, Binary k)

=> Order

Order of tree

-> Size

Maximum tree size

-> FilePath

Output file

-> Producer (BLeaf k e) m r

Producer of elements

-> m ()

Build a B-tree into the given file.

As the name suggests, this requires that the Producer emits leaves in ascending key order.

fromOrderedToByteString

Arguments

:: (Monad m, Binary e, Binary k)

=> Order

Order of tree

-> Size

Maximum tree size

-> Producer (BLeaf k e) m r

Producer of elements

-> m ByteString

Build a B-tree into ByteString

As the name suggests, this requires that the Producer emits leaves in ascending key order.

This is primarily used for testing. In particular, note that this is a bad idea for large trees as the entire contents of the tree will need to be kept in memory until all leaves have been added so that the header can be prepended.

fromUnorderedToFile

Arguments

:: (MonadIO m, Binary (BLeaf k e), Binary k, Binary e, Ord k)

=> FilePath

Path to scratch directory

-> Int

Maximum chunk size

-> Order

Order of tree

-> FilePath

Output file

-> Producer (BLeaf k e) m r

Producer of elements

-> ExceptT String m ()

Build a B-tree into the given file.

This does not assume that the leaves are produced in order. Instead, the sorting is handled internally through a simple merge sort. Chunks of leaves are collected, sorted in memory, and then written to intermediate trees. At the end these trees are then merged.

Looking up in trees

data LookupTree k e

A read-only B-tree for lookups

open :: FilePath -> IO (Either String (LookupTree k e))

Open a B-tree file.

fromByteString :: ByteString -> Either String (LookupTree k e)

Read a B-tree from a ByteString produced by Builder

lookup :: (Binary k, Binary e, Ord k) => LookupTree k e -> k -> Maybe e

Lookup a key in a B-tree.

Merging trees

mergeTrees

Arguments

:: (MonadIO m, Functor m, Binary k, Binary e, Ord k)

=> (e -> e -> m e)

merge operation on elements

-> Order

order of merged tree

-> FilePath

name of output file

-> [LookupTree k e]

trees to merge

-> m ()

Merge several LookupTrees

This is a convenience function for merging several trees already on disk. For a more flexible interface, see mergeLeaves.

mergeLeaves

Arguments

:: (MonadIO m, Functor m, Binary k, Binary e, Ord k)

=> (e -> e -> m e)

merge operation on elements

-> Order

order of merged tree

-> FilePath

name of output file

-> [(Size, Producer (BLeaf k e) m ())]

producers of leaves to merge

-> m ()

Merge trees' leaves taking ordered leaves from a set of producers.

Each producer must be annotated with the number of leaves it is expected to produce. The size of the resulting tree will be at most the sum of these sizes.

sizedProducerForTree

Arguments

:: (Monad m, Binary k, Binary e)

=> LookupTree k e

a tree

-> (Size, Producer (BLeaf k e) m ())

a sized Producer suitable for passing to mergeLeaves

Get a sized Producer suitable for mergeLeaves from a LookupTree

Iterating over leaves

walkLeaves :: (Binary k, Binary v, Monad m) => LookupTree k v -> Producer (BLeaf k v) m (ByteString, Maybe String)

Iterate over the leaves of the given tree in ascending key order.