ArborDb: a Rust document store where reading one field doesn't get slower as the record grows

ArborDb: a Rust document store where reading one field doesn't get slower as the record grows

Most embedded document stores make you pay the same price to read one field as to read the whole record: they deserialize the entire value, then hand you the field you asked for. That cost grows with the record. Read one number out of a 128-field document, or one element out of a 10 000-element list, and you've just decoded all of it.

ArborDb is a pure-Rust, typed, transactional, indexed document store built around the opposite idea: store each value as one zero-copy blob and read a field in place, without touching the rest. It's the 1.0 successor to StratoDb - same typed model and derive surface, a completely different storage strategy.

The core idea: one blob per value, navigated in place

A value in ArborDb is a tree of objects, lists, and scalar leaves. Instead of shredding each scalar into its own keyed row (StratoDb's old approach), ArborDb serializes the whole tree into a single blob in a single engine entry, laid out with offset tables:

• a leaf is its scalar's byte encoding;
• a list is a count plus a u32 offset table - O(1) jump to element i;
• an object is a count plus a name-sorted (name, offset) table - O(log n) field lookup.

A bespoke codec - think "rkyv, but hand-written for this layout" - reads scalars straight out of the engine's page bytes. No decode into an owned tree, no alignment requirement (every read is an explicit from_be_bytes over an unaligned slice). It's layered over the redb key-value engine, which is kept fully opaque: no engine type ever appears in ArborDb's public API. The payoff is the headline benchmark below. But first, what it feels like to use.

Quick start

use std::collections::BTreeMap;
use arbordb::{data::Scalar, ArborDb, Value};

fn main() -> arbordb::AdbResult<()> {
    let db = ArborDb::create_in_memory()?; // or ArborDb::create(path) for a file
    let users = db.open_table("users")?;

    // Writes are transactional: stage, then commit.
    let w = users.write()?;
    w.store_value(
        "alice",
        &Value::Node(BTreeMap::from([
            (String::from("age"), Value::Leaf(Scalar::I64(30))),
        ])),
    )?;
    w.commit()?;

    // Reads see committed data; a field is reached by its intra-value path.
    let r = users.read()?;
    assert_eq!(r.get_as::<i64>("alice", "age")?, Some(30));
    Ok(())
}

Typed access with #[derive(AData)]

The dynamic Value API is always there, but with the derive feature you get typed storage with a Serde-style attribute set (rename, skip, default, with, from/into/try_from, enum representations, generics, flatten):

use arbordb::{AData, ArborDb};

#[derive(AData, Debug, PartialEq)]
struct User {
    name: String,
    age: u32,
}

fn main() -> arbordb::AdbResult<()> {
    let db = ArborDb::create_in_memory()?;
    let users = db.open_table("users")?;

    let w = users.write()?;
    w.store::<User>("alice", &User { name: String::from("Alice"), age: 30 })?;
    w.commit()?;

    let r = users.read()?;
    assert_eq!(
        r.load::<User>("alice")?,
        Some(User { name: String::from("Alice"), age: 30 }),
    );
    Ok(())
}

The derive also generates lazy accessors - ArborUser<'_> / ArborUserMut<'_> - that navigate into the one blob without a full decode, so you can read (or patch) a single nested field of a large typed value.

A table is a virtual filesystem

This is the part that makes ArborDb feel different. A table isn't a flat keyspace - it's a tree of directories and files, and the filesystem operations sit right next to the value operations:

let w = table.write()?;
w.store_value("users/alice", &user("Alice", 30))?;
w.store_value("users/bob", &user("Bob", 40))?;
w.mv("users/bob", "users/robert")?;  // relink a name: O(1), identity preserved
w.cp("users/alice", "archive/alice")?; // deep copy under fresh keys
w.commit()?;

let r = table.read()?;
for entry in r.ls("users")? {
    println!("{}", entry.name());
}

Every node carries an opaque 16-byte AKey that survives renames and moves - mv relinks a name in O(1) and the key doesn't change. That's the reason for the two distinct path kinds:

• an APath (users/alice) addresses a whole value in the filesystem - resolved by walking directories from the root, amortized by a per-table cache;
• a VPath (home/city, tags[2]) navigates inside a value down to a scalar leaf, read zero-copy over the blob.

Access paths are never persisted, so a value's identity follows its key, not its location.

Secondary indexes

Declare them on the type, register with one call, and they're back-filled and maintained on write:

#[derive(AData)]
#[arbor(index(name = "by_age", columns(age)))]
struct User {
    name: String,
    age: i64,
}

users.create_indexes::<User>("users/*")?; // create + back-fill, scoped to a path pattern

// Query in index order; an empty prefix matches all.
let r = users.read()?;
let ages: Vec<i64> = r.find::<User>("by_age", &[])?.into_iter().map(|u| u.age).collect();

Indexes are named, composite (ordered columns), per-column ASC/DESC, optionally unique, and scoped to a path pattern. The key encoding is order-preserving across types, byte lengths and sign, so a prefix on a composite index returns every match ordered by the trailing columns, and reversing a query walks the index backward.

The headline: partial reads don't scale with the value

This is the whole point of the design. Because a value is one blob with offset tables, reaching one field or one list element is a jump straight to it - so ArborDb stays flat as the value grows, while a decode-the-whole-blob store grows linearly.

Read one field of an N-field record (on-disk):

Read one element of an N-element list (on-disk):

ArborDb's cost is essentially constant across a 40× range of data: 8.6× ahead at 128 fields, and over 500× ahead at 10 240 list elements. And on the "read + full decode" path - where nothing is skipped - ArborDb rides within ~4% of the raw engine it's built on (693 ns vs redb+bincode's 665 ns), while beating native_db by 1.9× and StratoDb by 1.7×.

Being honest about the tradeoffs

Fast partial reads aren't a free lunch, and the benchmarks page says so:

• Partial writes are conditional. Overwriting a scalar with one of the same byte width patches the blob in place - no decode, no re-encode (that's what puts update_score ahead of every other typed store). But a variable-width or structural edit re-encodes the one blob. Updating one element of a huge packed list trades write cost for the read speed above. A deliberate tradeoff, not magic.
• Bulk insert under one directory is ~O(N²) by design. Inserting N files into one directory re-links each into that directory's (growing) blob. It's a real property of the filesystem model - measured, not hidden.
• Numbers are indicative medians from a single machine; treat the ratios and the scaling shape (flat vs linear) as the durable signal.

What else is in the box

All opt-in via cargo features, nothing on by default:

• JSON / YAML export - a hand-written, dependency-free, read-only renderer (no serde_json / serde_yaml), for a stored value or an in-memory subtree.
• Entry timestamps - POSIX-style created / modified / accessed per node, stored out-of-band so the data format is unchanged and access times are buffered (a read burst never becomes a write burst).
• Permissions & integrity - user/password auth (Argon2id + XChaCha20-Poly1305; passwords are never stored), per-node graded ACLs (None ⊂ Access ⊂ Modify ⊂ Delete), and dual tamper detection - a keyed BLAKE3 MAC for authenticated users plus an Ed25519 signature a keyless guest can verify - so an edit that bypasses ArborDb to touch the raw file is caught.
• Rooted views - make every path relative to a fixed root and scope index queries to that subtree.
• Big numbers - arbitrary-precision int / fixed-precision float / rational, each as a native scalar or as composite data, with correct index ordering.
• serde and parallel (rayon) features too.

Status & trying it

ArborDb is at its 1.0 milestone: feature-complete, with a stable public API and on-disk format, runnable examples, a criterion benchmark suite, and CI. It's not yet on crates.io, so depend on it by git for now:

[dependencies]
arbordb = { version = "1.0.0", features = ["derive"] }

Builds on a recent stable toolchain (edition 2024).

👉 Repo: https://github.com/corebreaker/arbordb

If the "one blob, read in place" model is interesting to you - or if you have a workload where partial reads dominate - I'd love feedback, issues, and stars. What would you want to see before it lands on crates.io?