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

Abstract

The Native Grammar Format (NGF) database engine stores grammatical resources in a persistent, memory-mapped structure using copy-on-write transactions. Three aspects of its design were identified as potential bottlenecks: the use of Size-Balanced Trees 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 of NGF was implemented. The system supports alternative indexing structures, key-storage mechanisms, and allocation strategies, allowing their effects on performance to be studied independently. Twenty-two configurations were evaluated across six workloads at three scales (100K, 1M, and 5M operations), measuring execution time alongside L1 and L2 cache counters and instructions per cycle. B-trees outperformed Size-Balanced Trees across all configurations and workloads. The gap follows from tree height: B-tree nodes hold multiple keys, producing shorter traversal paths and fewer 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 due to fewer overflow accesses and lower allocator overhead. Page-aware allocation degraded performance at all tested node sizes, as alignment overhead outweighed any locality gain. Cache metrics showed the system to be instruction-bound for most configurations, explaining why a moderate tree degree was more effective than page alignment. The best configuration, a degree-5 B-tree with a 32-byte key prefix and no page alignment, outperforms the Size-Balanced Tree baseline by more than 25%.