Safe Haskell  None 

Language  Haskell2010 
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
A tree leaf (e.g. key/value pair)
BLeaf !k !e 
Instances
Functor (BLeaf k) Source #  
Eq k => Eq (BLeaf k e) Source #  This only compares on the keys 
Ord k => Ord (BLeaf k e) Source #  This only compares on the keys 
Defined in BTree.Types  
(Show k, Show e) => Show (BLeaf k e) Source #  
Generic (BLeaf k e) Source #  
(Binary k, Binary e) => Binary (BLeaf k e) Source #  
type Rep (BLeaf k e) Source #  
Defined in BTree.Types type Rep (BLeaf k e) = D1 (MetaData "BLeaf" "BTree.Types" "btree0.1.473dR3A2X0Vu3poq1AAXQQh" 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))) 
Building trees
:: (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 

> m () 
Build a Btree into the given file.
As the name suggests, this requires that the Producer
emits
leaves in ascending key order.
fromOrderedToByteString Source #
:: (Monad m, Binary e, Binary k)  
=> Order  Order of tree 
> Size  Maximum tree size 
> Producer (BLeaf k e) m r 

> m ByteString 
Build a Btree 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.
:: (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 

> ExceptT String m () 
Build a Btree 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 readonly Btree for lookups
fromByteString :: ByteString > Either String (LookupTree k e) Source #
Read a Btree 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 Btree.
size :: LookupTree k e > Size Source #
How many keys are in a LookupTree
.
Merging trees
:: (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
.
:: (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.
:: (Monad m, Binary k, Binary e)  
=> LookupTree k e  a tree 
> (Size, Producer (BLeaf k e) m ())  a sized 
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.