Deleting keys of B-trees in parallel
The B-tree is a fundamental data structure that is used to access and update a large number of keys. In this paper, we present a parallel algorithm on the EREW PRAM that deletes keys in a B-tree. Our algorithm runs in O(B(log k + log(B)n)) time with k processors, where n is the number of keys in the B-tree, B is the minimum degree of the B-tree, and k is the number of unsorted keys to delete, and it improves upon the previous algorithm by a factor of B. (C) 2004 Elsevier Inc. All rights reserved.
b-trees parallel algorithms balanced search trees dictionary operations