git clone 'https://github.com/laforge49/aatree.git'
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.
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.
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.
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.
There is still a ways to go before we have a production-ready database. The biggest failing is that there is no recovery from a failed transaction except to restart the database. That's just not good enough.