| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
BTree
Description
This package provides immutable B* trees targetting large data sets requiring secondary storage.
- 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)
Constructors
| 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 |
| (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 # | |
Building trees
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 |
|
| -> 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 |
|
| -> 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.
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 |
|
| -> 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
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
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.
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.
Arguments
| :: (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.