  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 have been developed for
NVM. One of them is the prevalent B+-tree. State-of-the-art in-NVM B+-trees
mainly focus on the optimization of write operations (insertion and deletion).
However, search is of vital 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.
