Hackage :: [Package]

btree-concurrent: A backend agnostic, concurrent BTree

[ data-structures, library ] [ Propose Tags ]

A backend agnostic, concurrent BTree

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0, 0.1.1, 0.1.3, 0.1.4, 0.1.5
Dependencies array (>=0.4 && <0.5), base (>=4 && <5), base64-bytestring (>=1 && <2), bytestring (>=0.9), cereal (>=0.3), containers (>=0.5), directory (>=1 && <2), filepath (>=1 && <2), hashable (>=1 && <2), mtl (>=2 && <3), random (>=1 && <2), snappy (>=0.2 && <0.3), stm (>=2.2 && <2.3), time (>=1 && <2) [details]
License LicenseRef-LGPL
Author Morten Brøns, Johan Brinch
Maintainer brinchj@gmail.com
Category Data Structures
Home page https://github.com/brinchj/btree-concurrent
Source repo head: git clone https://github.com/brinchj/btree-concurrent.git
Uploaded by JohanBrinch at 2012-10-31T13:09:44Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 4197 total (12 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for btree-concurrent-0.1.5

[back to package description]

btree-concurrent

A backend agnostic, concurrent BTree with relaxed balance[1] written in Haskell using a mix of IO operations and pure STM.

Although the code does work, it is neither production-ready nor complete.

Features include:

  • Caching: While nodes are periodically saved on persistent storage (e.g. disk) they are cached in-memory during operations.

  • Live flushing: It is possible to save the current version of the tree to disk and run modifying operations at the same time. The nodes are updated buttom-up to ensure a valid tree in the case of a crash.

  • Backend agnosticism: A simple API is used as an abstraction for the persistent storage.

  • Verification: The test-suite uses QuickCheck to compare the trees behaviour to that of Data.Map.

Deficients include:

  • Too much memory usage. Nodes are not stored in a compact fashion and are constantly being serialized/deserialized.

  • findMin and findMax are incomplete and may fail (see TODO for details).

  • The implementation does not parallelize well.

[1] B-trees with relaxed balance, K. S. Larsen & R. Fagerberg, Parallel Processing Symposium, 1995. Proceedings., 9th International