This is yet another implementation of an Adaptive Radix Tree (ART) in Rust. ARTs are an ordered associative (key-value) structure that outperform BTrees for many use cases.
The implementation is based on the paper The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases by Viktor Leis, Alfons Kemper, and Thomas Neumann.
I have not (yet) implemented the concurrent form described in later papers.
During implementation I looked at the following implementations, and borrowed some flow and ideas from them:
Performance boost can be gained through fixed sized keys and partials. There are a selection of key types and partials provided under the partials
module.
I believe my implementation to be competitive, performance wise. The included benches compare against BTreeMap
,
HashMap
, and art-rs
and show what you'd expect: performance between a hashtable and a btree for random inserts and
retrievals, but sequential inserts and retrievals are much faster than either.
Some notes:
stable
Rust.unsafe
code for performance reasons, but the public API is safe.fuzz/
) is included, but will fully work for nightly
only. Has already been used to identify
some bugsMore documentation to come. Still working at smoothing the rough corners. Contributions welcome.