Boosting the Search Performance of B+-tree with Sentinels for Non-volatile Memory
Chongnan Ye, Chundong Wang · 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC) · 2022
B+-tree has been an important index structure since the era of hard disks. The next-generation non-volatile memory (NVM) is striding into computer systems as a new tier as it incorporates both DRAM's byte-addressability and disk's persistency. Researchers and practitioners have considered building persistent memory by placing NVM on the memory bus for CPU to directly load and store data. As a result, cache-friendly data structures, such as the B+-tree, have been developed for NVM. State-of-the-art in-NVM B+-trees mainly focus on the optimization of write operations (insertion and deletion). How-ever, search is of paramount importance for B+-tree. Not only search-intensive workloads benefit from an optimized search, but insertion and deletion also rely on a preceding search operation to proceed. In this paper, we attentively study a sorted B+-tree node that spans over contiguous cache lines. Such cache lines exhibit a monotonically increasing trend and searching a target key across them can be accelerated by estimating a range the key falls into. To do so, we construct a probing Sentinel Array in which a sentinel stands for each cache line of B+-tree node. Checking the Sentinel Array avoids scanning unnecessary cache lines and hence significantly reduces cache misses for a search. A quantitative evaluation shows that using Sentinel Arrays boosts the search performance of state-of-the-art in-NVM B+-trees by up to 48.4 % while the cost of maintaining of Sentinel Array is low.