Cache-Friendly B+Tree Nodes with Dynamic Fanout

Summary

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_ |--------------------+ +----------------------+ | | Node Data | | +----------------------+ | | entries_[0] | <--+ | | entries_[1] | | | | entries_[2] | + used space | | ... | | | | entries_[k] | <--+ | +----------------------+<-------------------+ iter_end_ points to | | entries_[k+1], which is one-past-the-last | (unused space) | entry in the node. | ... | +----------------------+ Fig 1. Memory Layout of a B+Tree Node as a single contiguous block in heap Table of Contents Challenges The Struct Hack B+Tree Node Declaration Raw Memory Buffer The Price Of Fine-Grained Control Conclusion Challenges Using std::vector for a B+Tree node's entries is a non-starter. A std::vector object holds a pointer to its entries which are stored in a separate block of memory on the heap. This indirection fragments the memory layout, forcing us to fall back on C-style arrays for a contiguous layout when storing variable-length node entries. This leads to a dilemma. The size of the array must be known at compilation time, yet we need to allow users to configure the fanout (the array's size) at runtime. Furthermore, the implementation should allow inner nodes and leaf nodes t...