Crate subms_adaptive_radix_tree 

Adaptive Radix Tree (ART) over byte-string keys - Leis et al., 2013.

Two ideas carry the structure:

• Adaptive nodes. Child storage grows with fan-out: Node4 (up to 4 children, linear scan), Node16 (up to 16), Node48 (a 256-entry byte index into 48 slots), Node256 (direct 256-way). A node promotes to the next size when it fills and demotes when compaction shrinks it, so a sparse node never pays for 256 pointers and a dense one never pays a scan.
• Path compression. A run of single-child bytes collapses into one node’s prefix, so a long shared key stem costs one node, not one per byte. On a diverging insert the node splits at the first mismatch.

use subms_adaptive_radix_tree::Art;
let mut t: Art<i32> = Art::new();
t.insert(b"alice", 1);
t.insert(b"alicia", 2);   // shares "ali", splits at the 4th byte
assert_eq!(t.get(b"alice").copied(), Some(1));
assert_eq!(t.get(b"missing"), None);

Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-adaptive-radix-tree

Re-exports

pub use features::compaction::compact;

pub use features::compaction::delete;

pub use features::concurrent_reads::ArtSnapshot;

pub use features::metrics::ArtMetrics;

pub use features::metrics::MeasuredArt;

pub use features::metrics::NodeTypeCounts;

pub use features::range_scan::Bound;

pub use features::range_scan::range;

pub use features::serialize::ArtCodec;

pub use features::serialize::parse;

pub use features::serialize::write_to;

Modules

features

Opt-in ART feature modules. Each entry is gated by its own Cargo feature; the base Art in lib.rs stays zero-dep.

recipe

SubMsRecipe impl.

Structs

Art