lsm-tree-0.1.0.0: Log-structured merge-trees
Safe HaskellSafe-Inferred
LanguageGHC2021

Database.LSMTree.Internal.Index

Description

Provides support for working with fence pointer indexes of different types and their accumulators.

Keys used with an index are subject to the key size constraints of the concrete type of the index. These constraints are stated in the descriptions of the modules Database.LSMTree.Internal.Index.Compact and Database.LSMTree.Internal.Index.Ordinary, respectively.

Part of the functionality that this module provides is the construction of serialised indexes in a mostly incremental fashion. The incremental part of serialisation is provided through index accumulators, while the non-incremental bits are provided through the index operations headerLBS and finalLBS. To completely serialise an index interleaved with its construction, proceed as follows:

  1. Use headerLBS to generate the header of the serialised index.
  2. Incrementally construct the index using the operations of IndexAcc, and assemble the body of the serialised index from the generated chunks.
  3. Use finalLBS to generate the footer of the serialised index.
Synopsis

Index types

data IndexType Source #

The type of supported index types.

Constructors

Compact 
Ordinary 

Instances

Instances details
Show IndexType Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

showsPrec :: Int -> IndexType -> ShowS #

show :: IndexType -> String #

showList :: [IndexType] -> ShowS #

NFData IndexType Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

rnf :: IndexType -> () #

Eq IndexType Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

(==) :: IndexType -> IndexType -> Bool #

(/=) :: IndexType -> IndexType -> Bool #

DecodeVersioned IndexType Source # 
Instance details

Defined in Database.LSMTree.Internal.Snapshot.Codec

Methods

decodeVersioned :: SnapshotVersion -> Decoder s IndexType Source #

Encode IndexType Source # 
Instance details

Defined in Database.LSMTree.Internal.Snapshot.Codec

Methods

encode :: IndexType -> Encoding Source #

indexToIndexType :: Index -> IndexType Source #

Indexes

data Index Source #

The type of supported indexes.

Constructors

CompactIndex !IndexCompact 
OrdinaryIndex !IndexOrdinary 

Instances

Instances details
Show Index Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

showsPrec :: Int -> Index -> ShowS #

show :: Index -> String #

showList :: [Index] -> ShowS #

NFData Index Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

rnf :: Index -> () #

Eq Index Source # 
Instance details

Defined in Database.LSMTree.Internal.Index

Methods

(==) :: Index -> Index -> Bool #

(/=) :: Index -> Index -> Bool #

search :: SerialisedKey -> Index -> PageSpan Source #

Searches for a page span that contains a key–value pair with the given key. If there is indeed such a pair, the result is the corresponding page span; if there is no such pair, the result is an arbitrary but valid page span.

sizeInPages :: Index -> NumPages Source #

Yields the number of pages covered by an index.

headerLBS :: IndexType -> LazyByteString Source #

Yields the header of the serialised form of an index.

See the module documentation for how to generate a complete serialised index.

finalLBS :: NumEntries -> Index -> LazyByteString Source #

Yields the footer of the serialised form of an index.

See the module documentation for how to generate a complete serialised index.

fromSBS :: IndexType -> ShortByteString -> Either String (NumEntries, Index) Source #

Reads an index along with the number of entries of the respective run from a byte string.

The byte string must contain the serialised index exactly, with no leading or trailing space. Furthermore, its contents must be stored 64-bit-aligned.

The contents of the byte string may be directly used as the backing memory for the constructed index. Currently, this is done for compact indexes.

For deserialising numbers, the endianness of the host system is used. If serialisation has been done with a different endianness, this mismatch is detected by looking at the type–version indicator.

Index accumulators

data IndexAcc s Source #

The type of supported index accumulators, where an index accumulator denotes an index under incremental construction.

Incremental index construction is only guaranteed to work correctly when the supplied key ranges do not overlap and are given in ascending order.

Constructors

CompactIndexAcc !(IndexCompactAcc s) 
OrdinaryIndexAcc !(IndexOrdinaryAcc s) 

newWithDefaults :: IndexType -> ST s (IndexAcc s) Source #

Create a new index accumulator, using a default configuration.

appendSingle :: (SerialisedKey, SerialisedKey) -> IndexAcc s -> ST s (Maybe Chunk) Source #

Adds information about a single page that fully comprises one or more key–value pairs to an index and outputs newly available chunks.

See the documentation of the IndexAcc type for constraints to adhere to.

appendMulti :: (SerialisedKey, Word32) -> IndexAcc s -> ST s [Chunk] Source #

Adds information about multiple pages that together comprise a single key–value pair to an index and outputs newly available chunks.

The provided Word32 value denotes the number of overflow pages, so that the number of pages that comprise the key–value pair is the successor of that number.

See the documentation of the IndexAcc type for constraints to adhere to.

unsafeEnd :: IndexAcc s -> ST s (Maybe Chunk, Index) Source #

Returns the constructed index, along with a final chunk in case the serialised key list has not been fully output yet, thereby invalidating the index under construction. Executing unsafeEnd index is only safe when index is not used afterwards.