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.
- File Load and Save
- Using Adler32
- A 256-bit Checksum
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.
Next up will be a database with a transaction log: Heifer. To reduce code duplication when writing Heifer, Calf and Yearling have been broken into reusable traits.
A trait has also been developed to use an asynchronous channel instead of an agent. Later this will allow us to implement a pipeline for logging.