A deep-dive into practical techniques for implementing a production-grade, thread-safe, concurrent B+Tree data structure without deadlocks and data races. The B+Tree implementation supports search, insertions, deletions and bidirectional range scans.

A B+Tree node requires a contiguous, cache-friendly memory layout and a dynamic number of entries, but standard C++ tools falls short on both ends. This post explores how to solve this classic problem using the "struct hack" and manual memory management, while also exposing the higher complexity and drawbacks involved when chasing raw performance.

The stable logarithmic performance of a B+Tree is an outcome of its self-balancing property. When an inner node or leaf node falls below its minimum occupancy threshold during deletions, the tree rebalancing procedure is activated. The first choice is to either merge with a sibling, or borrow (redistribute) keys from a sibling. Neither choice is inherently better. Instead, the design decision signals the fundamental trade-off preferred by the specific implementation. A survey of major OLTP systems reveals a design space that is far more nuanced than this simple binary choice suggests.