Return to search

Performance Study of Concurrent Search Trees and Hash Algorithms on Multiprocessors Systems

This study examines the performance of concurrent algorithms for B-trees and linear hashing. B-trees are widely used as an access method for large, single key, database files, stored in lexicographic order on secondary storage devices. Linear hashing is a fast and reliable hash algorithm, suitable for accessing records stored unordered in buckets. This dissertation presents performance results on implementations of concurrent Bunk-tree and linear hashing algorithms, using lock-based, partitioned and distributed methods on the Sequent Symmetry shared memory multiprocessor system and on a network of distributed processors created with PVM (Parallel Virtual Machine) software. Initial experiments, which started with empty data structures, show good results for the partitioned implementations and lock-based linear hashing, but poor ones for lock-based Blink-trees. A subsequent test, which started with loaded data structures, shows similar results, but with much improved performances for locked Blink- trees. The data also highlighted the high cost of split operations, which reached up to 70% of the total insert time.

Identiferoai:union.ndltd.org:unt.edu/info:ark/67531/metadc332828
Date05 1900
CreatorsDemuynck, Marie-Anne
PublisherUniversity of North Texas
Source SetsUniversity of North Texas
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
Formatxi, 260 leaves : ill., Text
RightsPublic, Demuynck, Marie-Anne, Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved.

Page generated in 0.0017 seconds