Crate rart

RART - Ryan’s Adaptive Radix Tree

A high-performance, memory-efficient implementation of Adaptive Radix Trees (ART) in Rust.

Overview

Adaptive Radix Trees are a type of trie data structure that automatically adjusts its internal representation based on the number of children at each node, providing excellent performance characteristics:

• Space efficient: Compact representation that adapts to data density
• Cache friendly: Optimized memory layout for modern CPU architectures
• Fast operations: O(k) complexity where k is the key length
• Range queries: Efficient iteration over key ranges

Quick Start

use rart::{AdaptiveRadixTree, ArrayKey};

// Create a new tree with fixed-size keys
let mut tree = AdaptiveRadixTree::<ArrayKey<16>, String>::new();

// Insert some data
tree.insert("hello", "world".to_string());
tree.insert("foo", "bar".to_string());

// Query the tree
debug_assert_eq!(tree.get("hello"), Some(&"world".to_string()));
debug_assert_eq!(tree.get("missing"), None);

// Iterate over entries
for (key, value) in tree.iter() {
    println!("{:?} -> {}", key.as_ref(), value);
}

Key Types

RART supports two main key types:

• ArrayKey<N>: Fixed-size keys up to N bytes, stack-allocated
• VectorKey: Variable-size keys, heap-allocated

Both key types support automatic conversion from common Rust types:

use rart::{ArrayKey, VectorKey};

// From string literals
let key1: ArrayKey<16> = "hello".into();
let key2: VectorKey = "world".into();

// From numeric types
let key3: ArrayKey<8> = 42u64.into();
let key4: VectorKey = 1337u32.into();

Re-exports

pub use keys::KeyTrait;

pub use keys::array_key::ArrayKey;

pub use keys::vector_key::VectorKey;

pub use partials::Partial;

pub use tree::AdaptiveRadixTree;

pub use versioned_tree::VersionedAdaptiveRadixTree;

Modules

iter

Iterator implementation for RART.

keys

Key types and traits for RART.

partials

Partial key types and traits for RART.

range

Range query implementation for RART.

stats

Statistics and introspection for RART.

tree

Adaptive Radix Tree implementation.

versioned_tree

Versioned Adaptive Radix Tree implementation with copy-on-write semantics.