Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

A backend agnostic, concurrent BTree written in Haskell

branch: master

Fetching latest commit…

Octocat-spinner-32-eaf2f5

Cannot retrieve the latest commit at this time

Octocat-spinner-32 Data
Octocat-spinner-32 Test
Octocat-spinner-32 .gitignore
Octocat-spinner-32 IOTreeTestQC.hs
Octocat-spinner-32 LICENSE
Octocat-spinner-32 README.md
Octocat-spinner-32 Setup.hs
Octocat-spinner-32 TODO.org
Octocat-spinner-32 btree-concurrent.cabal
README.md

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

Something went wrong with that request. Please try again.