Relaxed AVL trees, main-memory databases and concurrency. (English) Zbl 1001.68509

Summary: 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.


68P15 Database theory
68M10 Network design and communication in computer systems
Full Text: DOI


[1] Adel’son-Vel’skii G. M., Doklady Akademi Nauk 146 pp 263– (1962)
[2] DOI: 10.1145/359460.359470 · Zbl 0371.68009
[3] DOI: 10.1007/BF00288683 · Zbl 0226.68008
[4] DOI: 10.1007/BF00263762 · Zbl 0343.68022
[5] Boyar J., In Proceeding of Third Scandinavian Workshop on Algorithm Theory-SWAT 92 pp 151– (1992)
[6] DOI: 10.1016/S0022-0000(05)80075-3 · Zbl 0938.68612
[7] Boyar, J., Fegerberg, R. and Larsen, K. S. 1995. Amortization results for chromatic search trees, with an application to priority queues. Proceedings of the fourth International Workshop on Algorithms and Data Structures, WADS. 1995. Vol. 95, pp.270–281.
[8] DOI: 10.1145/359642.359655 · Zbl 0386.68024
[9] DOI: 10.1109/TC.1980.1675680 · Zbl 0441.68071
[10] Guibas, L. J. and Sedgewick, R. 1978. A dichromatic framework for balanced trees. Proceeding of the 19th Annual Symposium on Foundations of Computer Science. 1978. Vol. 29, pp.8–21.
[11] DOI: 10.1145/182.358442 · Zbl 0519.68025
[12] Knuth D. E., Sorting and Searching 3 (1973) · Zbl 0302.68010
[13] Kung H. T., ACM Transactions on Database Systems 3 pp 339– (1980)
[14] DOI: 10.1007/BFb0022520
[15] Larsen, K. S. 1994. AVL trees with relaxed balance. Proceedings of the Eighth International Parallel Processing Symposium. 1994. pp.888–893.
[16] Larsen, K S. and Fagerberg, R. 1995. B-trees with relaxed balance. Proceedings of the Ninth International Parallel Processing Symposium. 1995. pp.196–202.
[17] Lehman J., A Study of Index Structures for Main Memory Database Management Systems (1986)
[18] DOI: 10.1145/1270.318576
[19] Nurmi, O. and Soisalon-Soininen, E. 1991. Uncoupling updating and rebalancing in chromatic binary search trees. Proceedings of the 10th ACM Symposium on Principles of Database Systems. 1991. pp.192–198.
[20] Nurmi O., Chromatic binary search trees : A structure for concurrent rebalancing. Acta Informatica (1996) · Zbl 0849.68026
[21] Nurmi, O., Soisalon-Soininen, E. and Wood, D. 1987. Concurrency control in database structures with relaxed balance. Proceedings of the Sixth ACM Symposium on Principles of Database Systems. 1987. pp.170–176.
[22] Nurmi O., Relaxed AVLTrees, Main-Memory Databases, and Concurrency (1993)
[23] Ottmann Th. Soisalon-Soininen E. Relaxed balancing made simple. Unpublished manuscript 1996
[24] DOI: 10.1007/BF00290147 · Zbl 0562.68054
[25] DOI: 10.1016/0022-0000(86)90021-8 · Zbl 0625.68084
[26] Soisalon-Soininen E. Widmayer P. Relaxed balancing in binary search trees. Unpublished manuscript 1995 · Zbl 0874.68080
[27] Soisalon-Soininen E., AVLTrees, On-The-Fly Restructuring, and Concurrency (1986)
[28] DOI: 10.1145/6592.6599
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.