db-10 — Execution

What was built, in the order it was built.

1. Rust (src/rust)

  • Cargo.toml declares crate btree10 (lib) and a binary btreectl. Edition 2021, lto = "thin", codegen-units = 1 for release.
  • src/lib.rs contains:
    • Constants T = 2, MAX_KEYS = 3, MIN_KEYS = 1.
    • Node { is_leaf, keys: Vec<(Vec<u8>, Vec<u8>)>, children: Vec<Box<Node>> }.
    • BTree with new, get, insert, delete, serialize_tree, scan, len, is_empty.
    • Free functions split_child, insert_nonfull, delete_from, plus the rebalance helpers borrow_from_prev, borrow_from_next, merge_children.
    • SplitMix64 PRNG (the textbook wrapping-add + xor-mul mix).
    • run_workload(scenario, seed, ops) -> BTree.
    • Inline #[cfg(test)] tests: empty-tree shape, single insert+get, insert + scan ordered, delete-of-absent returns false, delete-then-get returns None, deterministic shape under the three scenarios, scenario-cross seed independence.
  • src/bin/btreectl.rs: thin arg parser (--seed, --ops, --scenario), calls run_workload, writes serialize_tree() bytes to stdout.

2. Go (src/go)

  • go.mod module github.com/10xdev/dse/db10, Go 1.22.
  • btree.go ports the Rust API one-for-one. Pointer-based recursion: *node instead of Box<Node>. The serializer is byte-identical to Rust's: same preorder, same little-endian encodings.
  • btree_test.go mirrors all Rust tests.
  • cmd/btreectl/main.go is the matching CLI.

3. C++ (src/cpp)

  • CMakeLists.txt builds:
    • btree10_lib (static library from src/btree.cc).
    • btreectl (binary linking btree10_lib).
    • test_btree10 (ctest target linking btree10_lib).
    • Flags: -Wall -Wextra -Wpedantic -Werror -O3 -DNDEBUG in Release.
  • src/btree.h declares Node, BTree, run_workload, SplitMix64.
  • src/btree.cc implements them. std::unique_ptr<Node> plays the role of Rust's Box<Node>.
  • src/btreectl.cc is the CLI.
  • tests/test_btree10.cc mirrors Rust's inline tests. Uses #undef NDEBUG before <cassert> so asserts fire under Release; never assert(side_effect).

4. Scripts

  • scripts/verify.sh builds and runs unit tests in all three languages. Exits 0 only if all three are green; prints === OK ===.
  • scripts/cross_test.sh:
    1. Builds Rust/Go/C++ btreectl binaries.
    2. Scenario A: btreectl --seed 42 --ops 500 --scenario inserts in each language; sha256 + size comparison.
    3. Scenario B: btreectl --seed 7 --ops 500 --scenario mixed; sha256 + size comparison.
    4. Spot-check on the rust scenario-A output: assert a known key-prefix appears in the hex stream, guarding against silent-empty-output regressions.
    5. Print === ALL OK ===.

What was deliberately not built

  • Persistence. No file I/O, no page format. db-11.
  • Range scans with iterator-style streaming. scan() returns the whole list; sufficient for tests, lazy for the spec.
  • Bulk-loading from a sorted input. A real B-tree would offer a fast path that builds the tree bottom-up. db-15 may revisit.
  • Concurrency control. No latches, no locks. Trees of T = 2 fit comfortably in a single thread's working set and the lab has no concurrent test harness.