db/radixtree

RadixTree

A persistent radix tree implementation in Rust using OurDB for storage.

Overview

RadixTree is a space-optimized tree data structure that enables efficient string key operations with persistent storage. This implementation provides a persistent radix tree that can be used for efficient prefix-based key operations, such as auto-complete, routing tables, and more.

A radix tree (also known as a patricia trie or radix trie) is a space-optimized tree data structure that enables efficient string key operations. Unlike a standard trie where each node represents a single character, a radix tree compresses paths by allowing nodes to represent multiple characters (key segments).

Key characteristics:

• Each node stores a segment of a key (not just a single character)
• Nodes can have multiple children, each representing a different branch
• Leaf nodes contain the actual values
• Optimizes storage by compressing common prefixes

Features

• Efficient prefix-based key operations
• Persistent storage using OurDB backend
• Memory-efficient storage of strings with common prefixes
• Support for binary values
• Thread-safe operations through OurDB

Usage

Add the dependency to your Cargo.toml:

[dependencies]
radixtree = { path = "../radixtree" }

Basic Example

use radixtree::RadixTree;

fn main() -> Result<(), radixtree::Error> {
    // Create a new radix tree
    let mut tree = RadixTree::new("/tmp/radix", false)?;
    
    // Set key-value pairs
    tree.set("hello", b"world".to_vec())?;
    tree.set("help", b"me".to_vec())?;
    
    // Get values by key
    let value = tree.get("hello")?;
    println!("hello: {}", String::from_utf8_lossy(&value)); // Prints: world
    
    // List keys by prefix
    let keys = tree.list("hel")?; // Returns ["hello", "help"]
    println!("Keys with prefix 'hel': {:?}", keys);
    
    // Get all values by prefix
    let values = tree.getall("hel")?; // Returns [b"world", b"me"]
    
    // Delete keys
    tree.delete("help")?;
    
    Ok(())
}

API

Creating a RadixTree

// Create a new radix tree
let mut tree = RadixTree::new("/tmp/radix", false)?;

// Create a new radix tree and reset if it exists
let mut tree = RadixTree::new("/tmp/radix", true)?;

Setting Values

// Set a key-value pair
tree.set("key", b"value".to_vec())?;

Getting Values

// Get a value by key
let value = tree.get("key")?;

Updating Values

// Update a value at a given prefix
tree.update("prefix", b"new_value".to_vec())?;

Deleting Keys

// Delete a key
tree.delete("key")?;

Listing Keys by Prefix

// List all keys with a given prefix
let keys = tree.list("prefix")?;

Getting All Values by Prefix

// Get all values for keys with a given prefix
let values = tree.getall("prefix")?;

Performance Characteristics

• Search: O(k) where k is the key length
• Insert: O(k) for new keys, may require node splitting
• Delete: O(k) plus potential node cleanup
• Space: O(n) where n is the total length of all keys

Use Cases

RadixTree is particularly useful for:

• Prefix-based searching
• IP routing tables
• Dictionary implementations
• Auto-complete systems
• File system paths
• Any application requiring efficient string key operations with persistence

Implementation Details

The RadixTree implementation uses OurDB for persistent storage:

• Each node is serialized and stored as a record in OurDB
• Node references use OurDB record IDs
• The tree maintains a root node ID for traversal
• Node serialization includes version tracking for format evolution

For more detailed information about the implementation, see the ARCHITECTURE.md file.

Running Tests

The project includes a comprehensive test suite that verifies all functionality:

# Run all tests
cargo test

# Run specific test file
cargo test --test basic_test
cargo test --test prefix_test
cargo test --test getall_test
cargo test --test serialize_test

Running Examples

The project includes example applications that demonstrate how to use the RadixTree:

# Run the basic usage example
cargo run --example basic_usage

# Run the prefix operations example
cargo run --example prefix_operations

Benchmarking

The project includes benchmarks to measure performance:

# Run all benchmarks
cargo bench

# Run specific benchmark
cargo bench -- set
cargo bench -- get
cargo bench -- prefix_operations

License

This project is licensed under the same license as the HeroCode project.