Most balanced search trees use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were investigated in the past, their non-blocking concurrent variants have received very little attention so far.

In this paper, we propose the first non-blocking implementation of the classic interpolation search tree data structure. For arbitrary key distributions, the data structure ensures amortized O(log n) insertion and deletion. Furthermore, when input key distributions are smooth, lookups run in expected O(log log n) time, and insertion and deletion run in amortized O(log log n). To improve the scalability of insertion and deletion operations, we propose a novel, scalable concurrent rebuilding technique. We implement the concurrent interpolation search tree, and evaluate the efficiency of its operations.