b-tree-0.1.3: Immutable disk-based B* trees

Safe HaskellNone
LanguageHaskell2010

BTree

Contents

Description

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

Synopsis

Basic types

data BLeaf k e Source #

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

Constructors

BLeaf !k !e 

Instances

Functor (BLeaf k) Source # 

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

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

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 # 

Methods

showsPrec :: Int -> BLeaf k e -> ShowS #

show :: BLeaf k e -> String #

showList :: [BLeaf k e] -> ShowS #

Generic (BLeaf k e) Source # 

Associated Types

type Rep (BLeaf k e) :: * -> * #

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 # 

Methods

put :: BLeaf k e -> Put #

get :: Get (BLeaf k e) #

putList :: [BLeaf k e] -> Put #

type Rep (BLeaf k e) Source # 
type Rep (BLeaf k e) = D1 (MetaData "BLeaf" "BTree.Types" "b-tree-0.1.3-DBxFCvdSA8C4buq9GOyiH1" False) (C1 (MetaCons "BLeaf" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 k)) (S1 (MetaSel (Nothing 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.