Abstract

Classical B-Trees were not designed for the modern hardware. They often do not scale on today’s many-core CPUs because they do not handle high-contention workloads well. Moreover, their fixed-size nodes result in underfull nodes and a space utilization below 70%. This low space utilization is economically undesirable, especially with fast but relatively expensive NVMe SSDs, and causes unnecessary read and write amplification. In this paper, we address these two shortcomings by introducing two techniques: The first, Contention Split detects unnecessary contention on nodes and splits them to allow higher concurrency. The second technique, XMerge, saves space by lazily merging neighboring nodes. Both techniques are lightweight, easy to integrate into existing database systems, and result in substantial space and performance improvements.