Rust storage engine / mcranny/btree-storage-engine

Disk-backed B-tree storage engine in Rust.

One database file, 4096-byte pages, signed 64-bit keys, byte-string values up to 256 bytes, a bounded 64-page LRU pager cache, checksummed redo WAL, range scans, and rebalancing deletion.

Language Rust disk-backed pages

Validation 36 tests 10 files with tests

Integration tests 7 files point lookup / insert / delete / range / SQLite

Property tests proptest generated put/delete/get traces

On-disk page layout

docs/design.md and src/format.rs

page 0 metadata magic BTREEDB\0 format version root page id page count free-list head

node page 0..4 magic NODE 4 node type 6..8 key count 8..16 parent page id 32..3568 thirteen 272-byte records 3568..3680 fourteen child page ids 3680..4096 reserved zero-fill

free page magic FREE next free page id at offset 8 reused after merge/root contraction

Split and validation artifacts

github.com/mcranny/btree-storage-engine

Top-down split path

Full children are split before descent. The median record moves into the parent; the left and right nodes each keep six records for minimum degree t = 7.

let mut left_entries = child.entries().to_vec();
let right_entries = left_entries.split_off(MIN_DEGREE);
let median = left_entries
    .pop()
    .expect("a full node always contains a median entry");

let right_id = self.pager.allocate_page()?;
let left = Node::new(child.kind(), Some(parent_id), left_entries, left_children)?;
let right = Node::new(child.kind(), Some(parent_id), right_entries, right_children)?;

parent_entries.insert(child_index, median);
parent_children.insert(child_index + 1, right_id);

SQLite differential check

The test harness applies the same generated operation stream to this engine and an in-memory SQLite table, then compares point lookup and full-range output.

match operation {
    Op::Put(key, value) => {
        engine.put(key, value.clone()).unwrap();
        connection.execute(
            "INSERT OR REPLACE INTO kv VALUES (?1, ?2)",
            params![key, value],
        ).unwrap();
    }
    Op::Delete(key) => {
        let engine_removed = engine.delete(key).unwrap();
        let sqlite_removed =
            connection.execute("DELETE FROM kv WHERE key = ?1", [key]).unwrap() != 0;
        prop_assert_eq!(engine_removed, sqlite_removed);
    }
    Op::Get(key) => {
        prop_assert_eq!(engine.get(key).unwrap(), sqlite_get(&connection, key));
    }
}

Correctness lineage

neo-updater -> btree-storage-engine

neo-updater

JPL CAD/SBDB records are normalized into SQLite. Lambert solutions are kept only after endpoint propagation checks.

btree-storage-engine

The storage engine goes one layer lower: fixed page layout, WAL-backed mutations, and operation-by-operation SQLite differential checks.

Implementation facts

README.md and docs/design.md

Public API	`open`, `put`, `get`, `delete`, `range`, `close`.
Page format	Page zero metadata; every other page is a B-tree node or reusable free page. Node pages store thirteen fixed-width records and fourteen child page IDs.
Mutation durability	Each public mutation writes checksummed full-page after-images to a redo WAL before dirty database pages are checkpointed.
Deletion	Rebalances before descent by borrowing through the parent or merging a child, separator, and sibling; merged pages return to the persistent free list.
Repo	https://github.com/mcranny/btree-storage-engine