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.

Table of Contents

• Features
• Installation
• Quick Start
• Architecture Overview
  • Append Phase
  • Rebuild Phase
  • Swap Phase
  • Reclaim Phase
• 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     │
└─────────────┘       └──────────────┘        └───────────────────┘

1. Append Phase
   Writers push BatchEntry to a mutex-protected collector.
2. Rebuild Phase
   Background thread extracts, sorts, and constructs a new AVL tree in the inactive arena buffer.
3. Swap Phase
   Root AtomicPtr is exchanged. Previous root is queued for epoch-based disposal.
4. 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.

License

SPDX-License-Identifier: MIT
© 2026 Dzulkifli Anwar
See LICENSE for full terms.