vsdb

A high-performance, embedded key-value database for Rust with an API that feels like standard collections.

What it does

• Persistent collections — Mapx (like HashMap), MapxOrd (like BTreeMap), backed by MMDB (pure-Rust LSM-Tree)
• Git-model versioning — VerMap provides branching, commits, three-way merge, and rollback over a COW B+ tree with structural sharing; garbage collection is fully automatic via reference counting and MMDB background compaction
• Merkle trie — MptCalc (Merkle Patricia Trie) and SmtCalc (Sparse Merkle Tree) as stateless computation layers; VerMapWithProof integrates VerMap with MptCalc for versioned 32-byte Merkle root commitments
• Slot-based index — SlotDex for efficient, timestamp-based paged queries via a skip-list-like tier structure
• Vector index — VecDex for approximate nearest-neighbor search via a pure-Rust HNSW implementation; supports L2, Cosine, and InnerProduct metrics with filtered search

Quick start

cargo add vsdb

use vsdb::versioned::map::VerMap;

let mut m: VerMap<u32, String> = VerMap::new();
let main = m.main_branch();

m.insert(main, &1, &"hello".into()).unwrap();
m.commit(main).unwrap();

let feat = m.create_branch("feature", main).unwrap();
m.insert(feat, &1, &"updated".into()).unwrap();
m.commit(feat).unwrap();

// Branches are isolated
assert_eq!(m.get(main, &1).unwrap(), Some("hello".into()));
assert_eq!(m.get(feat, &1).unwrap(), Some("updated".into()));

// Three-way merge: source wins on conflict
m.merge(feat, main).unwrap();
assert_eq!(m.get(main, &1).unwrap(), Some("updated".into()));

m.delete_branch(feat).unwrap();
// Dead commits and B+ tree nodes are reclaimed automatically —
// no manual gc() call required.

Architecture

vsdb (workspace)
+-- core/    vsdb_core   Storage engine (MMDB), MapxRaw, PersistentBTree
+-- strata/  vsdb        High-level crate (the one users depend on)
     +-- basic/          Mapx, MapxOrd, MapxOrdRawKey, Orphan
     +-- versioned/      VerMap (branch, commit, merge, diff)
     +-- trie/           MptCalc, SmtCalc, VerMapWithProof
     +-- slotdex/        SlotDex
     +-- dagmap/         DagMapRaw, DagMapRawKey
     +-- vecdex/         VecDex (HNSW vector index)

Module overview

Module	Key types	Purpose
basic	Mapx, MapxOrd, Orphan	Persistent, typed collections
versioned	VerMap, BranchId, CommitId	Git-model versioned KV store with COW B+ tree
trie	MptCalc, SmtCalc, SmtProof, VerMapWithProof	Stateless Merkle tries + VerMap integration
slotdex	SlotDex	Skip-list-like index for timestamp-based paged queries
dagmap	DagMapRaw, DagMapRawKey	DAG-based collections
vecdex	VecDex, HnswConfig	Approximate nearest-neighbor vector index (HNSW)

Trie + VerMap integration

  VerMap<K,V>          MptCalc / SmtCalc
  (persistence)        (computation)
  +-------------+      +-------------+
  | branch/     |      | in-memory   |
  | commit/     | diff | trie nodes  |  root_hash()
  | merge/      |----->| (ephemeral) |-------------> [u8; 32]
  | rollback    |      |             |
  +-------------+      +-------------+
       |                      |
       |                 save_cache()
       |                 load_cache()
       |                      |
       |                +-----v-----+
       |                | disk cache| (disposable)
       +----------------+-----------+

VerMapWithProof wraps a VerMap and an MptCalc. On each merkle_root() call it computes an incremental diff from the last sync point and applies it to the trie, avoiding full rebuilds. A disposable on-disk cache makes restarts cheap.

SmtCalc additionally supports prove() / verify_proof() for constant-time (256-hash) membership and non-membership proofs.

Documentation

• API Examples
• Versioned Module — Architecture & Internals

License

MIT