Performance study of concurrent search trees and hash algorithms on multiprocessor systems
Marie-Anne Demuynck · 1996
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 Bi$\sp{link}$-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 B$\sp{link}$-trees. A subsequent test, which started with loaded data structures, shows similar results, but with much improved performances for locked B$\sp{link}$-trees. The data also highlighted the high cost of split operations, which reached up to 70% of the total insert time. To improve the performance of the B-tree data structure in a parallel computing environment, we have developed the B$\sp{mad}$-tree, a B$\sp{link}$-tree variant. It allows insertion without node splits, with multiple access in its leaf nodes, and dilation in both the index and the leaf nodes. Concurrent search, insert and restructuring algorithms for partitioned, locked and distributed models are given. Two locked approaches are used; both minimize the necessary number of locks. Only part of an insertion node is locked during insert, and simultaneous insertions by multiple processors in the same node are allowed. A restructuring algorithm runs periodically in the background and requires only waits. At most one such wait is encountered by any search or update operation. The B$\sp{mad}$-tree implementations showed very good results for locked and partitioned algorithms. Especially the locked algorithms exceeded expectations. The distributed results were disappointing. High communication costs prevented a good performance. Experimental data were used to project performance beyond the current test systems. This research also prompted some further investigations, such as analyzing the high cost of process creation and the development of a load balancing method.