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.
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.
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
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.