aatree

A Clojure library for AA Trees.

AA Trees are simpler than red-black trees, which makes them easier to modify and extend. But the performance is about the same.

In addition to implementing complete replacements for vector, sorted-set and sorted-map, an extension is provided for lazy deserialization/reserialization. This can be used to minimize the time to deserialize, update and reserialize a large block of data. Because only a small portion of a data block needs to be processed, processing is ridiculously fast when compared to the processing time needed if the entire data block is deserialized / reserialized, as is typical of applications requiring significant durable data.

Another extension is provided to support virtual data structures. Structures no longer need to fit in memory, as only the parts of interest need to be loaded.

Validation has been done using collection-check. Compiled AOT with Clojure 1.7.0. Reflection has been avoided through the use of warn-on-reflection.

##Releases

Wiki

Virtual Structures, easy to use but almost too simple to explain

API

Benchmarks

Immutable Value, Mutable Form

Towards Greater Code Reuse

Durable Applications--File Load and Save

It is not often that you need lazy deserialization when doing a file load. Rather, we are using file load and save here to illustrate how to use the lazy structures of aatree.

1. File Load and Save
2. Using Adler32
3. A 256-bit Checksum

Write Me a Database

It is easy enough to code up a small database, like Calf, using lazy aatree structures. The catch is that the contents of the database must fit in memory.

Virtual Data Structures

The Yearling database supports virtual data structures, which allows for structures that are larger than will fit in memory. Disk Space Management is also part of Yearling.

The Heifer Database

Next up will be a database with a transaction log: Heifer.