Jacob Sherin writes about database internals.
This post contains challenges I faced in implementing a thread-safe, concurrent B+Tree implementation. You can find the code here and tests here . A lot of engineering effort in code reviews, tests, analyzers ( ThreadSanitizer ) was required to finally arrive at an implementation without deadlocks and data races. You will see that the same thinking and techniques apply to other concurrent data…
For a high-performance B+Tree, the memory layout of each node must be a single contiguous block. This improves locality of reference, increasing the likelihood that the node's contents reside in the CPU cache. In C++, achieving this means forgoing the use of std::vector , as it introduces a layer of indirection through a separate memory allocation. The solution to this problem though inevitably…
A B+Tree's stable algorithmic performance relies on a single invariant: the path from its root to any leaf is always the same length. However, a delete operation can cause a node to underflow (falling below its minimum occupancy), triggering a rebalancing procedure to maintain this critical invariant. Modern B+Trees use fast, optimistic latching protocols which operate under the assumption that…