Safe Haskell	None
Language	Haskell2010

BTree

Contents

Basic types
Building trees
Looking up in trees
Merging trees
Iterating over leaves

Description

This package provides immutable B* trees targetting large data sets requiring secondary storage.

Synopsis

data BLeaf k e = BLeaf !k !e
type Size = Word64
type Order = Word64
fromOrderedToFile :: (MonadMask m, MonadIO m, Binary e, Binary k) => Order -> Size -> FilePath -> Producer (BLeaf k e) m r -> m ()
fromOrderedToByteString :: (Monad m, Binary e, Binary k) => Order -> Size -> Producer (BLeaf k e) m r -> m ByteString
fromUnorderedToFile :: forall m e k r. (MonadMask m, MonadIO m, Binary (BLeaf k e), Binary k, Binary e, Ord k) => FilePath -> Int -> Order -> FilePath -> Producer (BLeaf k e) m r -> ExceptT String m ()
data LookupTree k e
open :: FilePath -> IO (Either String (LookupTree k e))
fromByteString :: ByteString -> Either String (LookupTree k e)
lookup :: (Binary k, Binary e, Ord k) => LookupTree k e -> k -> Maybe e
size :: LookupTree k e -> Size
mergeTrees :: (MonadMask m, MonadIO m, Functor m, Binary k, Binary e, Ord k) => (e -> e -> m e) -> Order -> FilePath -> [LookupTree k e] -> m ()
mergeLeaves :: (MonadMask m, MonadIO m, Functor m, Binary k, Binary e, Ord k) => (e -> e -> m e) -> Order -> FilePath -> [(Size, Producer (BLeaf k e) m ())] -> m ()
sizedProducerForTree :: (Monad m, Binary k, Binary e) => LookupTree k e -> (Size, Producer (BLeaf k e) m ())
walkLeaves :: (Binary k, Binary v, Monad m) => LookupTree k v -> Producer (BLeaf k v) m (ByteString, Maybe String)

Basic types

data BLeaf k e Source #

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

Constructors

BLeaf !k !e

Instances

Functor (BLeaf k) Source #
Instance details Defined in BTree.Types Methods fmap :: (a -> b) -> BLeaf k a -> BLeaf k b # (<$) :: a -> BLeaf k b -> BLeaf k a #
Eq k => Eq (BLeaf k e) Source #	This only compares on the keys
Instance details Defined in BTree.Types Methods (==) :: BLeaf k e -> BLeaf k e -> Bool # (/=) :: BLeaf k e -> BLeaf k e -> Bool #
Ord k => Ord (BLeaf k e) Source #	This only compares on the keys
Instance details Defined in BTree.Types Methods compare :: BLeaf k e -> BLeaf k e -> Ordering # (<) :: BLeaf k e -> BLeaf k e -> Bool # (<=) :: BLeaf k e -> BLeaf k e -> Bool # (>) :: BLeaf k e -> BLeaf k e -> Bool # (>=) :: BLeaf k e -> BLeaf k e -> Bool # max :: BLeaf k e -> BLeaf k e -> BLeaf k e # min :: BLeaf k e -> BLeaf k e -> BLeaf k e #
(Show k, Show e) => Show (BLeaf k e) Source #
Instance details Defined in BTree.Types Methods showsPrec :: Int -> BLeaf k e -> ShowS # show :: BLeaf k e -> String # showList :: [BLeaf k e] -> ShowS #
Generic (BLeaf k e) Source #
Instance details Defined in BTree.Types Associated Types type Rep (BLeaf k e) :: Type -> Type # Methods from :: BLeaf k e -> Rep (BLeaf k e) x # to :: Rep (BLeaf k e) x -> BLeaf k e #
(Binary k, Binary e) => Binary (BLeaf k e) Source #
Instance details Defined in BTree.Types Methods put :: BLeaf k e -> Put # get :: Get (BLeaf k e) # putList :: [BLeaf k e] -> Put #
type Rep (BLeaf k e) Source #
Instance details Defined in BTree.Types type Rep (BLeaf k e) = D1 (MetaData "BLeaf" "BTree.Types" "b-tree-0.1.4-73dR3A2X0Vu3poq1AAXQQh" False) (C1 (MetaCons "BLeaf" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 k) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 e)))

type Size = Word64 Source #

The number of entries in a B-tree

type Order = Word64 Source #

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

Building trees

fromOrderedToFile Source #

Arguments

:: (MonadMask m, 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 Source #

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

Arguments

:: (MonadMask m, 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 Source #

A read-only B-tree for lookups

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

Open a B-tree file.

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

Read a B-tree from a ByteString produced by Builder

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

Lookup a key in a B-tree.

size :: LookupTree k e -> Size Source #

How many keys are in a LookupTree.

Merging trees

mergeTrees Source #

Arguments

:: (MonadMask m, 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 Source #

Arguments

:: (MonadMask m, 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 Source #

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) Source #

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