Cache-Friendly B+Tree Nodes With Dynamic Fanout 18-Aug-2025
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 increases the implementation complexity and is mired with hidden drawbacks. Nevertheless, this is still a necessary trade-off for unlocking high performance.
+----------------------+
| Node Metadata Header |
+----------------------+
| node_type_ |<-- Inner Node or Leaf Node
| max_size_ |<-- Maximum Capacity (aka Node Fanout)
| node_latch_ |<-- RW-Lock Mutex
| iter_end_ |--------------------+
... continue reading