Radix Immutable

An immutable radix trie in Rust with structural sharing via Arc. Each mutation returns a new trie, sharing unchanged subtrees with the original.

Originally forked from radix_trie and substantially rewritten.

Features

• Immutable API — insert/remove return new tries; originals are unchanged
• Structural sharing — unchanged subtrees are shared via Arc, making clones cheap
• Longest prefix match — find the most specific stored prefix for a key (routing, path resolution)
• Prefix iteration — iterate all entries under a prefix without scanning the full trie
• Prefix views — lightweight subtrie handles for comparison and lookup
• Structural hashing — lazily cached hashes for fast subtree equality checks
• BTreeMap children — deterministic iteration order, no sort overhead
• Serde support — optional serde feature flag for serialization
• Key generic — supports any type convertible to bytes (String, Vec<u8>, custom types)

Usage

[dependencies]
radix_immutable = "0.1"

# With serde support:
radix_immutable = { version = "0.1", features = ["serde"] }

Quick start

use radix_immutable::StringTrie;

let trie = StringTrie::<String, i32>::new()
    .insert("hello".to_string(), 1)
    .insert("help".to_string(), 2)
    .insert("world".to_string(), 3);

// Lookup
assert_eq!(trie.get(&"hello".to_string()), Some(&1));

// Longest prefix match
let trie = trie.insert("/api".to_string(), 10)
    .insert("/api/users".to_string(), 20);
assert_eq!(
    trie.longest_prefix_match(&"/api/users/123".to_string()),
    Some((&"/api/users".to_string(), &20))
);

// Prefix iteration
let hel_entries: Vec<_> = trie.iter_prefix("hel".to_string()).collect();
assert_eq!(hel_entries.len(), 2); // "hello" and "help"

// Collect from iterator
let trie: StringTrie<String, i32> = vec![
    ("a".to_string(), 1),
    ("b".to_string(), 2),
].into_iter().collect();

Performance

Why not just use a HashMap?

Prefix operations on a trie are O(key length), independent of collection size. A HashMap must scan every entry.

With 1,000 path-like keys:

Structural sharing vs. cloning

Inserting into an immutable trie shares unchanged subtrees via Arc. A HashMap must clone the entire map to get a new version.

With 1,000 entries, inserting one new key:

The trie is ~124x faster because it only allocates nodes along the new key's path.

Memory: snapshots via structural sharing

Keeping 10 snapshots of a 500-entry collection (each with one additional key):

The trie uses ~36x less memory because each version shares unchanged subtrees with the original.

Functional patterns

Immutable data structures enable patterns that are expensive or awkward with mutable collections. With structural sharing, the trie handles these naturally:

The trie's advantage grows with collection size — branching from a 500-entry base is ~26x faster because the trie forks via Arc, while the HashMap must clone all 500 entries for each branch.

Lookup scaling

Getting 100 keys from tries of increasing size (lookup time depends on key length, not collection size):

Run benchmarks yourself with cargo bench.

Documentation

https://docs.rs/radix_immutable/

Original radix_trie Contributors

• Allan Simon (@allan-simon)
• Andrew Smith (@andrewcsmith)
• Arthur Carcano (@NougatRillettes)
• Devin Ragotzy (@DevinR528)
• @hanabi1224
• Jakob Dalsgaard (@jakobdalsgaard)
• Michael Sproul (@michaelsproul)
• Robin Lambertz (@roblabla)
• Sergey (@Albibek)
• Stuart Hinson (@stuarth)
• Vinzent Steinberg (@vks)

License

MIT License. Copyright Micah Fitch, Michael Sproul and contributors 2015-present.