Title

Parallel Construction Of (A, B)-Trees

Authors

Authors

N. Deo; A. Jain;M. Medidi

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

J. Parallel Distrib. Comput.

Keywords

B-TREES; ALGORITHMS; OPERATIONS; 2, 3-TREES; Computer Science, Theory & Methods

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 less than or equal to N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p less than or equal to 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. (C) 1994 Academic Press, Inc.

Journal Title

Journal of Parallel and Distributed Computing

Volume

23

Issue/Number

3

Publication Date

1-1-1994

Document Type

Note

Language

English

First Page

442

Last Page

448

WOS Identifier

WOS:A1994PU61700016

ISSN

0743-7315

Share

COinS