Crate astrie

ASTrie (Adaptive Segmented Trie)

astrie is a high-performance hybrid data structure that combines the benefits of tries and B+ trees to provide efficient key-value storage with adaptive behavior based on data patterns.

Features

• Hybrid Structure: Dynamically switches between trie and B+ tree nodes based on data characteristics
• Efficient Operations: O(k) or O(log n) lookups, where k is key length
• Range Queries: Fast range scans with ordered iteration
• Thread-Safe: Concurrent access support using fine-grained locking
• Memory Efficient: Adaptive storage strategy to minimize memory usage
• Generic: Supports any key type that implements required traits

Usage

Add this to your Cargo.toml:

[dependencies]
astrie = "0.1.0"

Example

use astrie::ASTrie;

// Create a new ASTrie with string keys and integer values
let trie = ASTrie::<String, i32>::new();

// Insert some data
trie.insert("hello".to_string(), 1);
trie.insert("world".to_string(), 2);

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

// Range query
let range = trie.range(&"h".to_string(), &"w".to_string());
assert_eq!(range.len(), 1);

Custom Types

To use custom types as keys, implement the required traits:

use astrie::{ToBytes, FromBytes};

#[derive(Clone, Ord, PartialOrd, Eq, PartialEq)]
struct CustomKey {
    id: u32,
    name: String,
}

impl ToBytes for CustomKey {
    fn to_bytes(&self) -> Vec<u8> {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(&self.id.to_be_bytes());
        bytes.extend_from_slice(self.name.as_bytes());
        bytes
    }
}

impl FromBytes for CustomKey {
    fn from_bytes(bytes: &[u8]) -> Option<Self> {
        if bytes.len() < 4 {
            return None;
        }
        let id = u32::from_be_bytes(bytes[0..4].try_into().ok()?);
        let name = String::from_utf8(bytes[4..].to_vec()).ok()?;
        Some(CustomKey { id, name })
    }
}

Performance

The ASTrie structure adapts to your data patterns:

• For sparse key spaces: Uses trie nodes for O(k) lookups
• For dense key ranges: Uses B+ tree nodes for O(log n) lookups
• For range queries: O(log n + m) where m is the size of the range

Thread Safety

ASTrie uses fine-grained locking for concurrent access:

use std::thread;
use std::sync::Arc;
use astrie::ASTrie;

let trie = Arc::new(ASTrie::<String, i32>::new());
let mut handles = vec![];

for i in 0..10 {
    let trie_clone = trie.clone();
    let handle = thread::spawn(move || {
        trie_clone.insert(format!("key-{}", i), i);
    });
    handles.push(handle);
}

for handle in handles {
    handle.join().unwrap();
}

Configuration

Key constants that can be tuned:

const TRIE_DEPTH_THRESHOLD: usize = 8;    // Max trie depth before conversion
const BTREE_MIN_OCCUPANCY: f32 = 0.4;     // Min B+ tree node occupancy
const NODE_SIZE: usize = 256;             // Node size for cache alignment

Use Cases

ASTrie is particularly well-suited for:

• Key-value stores with range query requirements
• Network routing tables (IP prefix matching)
• Auto-complete systems
• Time-series databases
• In-memory caches

Error Handling

Operations that might fail return Option or Result:

use astrie::ASTrie;
let trie = ASTrie::<String, i32>::new();

// Get returns Option
match trie.get(&"key".to_string()) {
    Some(value) => println!("Found: {}", value),
    None => println!("Key not found"),
}

// Range queries return empty Vec if no matches
let empty_range = trie.range(&"z".to_string(), &"zzz".to_string());
assert!(empty_range.is_empty());

Implementation Details

The adaptive behavior is controlled by two main mechanisms:

1. Depth-based Conversion: Trie nodes beyond TRIE_DEPTH_THRESHOLD are converted to B+ tree nodes
2. Occupancy-based Conversion: B+ tree nodes below BTREE_MIN_OCCUPANCY are converted to tries

License

This project is licensed under the Apache 2.0 License - see the LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Structs

ASTrie

Main ASTrie data structure

Traits

FromBytes

Key trait for reconstructing types from bytes

ToBytes

Key trait for converting types to byte representation