Back to search

University of North Texas

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

Abstract

dc:description

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.

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 × 7

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Demuynck, Marie-Anne. Performance Study of Concurrent Search Trees and Hash Algorithms on Multiprocessors Systems. University of North Texas, 1996. https://digital.library.unt.edu/ark:/67531/metadc332828/