Concurrent AVL Tree

Lock-free readable AVL tree with epoch-based memory reclamation and background batch rebalancing. Designed for high-concurrency, high-read workloads with deterministic traversal latency.

Features
Installation
Quick Start
Architecture Overview
Benchmarking & Testing
Contributing & Changelog
License

Features

Lock-Free Reads
Readers traverse without acquiring mutexes or spinlocks.
Epoch-Based Reclamation
Zero use-after-free guarantees via deferred memory disposal.
Batched Rebuilds
Writes are collected, sorted, and applied by a background thread that atomically swaps the root pointer.
Generational Arena
Double-buffered, cache-line aligned allocator eliminates dynamic allocation during rebuilds.
Production-Ready Documentation
Strict rustdoc compliance, exhaustive examples, and CI-enforced lints.

Installation

Add to Cargo.toml:

[dependencies]

concurrent_avl_tree = "0.1.0"

Or via CLI:

cargo add concurrent_avl_tree

Requires Rust 1.91.1 or newer.

Quick Start

use concurrent_avl_tree::concurrent_avl_tree::ConcurrentAVLTree;

fn main() {
    let tree = ConcurrentAVLTree::new();
    tree.insert_key_value(42, "hello".to_string());
    tree.insert_key_value(10, "world".to_string());

    // Allow background rebuild to complete
    std::thread::sleep(std::time::Duration::from_millis(50));

    let value = tree.get_value(42);
    assert_eq!(value, Some("hello".to_string()));
}

Architecture Overview

┌─────────────┐       ┌──────────────┐        ┌───────────────────┐
│   Writers   │──────▶│ Batch Queue  │──────▶│ Background Thread │
└─────────────┘       └──────────────┘        └─────────┬─────────┘
                                                        │
                                                        ▼
┌─────────────┐       ┌──────────────┐        ┌───────────────────┐
│   Readers   │◀──────│ Root Pointer │◀──────│    Arena Swap     │
└─────────────┘       └──────────────┘        └───────────────────┘

Append Phase
Writers push BatchEntry to a mutex-protected collector.
Rebuild Phase
Background thread extracts, sorts, and constructs a new AVL tree in the inactive arena buffer.
Swap Phase
Root AtomicPtr is exchanged. Previous root is queued for epoch-based disposal.
Reclaim Phase
EBR tracks active reader epochs. After a two-epoch grace period, queued callbacks free memory safely.

Benchmarking & Testing

Run unit & doc tests:

cargo test

cargo test --doc

Execute benchmarks (headless safe):

cargo bench -- --noplot

Generate coverage report:

cargo install cargo-llvm-cov

cargo llvm-cov --all-features --open

Contributing & Changelog

See CONTRIBUTING.md for setup, code style, and PR workflow.
View release history in CHANGELOG.md.

concurrent_avl_tree 0.1.0