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
  • C++20
  • CMake
  • Benchmarking
Links

Code for Adaptrees

Bar charts of throughput for adaptive and baseline B-trees on integer, URL and Wikipedia keys
Throughput at 1M keys, million operations per second

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.