Title

Parallel Construction of (a, b)-Trees

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)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log 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% better than that for the worst-case and is also better than that for a random (a, b)-tree. 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. © 1994 Academic Press, Inc.

Publication Date

1-1-1994

Publication Title

Journal of Parallel and Distributed Computing

Volume

23

Issue

3

Number of Pages

442-448

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1006/jpdc.1994.1154

Socpus ID

0040659643 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0040659643

This document is currently not available here.

Share

COinS