上海科技大学知识管理系统

Search trees are one of the most important and widely used data structures, and parallelization is an effective method to improve their performance. However, many existing parallel search trees incur high synchronization costs and low memory I/O efficiency, which limits their performance. We propose PPBT, a batched parallel search tree which minimizes synchronization by partitioning the tree using novel algorithms and minimizing I/O cost using buffering. We give a new sequential algorithm for batch processing on search trees with optimal I/O efficiency for insert and delete operations, and also present a fast parallel algorithm for joining disjoint search trees. We show experimentally that PPBT is over 6×faster than the state-of-the-art parallel tree in [1] and over 40× faster than the concurrent search tree in [7], and achieves 21×speedup using 32 threads. PPBT's throughput on searches is lower due to reduced opportunities for buffering, but is still 1.3 × that of [1]. In addition, PPBT has good response times for searches, for example completing 100K searches in under 1 ms in a tree with 10M elements. © 2021 IEEE.