![Sample our Mathematics & Statistics journals, sign in here to start your FREE access for 14 days]({"type":"image" , "src" : "/sda/5943/TOC-Subject-Sample-2021-Mathematics-Statistics.jpg"})
Abstract
We consider the use of search trees to represent the dictionary aspects of a main-memory database in a concurrent environment. Efficiency considerations require that the trees be balanced and that operations on a search tree should not block too large a part of the tree for too long a time. These two requirements conflict, since rebalancing a tree after an update can, in a straightforward implementation, block too large a part of the tree. We would prefer that all search operations reserve only a small, fixed-size part of a tree at all times. We propose a new, elegant solution for this problem based on the notion of relaxed AVL trees and the decoupling of updates and rebalancing. The main advantage of our solution is that the implementation of the dicitionary operations in a concurrent environment is as simple as their implementation in a sequential environment, whereas previous concurrent solutions are more descriptively complex.
C.R. Category::
This research was supported partially by a Natural Sciences and Engineering Research Council of Canada Research Grant and partially by the Academy of Finland. The work of the third author was carried out at the University of Waterloo.
This research was supported partially by a Natural Sciences and Engineering Research Council of Canada Research Grant and partially by the Academy of Finland. The work of the third author was carried out at the University of Waterloo.
Notes
This research was supported partially by a Natural Sciences and Engineering Research Council of Canada Research Grant and partially by the Academy of Finland. The work of the third author was carried out at the University of Waterloo.