Locality-Aware Indexing in Copy-on-Write Memory-Mapped Database Systems - An Evaluation of B-Trees, Inline Key Storage, and Page-Aware Memory Allocation

Sammanfattning

The Native Grammar Format (NGF) database engine stores grammatical resourcesin a persistent, memory-mapped structure using copy-on-write transactions. Threeaspects of its design were identified as potential bottlenecks: the use of Size-BalancedTrees as the indexing structure, keys being stored separately from the tree nodes,and allocation without regard to page boundaries. To evaluate these potential bottlenecks, a custom database engine reproducing the core architectural principles ofNGF was implemented. The system supports alternative indexing structures, key-storage mechanisms, and allocation strategies, allowing their effects on performanceto be studied independently. Twenty-two configurations were evaluated across sixworkloads at three scales (100K, 1M, and 5M operations), measuring execution timealongside L1 and L2 cache counters and instructions per cycle. B-trees outperformedSize-Balanced Trees across all configurations and workloads. The gap follows fromtree height: B-tree nodes hold multiple keys, producing shorter traversal paths andfewer nodes visited per operation. Storing keys with a 32-byte inline prefix improved performance for both structures, with a larger effect for B-trees at scale dueto fewer overflow accesses and lower allocator overhead. Page-aware allocation degraded performance at all tested node sizes, as alignment overhead outweighed anylocality gain. Cache metrics showed the system to be instruction-bound for mostconfigurations, explaining why a moderate tree degree was more effective than pagealignment. The best configuration, a degree-5 B-tree with a 32-byte key prefix andno page alignment, outperforms the Size-Balanced Tree baseline by more than 25%.