scientific article; zbMATH DE number 3909752
A balanced search tree (such as an AVL-tree, a 2-3 tree, a B-tree or a weight-balanced tree) is an efficient data structure for storing a large amount of information, since it allows a search, an insertion or a deletion to be executed in time proportional to the logarithm of the number of keys [\textit{A. V. Aho, J. E. Hopcroft} and \textit{J. D. Ullman}: The design and analysis of computer algorithms (1974; Zbl 0326.68005)]. The usual update algorithms on these trees are 2-pass top-down bottom-up: a search is conducted from the root to find the appropriate leaf to insert or delete, followed by a re-balancing step which could propagate all the way back to the root. This approach poses problems if many users (or many processors) have to access the same data concurrently: each user must keep the others from changing that data in a way which would kill the search, but locking the whole tree during the course of the serach would be too wasteful of time and storage. The thesis under review examines various more efficient locking protocols [for example: \textit{R. Bayer} and \textit{M. Schkolnick}, Acta Inf. 9, 1-21 (1977; Zbl 0343.68022), \textit{L. J. Guibas} and \textit{R. Sedgewick}, 19th Ann. Symp. Found. Comput. Sci., 8-21 (1978), \textit{J. Nievergelt} and \textit{E. M. Reingold}, SIAM J. Comput. 2, 33-43 (1973; Zbl 0262.68012), \textit{A. S. Zaki}: A top-down deletion algorithm for minimum-order B-trees, Univ. Washington, Techn. Report (1978)], finds that they are complicated and that none of them are 1-pass top-down under all circumstances (the last three cited here are sometimes 2-pass top-down), and provides some relatively simple 1-pass top-down update schemes. The first algorithm given here is for a data structure similar to a B- tree [\textit{R. Bayer} and \textit{M. Schkolnick}, loc. cit.], called an \(\alpha\)-\(\beta\) tree: for any pair of integers (\(\alpha\),\(\beta)\) such that \(\beta\geq 5\) and \(\alpha =\lceil \beta /2\rceil -1\), (1) every internal node (except for the root) has at least \(\alpha\) and at most \(\beta\) sons; (2) the root has at least 2 (and at most \(\beta\) ?) sons; (3) all the leaves have the same distance from the root. The algorithm locks only 3 nodes at any one time, and is general enough to handle insertions and deletions and several routing schemes (assignments of values to the internal nodes to direct the search). The code can be simplified if only insertions or only deletions are considered or if a so-called good routing scheme [\textit{Y. S. Kwong} and \textit{S. Wood}: On B-trees: Routing schemes and concurrency, Proc. 1980 ACM/SIGMOD Int. Conf. Management of Data, 207-231 (1980)] is used. This algorithm is then generalized to a wider class of trees called stratified trees, defined by \textit{J. van Leeuwen} and \textit{M. H. Overmars} [Acta Inf. 18, 345-359 (1983; Zbl 0493.68063)] and modified here to accommodate both insertions and deletions. Two versions of the generalized algorithm are given, one for a good routing scheme and another for a bad one. No bound is given on the number of nodes which must be locked at any one time, but the number of levels of nodes which must be locked is bounded as a function of the routing scheme. It is claimed here that many known classes of balanced trees are either stratified or contain stratified subclasses (for example, AVL-trees, B- trees, 1-2 brother trees and \(\alpha\)-\(\beta\) trees); unfortunately it is not clear from the text whether \textit{J. van Leeuwen} and \textit{M. H. Overmars} [loc. cit.] state which is which and/or give proofs of all these claims. It is shown that weight-balanced trees do not contain a stratified subclass; the question of whether a 1-pass top-down update algorithm can be found for these trees is left open. It is also admitted that the algorithm given is far from being optimal for any single class; the reader is thus advised to look for a fast, efficient 1-pass top-down update algorithm for a specific application involving a particular class of trees and a particular routing scheme. The author tabulates the best- , average- and worst-case numbers of inner nodes and numbers of splits of the root for \(\alpha\)-\(\beta\) trees (the simplest case - 2-5 trees - is derived in an appendix) and thence deduces that an \(\alpha\)-\(\beta\) tree uses about the same amount of storage per key as a B-tree with the same maximum branching number. Hence, by using \(\alpha\)-\(\beta\) trees one can combine the space-efficiency of B-trees with the advantages of a 1-pass algorithm. In the reviewer's opinion, the advantages of a 1-pass algorithm over a 2- pass top-down one are not convincingly enough demonstrated; as well as stating that we are really interested in purely top-down algorithms, that is 1-pass top-down algorithms the author might have included a comparison of the computational performances of the best 1-pass and 2- pass top-down algorithms. The results obtained for height-balanced trees are applied to a multiprocessor environment: a tree of O(N) processors is constructed for a database with N partitions, obtaining a better concurrency-throughput trade-off than in previous work [\textit{M. J. Carey} and \textit{C. D. Thompson}: An efficient implementation of search trees on O(log N) processors, Techn. Report, Comput. Sci. Div. Univ. California, Berkeley, CA 94720 (1982)]. Finally, another appendix (in German) describes the development of the installation of the TEX typesetting system at the University of Karlsruhe. Overall, the thesis is very well motivated and easy to read and, the reviewer's nitpicking notwithstanding, represents an important contribution to the field of theoretical computer science.
- Purely top-down updating algorithms for stratified search trees
- Operation-specific locking in balanced structures
- Maintaining α-balanced trees by partial rebuilding
- scientific article; zbMATH DE number 3845065 (Why is no real title available?)
- scientific article; zbMATH DE number 3856424 (Why is no real title available?)
- A TOP-DOWN UPDATING ALGORITHM FOR WEIGHT-BALANCED TREES
- String Processing and Information Retrieval
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3686049)