bbtree++ is a C++20 port of bbtree, the B+-tree ordered map by Xiangpeng Hao originally implemented in Rust.

• bbtree++ outperforms the original in most cases: see bbtree/bench/COMPARISON.md for details
• bbtree++ outperforms the standard std::map in almost all cases while using less memory: see bbtree/bench/CPP_MAPS.md for details

These show maps of 1M entries; bbtree/bench/charts has the charts of every size.

bbtree++ keeps the Rust original's design: its nodes and their layouts, inline keys, prefix stripping, batched operations, optimistic lock coupling and file maps. design/ holds the original's design documents, which bbtree++ follows.

• bbtree::unsync::bbtree_map and bbtree_set: drop-in replacements for std::map and std::set, for one thread.
• bbtree::bbtree_map: the map threads share, through optimistic lock coupling, with closures instead of handles.
• File maps (bbtree/file.hpp) and bbtree-mmap: maps compacted into a file and looked up where they lie.
• bbtree::pooled_allocator: packs a map's pages into 2 MiB chunks on huge pages. Without mimalloc or another allocator replacing operator new, it makes large maps up to 2× faster to walk and build on glibc, as GLIBC_TUNABLES=glibc.malloc.hugetlb=1 in the environment also does; give many small maps copies of one allocator to share its pool (PORTING.md, pooled pages).
• Zero dependencies: headers only, C++20, Clang 15+ or GCC 13+; CMake 3.28+.

#include <bbtree/unsync/map.hpp>

bbtree::unsync::bbtree_map<std::uint64_t, std::string> map;
map.insert({1, "one"});
map[2] = "two";
for (const auto& [key, value] : map) {  // const auto& or auto&&, not auto&
  std::printf("%lu %s\n", key, value.c_str());
}
map.for_each([](const auto& key, auto& value) { value += '!'; });  // a leaf at a time, faster than range-for
auto upper = map.split_off(2);  // O(log n)
std::array<std::uint64_t, 64> keys = ...;
auto values = map.get_many(keys);  // batched lookups, misses overlapped

#include <bbtree/map.hpp>

bbtree::bbtree_map<std::uint64_t, std::uint64_t> map;
{
  std::jthread a([&] { map.insert(1, 10); });
  std::jthread b([&] { map.insert(2, 20); });
}
map.get_copied(1);                                                      // std::optional{10}
map.read(2, [](const auto&, const auto& value) { return value + 1; });  // std::optional{21}
map.update(1, [](const auto&, auto& value) { value *= 2; });
map.scan([](const auto& key, const auto& value) { return true; });      // key order, true goes on

#include <bbtree_mmap/bbtree_map_file.hpp>

bbtree_mmap::bbtree_map_file<std::uint64_t, std::string>::create("names.bbtree", names);
auto file = bbtree_mmap::bbtree_map_file<std::uint64_t, std::string>::mmap("names.bbtree");
file.get(42);  // std::optional<std::string_view>

Keys get inline keys (design/04-inline-key.md) when they are std byte strings (std::string, std::string_view, std::vector<std::uint8_t>, std::array<std::uint8_t, 16/20/32>), 64- or 128-bit integers, or a type of yours with an inline_key<K> specialization, and the comparator is std::less<K> or std::less<>:

template <>
struct bbtree::inline_key<my_key> {
  // bytes offset..offset + 8 of an encoding that orders like my_key, big-endian
  static bbtree::inline_word at(const my_key& key, std::size_t offset) noexcept;
  // optional: width, hash_tag, cmp_from, cmp_prefix (inline_key.hpp)
};

Specialize bbtree::is_trivially_relocatable<T> for a key or value type that can move as its bytes, for the fastest shifts (PORTING.md, moves).

For string keys, bbtree::compact_string (bbtree/compact_string.hpp) is 16 bytes against libstdc++'s 32, holds up to 12 bytes in place, and moves as bytes; bbtree::compact_string_24 holds up to 20, for lookups of longer keys, and bbtree::basic_compact_string<Size, ShortCapacity> takes a 2-byte size for 2 more bytes in place, with strings capped at 65,535 bytes. It takes std::string, std::string_view and C strings wherever a key goes in, and with std::less<> looks them up without converting; keys come out as const compact_string&, a std::string_view by conversion (PORTING.md, compact_string):

bbtree::unsync::bbtree_map<bbtree::compact_string, int, std::less<>> map;
map[std::string("key")] = 1;
map.find(std::string_view("key"));
std::string_view first = map.begin()->first;

• Iterators dereference to bbtree::entry_ref<K, V>, a pair of references: for (auto& [k, v] : map) does not compile; it->second = v writes through (PORTING.md, iterators).
• Every insert and erase invalidates every iterator, and every reference and pointer to an entry, as for absl::btree_map: m[a] = m[b] reads a reference that the insert of a may have moved. Iterators stay valid across swap and moves of the map.
• for (const std::pair<const K, V>& entry : map) compiles and copies every entry; take const auto&.
• Not there: extract, merge and node handles, value_comp, transparent equal_range, constructors that take a comparator or an allocator with a range, deduction guides. std::erase_if and std::views::keys don't compile for the maps; erase_if(map, predicate), found by its argument, and a range-for with entry.first stand for them.
• An emplace or try_emplace that an allocator refuses a page has consumed its arguments, as std::map's has when it throws.
• Comparators must be stateless; allocators are page allocators (bbtree/allocator.hpp), not std allocators (PORTING.md, allocators, comparators).
• Comparators, inline-key specializations, and key and value moves and destructors must not throw (PORTING.md, exceptions).

cmake --preset debug && cmake --build --preset debug && ctest --preset debug
scripts/check.sh            # format, Clang and GCC builds, tests
scripts/check.sh --sanitize # plus AddressSanitizer + UBSan
cmake --preset tsan && cmake --build --preset tsan && ctest --preset tsan   # ThreadSanitizer
cmake --preset fuzz && cmake --build --preset fuzz                          # libFuzzer targets
scripts/check-install.sh    # install, and build a project against the install

To use bbtree++ from another CMake project, either add it with add_subdirectory (or FetchContent), or install it and find it:

cmake -S . -B build/release -DCMAKE_BUILD_TYPE=Release -DBBTREE_BUILD_TESTS=OFF
cmake --install build/release --prefix /opt/bbtree

find_package(bbtree 0.2 CONFIG REQUIRED)   # with /opt/bbtree in CMAKE_PREFIX_PATH
target_link_libraries(app PRIVATE bbtree::bbtree)   # or bbtree::mmap, bbtree::store

Testing. 328 Catch2 test cases, most built for the baseline and for the native target (619 tests in all), pass under Clang and GCC with warnings as errors; CI runs them again under AddressSanitizer and UBSan, and the shared map's under ThreadSanitizer. Eight libFuzzer targets check the maps and the shared map against std::map, the set algebra against std's algorithms, the tree's invariants after every operation, and memory safety under keys whose order lies. CI fuzzes each target for a minute, and the ordinary tests run the same harnesses on fixed inputs. The shared map's interleavings run under a seeded scheduler (PORTING.md, switch points). Of the Rust crate's own test suites, parts are still to port (FUTURE_WORK.md, tests).

How it was ported. bbtree++ was written by an AI coding agent, Claude Opus 5.5, with Claude Fable 5.1 as its advisor, under a human's direction. The agent ported the Rust crate milestone by milestone (PLAN.md), following the original's design documents and the rules in AGENTS.md. The human set the goals, contributed ideas, and reviewed and steered the work. Performance work followed the original's rules: reason about the cost first, then measure, on a port of the Rust bench that runs the same benchmarks cell for cell.

PORTING.md says where and why the port differs from the Rust original, FUTURE_WORK.md what is left and what would be faster at the cost of more code, and PLAN.md how the port went.

Copyright (c) 2026 Xiangpeng Hao (bbtree, its design and design/) and Markus Junginger (objectbox.io, the C++ port). Licensed under either of Apache License, Version 2.0 or MIT license, at your option, as the original is; LICENSE holds both texts.