Title :
Deleting keys of B-trees in parallel
Author :
Heejin Park ; Kunsoo Park ; Yookun Cho
Author_Institution :
Sch. of Comput. Sci. & Eng., Seoul Nat. Univ., South Korea
Abstract :
The B-tree is a fundamental data structure that is used to access and update a large number of keys. In this paper we present a parallel algorithm on the EREW PRAM that deletes keys in a B-tree. Our algorithm runs in O(t(log k+log, n)) time with k processors, where n is the number of keys in the B-tree, t is the minimum degree of the B-tree, and k is the number of unsorted keys to delete, and it improves upon the previous algorithm by a factor of t.
Keywords :
computational complexity; parallel algorithms; pipeline processing; search problems; tree data structures; B-trees; EREW PRAM; balanced search trees; computational complexity; data structure; dictionary operations; parallel algorithms; pipeline processing; Computer science; Data engineering; Data structures; Dictionaries; Distributed processing; Parallel algorithms; Phase change random access memory; Pipeline processing;
Conference_Titel :
Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM
Conference_Location :
Ft. Lauderdale, FL
Print_ISBN :
0-7695-1573-8
DOI :
10.1109/IPDPS.2002.1015581
