MAINTAINING B-TREES ON AN EREW PRAM

Abstract

Efficient and practical algorithms for maintaining general B-trees on an EREW PRAM are presented. Given a B-tree of order b with m distinct records, the search (respectively, insert and delete) problem for n input keys is solved on an n-processor EREW PRAM in 0(logn+blogsubbm) (respectively, 0(b(logn+logsubbm)) and 0(bsup2(logsubbn+logsubbm))) time.