DeltaTree: A Locality-aware Concurrent Search Tree
Like other fundamental abstractions for high-performance computing, search trees need to support both high concurrency and data locality. However, existing locality-aware search trees based on the van Emde Boas layout (vEB-based trees), poorly support concurrent (update) operations. We present DeltaTree, a practical locality-aware concurrent search tree that integrates both locality-optimization techniques from vEB-based trees, and concurrency-optimization techniques from highly-concurrent search trees. As a result, DeltaTree minimizes data transfer from memory to CPU and supports high concurrency. Our experimental evaluation shows that DeltaTree is up to 50% faster than highly concurrent B-trees on a commodity Intel high performance computing (HPC) platform and up to 65% faster on a commodity ARM embedded platform.
© ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Performance Evaluation Review 2015, 43(1):457-458. Published version available at http://dx.doi.org/10.1145/2796314.2745891