Adaptrees
A C++20 B+tree for variable-length keys, after the SIGMOD 2025 paper “B-Trees Are Back”. Up to 2× faster inserts than a textbook B+tree.
- Role
- Solo, CS 6360, Database Design
- Stack
- Links

Problem
B-trees with variable-length keys (URLs, titles) waste space and comparisons when nodes store full keys. Müller, Benson and Leis showed that careful node layout closes much of the gap to in-memory structures while keeping pages pageable. I implemented their main techniques to measure them myself.
What I built
Fixed 4 KB slotted pages with 16-byte slots, static per-node prefix truncation, 4-byte key heads for fast comparison, and a 16-entry hint array to narrow binary search.
Iterative descent with a fixed path stack and a fast path for ascending inserts.
A plain baseline B-tree used as a correctness oracle, synthetic integer, URL and Wikipedia-title datasets, and insert, point-lookup and range-scan benchmarks.
Results
- At 1M keys on an Apple M5 Pro (median of 5 runs): 1.3–2.0× faster inserts and 1.2–1.6× faster point lookups than the baseline B+tree.
- The gains are largest on long shared-prefix keys: Wikipedia-title inserts run 2.04× faster, URL lookups 1.56×.
- Range scans over short integer keys are slower (0.70×) because each row rebuilds the full key into a new string; returning suffix views would likely fix it.
- Lookup and scan checksums match the baseline on every dataset.