Logo image
Back
Cost-optimal parallel algorithms for constructing B-trees
Conference paper

Cost-optimal parallel algorithms for constructing B-trees

B.-F. Wang, G.-H. Chen and M.-S. Yu
International Conference on Parallel Processing, Vol.3, pp.294-135
1991
DOI: https://doi.org/10.1016/0020-0255(94)90089-2

Abstract

cost-optimal parallel algorithms;B-tree;sorted list of N keys;shared-memory SIMD computer;EREW model;Nloglog N processors;O(loglog N) time;CREW model;N processors;O(1) time.
In this paper two cost-optimal parallel algorithms are presented for constructing a B-tree for a sorted list of N keys. These two parallel algorithms are designed on the shared-memory SIMD computer: one, based on the EREW model, uses Nloglog N processors and requiresO(loglog N) time; the other, based on the CREW model, uses N processors and requires O(1) time.

Metrics

1 Record Views

Details

Logo image