IAVL Tree Implementation

An immutable, versioned AVL+ tree implementation in Rust, designed for blockchain applications.

Features

• Immutable versioned storage: Each tree modification creates a new version while preserving previous states
• Efficient persistence: Write-ahead logging (WAL) for crash recovery
• Balanced operations: Self-balancing AVL tree with O(log n) operations
• Range queries: Efficient iteration over key ranges
• Memory and disk storage: In-memory and persistent storage implementations
• Batch operations: Atomic write batches for efficient updates

Core Components

• IAVLTree: The main balanced tree implementation
• IAVLDB: Persistent storage wrapper with WAL support
• MemTree: Pure in-memory implementation
• Overlay: Transactional overlay for atomic changes
• KVStore: Common key-value store trait

Basic Usage

use iavl::{IAVLTree, KVStore};

let mut tree = IAVLTree::new();

// Insert key-value pairs
tree.set(b"key1".to_vec(), b"value1".to_vec());
tree.set(b"key2".to_vec(), b"value2".to_vec());

// Get values
assert_eq!(tree.get(b"key1"), Some(&b"value1"[..]));

// Range iteration
for (key, value) in tree.range(b"key1"..b"key3") {
    println!("{:?} => {:?}", key, value);
}

// Remove keys
tree.remove(b"key1");

Persistent Storage Example

use iavl::{IAVLDB, KVStore};

let mut db = IAVLDB::new(/* storage path */);

// Make changes
db.set(b"key1".to_vec(), b"value1".to_vec());

// Save version and persist to disk
let version_hash = db.save_version();

Safety

This implementation uses #![forbid(unsafe_code)] to ensure memory safety.

License

Apache 2.0