The Purely Functional Canonical B-Tree

I still need a better name, but there it is.

A data structure that has the following properties:

  • B-Tree Like (Entries are consecutively stored in blocks)
  • Purely Functional (Immutable and confluently persistent).
  • Canonical Representation (Always the same representation - indifferent to insertion order).

Because of these properties:

  • it has ACID properties.
  • it can be stored efficiently and incrementally.
  • it can operate on top of a DHT.
  • set operations (such as union, difference, etc) can be performed with maximum theoretical efficiency bounds (probabilistic)
  • immutable instances (versions) can be matched efficiently against other instances (probabilistic)

Description and algorithms will follow shortly ;)

This revision created on Fri, 10 Jul 2009 21:44:53 by rapido