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 (Same representation that is indifferent to insertion order).

Because of these properties, this data structure can be efficiently implemented on top of a key-value store, or even on top of a DHT.

The description and algorithms will follow shortly ;)

This revision created on Fri, 10 Jul 2009 21:34:15 by rapido (spelling)