OxidArt

A blazingly fast Adaptive Radix Tree (ART) implementation in Rust with path compression.

Features

• O(k) complexity - All operations run in O(k) time where k is the key length, not the number of entries
• Path compression - Minimizes memory usage by collapsing single-child paths
• Prefix queries - getn and deln for efficient prefix-based operations
• TTL support - Built-in time-to-live with lazy expiration
• Async runtime integration - First-class support for monoio and tokio
• Zero-copy values - Uses bytes::Bytes for efficient value handling
• Memory efficient - Adaptive node sizing with SmallVec and Slab allocation

Installation

[dependencies]
oxidart = "0.2"
bytes = "1"

Feature Flags

Note: monoio and tokio features are mutually exclusive.

Quick Start

use oxidart::OxidArt;
use bytes::Bytes;

let mut tree = OxidArt::new();

// Insert key-value pairs
tree.set(Bytes::from_static(b"hello"), Bytes::from_static(b"world"));
tree.set(Bytes::from_static(b"hello:foo"), Bytes::from_static(b"bar"));

// Retrieve a value
assert_eq!(tree.get(Bytes::from_static(b"hello")), Some(Bytes::from_static(b"world")));

// Get all entries with a prefix
let entries = tree.getn(Bytes::from_static(b"hello"));
assert_eq!(entries.len(), 2);

// Delete a key
tree.del(Bytes::from_static(b"hello"));

// Delete all keys with a prefix
tree.deln(Bytes::from_static(b"hello"));

TTL Support

With the ttl feature (enabled by default), you can set expiration times on entries:

use oxidart::OxidArt;
use bytes::Bytes;
use std::time::Duration;

let mut tree = OxidArt::new();

// Update internal clock (call periodically from your event loop)
tree.set_now(current_timestamp_secs);

// Insert with TTL - expires after 60 seconds
tree.set_ttl(
    Bytes::from_static(b"session:abc"),
    Duration::from_secs(60),
    Bytes::from_static(b"user_data")
);

// Insert without TTL - never expires
tree.set(Bytes::from_static(b"config:key"), Bytes::from_static(b"value"));

// Expired entries are automatically filtered on get/getn

Async Runtime Integration

For TTL support, we recommend using the shared_with_ticker constructor which creates a shared tree with automatic timestamp updates.

With monoio (single-threaded)

[dependencies]
oxidart = { version = "0.1", features = ["monoio"] }

use oxidart::OxidArt;
use bytes::Bytes;
use std::time::Duration;

#[monoio::main(enable_timer = true)]
async fn main() {
    // Recommended: creates Rc<RefCell<OxidArt>> with automatic ticker
    let tree = OxidArt::shared_with_ticker(Duration::from_millis(100));

    // Use TTL
    tree.borrow_mut().set_ttl(
        Bytes::from_static(b"session"),
        Duration::from_secs(3600),
        Bytes::from_static(b"data"),
    );

    // Your server loop...
}

With tokio (multi-threaded)

[dependencies]
oxidart = { version = "0.1", features = ["tokio"] }

use oxidart::OxidArt;
use bytes::Bytes;
use std::time::Duration;

#[tokio::main]
async fn main() {
    // Recommended: creates Arc<Mutex<OxidArt>> with automatic ticker
    let tree = OxidArt::shared_with_ticker(Duration::from_millis(100)).await;

    // Use TTL
    tree.lock().await.set_ttl(
        Bytes::from_static(b"session"),
        Duration::from_secs(3600),
        Bytes::from_static(b"data"),
    );

    // Your server loop...
}

API

Why ART?

Adaptive Radix Trees combine the efficiency of radix trees with adaptive node sizes:

• Unlike hash maps, ART maintains key ordering and supports efficient range/prefix queries
• Unlike B-trees, ART has O(k) lookup independent of the number of entries
• Path compression eliminates redundant nodes, reducing memory overhead

License

Licensed under the Mozilla Public License 2.0.