bbtree: a fast Rust B-tree whose code was written by LLMs

Developer Xiangpeng Hao has published a blog post introducing bbtree, a B-tree data structure for Rust that he says is a drop-in replacement for the standard library's BTreeMap and BTreeSet. Notably, Hao describes the code as having been written by large language models under his guidance, with the project validated through formal verification, model checking, deterministic simulation, and fuzzing.

According to Hao's own benchmarks, bbtree runs 5 times faster than Rust's standard BTreeMap on a single thread and 12 times faster than the crossbeam-skiplist crate at 96 threads, while using 30% less memory. He also tested bbtree as a drop-in replacement inside four existing LSM-tree projects (fjall, SlateDB, Tonbo, and Lance) and the Turso database, reporting speedups ranging from roughly 1.2 times to nearly 7 times depending on the operation. A companion crate, bbtree-mmap, lets a tree be memory-mapped from disk and queried instantly without rebuilding, which Hao says answers the first query 160 to 2,500 times faster than rebuilding a standard BTreeMap after a restart.

The post walks through the design choices behind these numbers, including cache-miss-driven node sizing, inline and prefix-compressed keys, and a lightweight async-based batch lookup scheme. The code is open source on GitHub.

Why it matters

It's a concrete example of LLM-written systems code delivering big measured speedups in a performance-critical data structure, backed by formal verification and fuzzing.

Source: Xiangpeng Hao