Abstract
We present an optimal parallel algorithm for the construction of (a,b)-trees --- a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a,b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a,b)-trees with N keys in O(N/p + loglog N) time using p <= N/loglog N processors on the EREW-PRAM model, and in O(N/p) time using p <= N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50 percent better than that for the worst-case and is also better than that for a random (a,b)-trees. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.
Appeared in: Journal of Parallel and Distributed Computing, volume 23, pp. 442-448 (1994)
View the PostScript document.