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

Nurmi, Otto; Soisalon-Soininen, Eljas; Wood, Derick

Int. J. Comput. Math. 62, No. 1-2, 23-44 (1996).

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.

MSC:

68P15	Database theory
68M10	Network design and communication in computer systems

Keywords:

search trees; relaxed AVL tree; dictionary operations; concurrency

References:

[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