University of North Texas
Performance Study of Concurrent Search Trees and Hash Algorithms on Multiprocessors Systems
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 1996
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Demuynck, Marie-Anne
- Contributors dc:contributor
-
- Das, Sajal K.
- Fisher, Paul S.
- Brand, Neal E.
- Shi, Weipeng
Subjects
dc:subject × 7Rights
dc:rights- Statement dc:rights
-
- Public
- Demuynck, Marie-Anne
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights reserved.
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
local-cont-no: 1002727485-Demuynck
call-no: 379 N81d no.4268
untcat: b1984871
oclc: 35868283
ark: ark:/67531/metadc332828