A Parallel Algorithm for Reconstruction of B-tree Structure after Substantial Key Removals

B-tree is sophisticated and well known data structure which has extensive application in data storage and retrieval systems including parallel database systems. In this paper, we present an algorithm for deleting keys of B-tree concurrently in the case that the number of to-be-deleted keys is more than a half of the total keys in the tree. The proposed algorithm can be implemented on CREW PRAM model in optimal O (log2 n+B logB n) time with the total processors equal to the number of keys to be removed. n is the total number of keys in B-tree and B is equal to half of the keys in an internal node containing maximum keys. It counts as an improvement upon the previous comparable known algorithms by a reduction of factor B in the (log2 n)-term of the time complexity

کلیدواژه ها:

B-tree ، Parallel Algorithm ، Balanced Search Tree ، Dictionary Operations ، Array Packing ، PRAM