Relaxed avl trees, main-memory databases and concurrencyFootnote

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.

References

• Adel'son-Vel'skii , G. M. and Landis , Y. M. 1962 . An algorithm for the organization of information . Doklady Akademi Nauk , 146 : 263 – 266 .
   Web of Science ®Google Scholar
• Banker , G. B. 1978 . List processing in real time on a serial computer . Communications of the ACM , 21 : 280 – 294 .
   Web of Science ®Google Scholar
• Bayer , R. and Mccreight , E. 1972 . Organization and maintenance of large ordered indexes . Acta Inforamtica , 1 : 173 – 189 .
   Google Scholar
• Bayer , R. and Schkolnick , M. 1977 . Concurrent operations on B-trees . Acta Informatica , 9 : 1 – 21 .
   Web of Science ®Google Scholar
• Boyar , J. and Larsen , K. S. 1992 . Efficient rebalancing of chromatic search trees . In Proceeding of Third Scandinavian Workshop on Algorithm Theory-SWAT , 92 : 151 – 164 .
   Google Scholar
• Boyar , J. and Larsen , K. S. 1992 . Efficient rebalancing of chromatic search trees . Journal of Computer and System Sciences , 49 : 667 – 682 .
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Dijkstra , E. W. , Lamport , L. , Martin , A. J. , Scholten , C. S. and Steffens , E. F. M. 1978 . On-the-fly garbage collection: An exercise in cooperation . Communications of the ACM , 21 : 966 – 975 .
   Web of Science ®Google Scholar
• Ellis , C. S. 1980 . Concurrent search and insertion in AVL trees . IEEE Transactions on Computers , 29 : 811 – 817 .
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Kessels , J. L. W. 1983 . On-the-fly optimization of data structures . Communications of the ACM , 26 : 895 – 901 .
   Web of Science ®Google Scholar
• Knuth , D. E. 1973 . “ The Art of Computer Programming ” . In Sorting and Searching , Vol. 3 , Reading, Mass : Addison-Wesley Publishing Co .
   Google Scholar
• Kung , H. T. and Lehman , P. L. 1980 . A concurrent database manipulation problem: Binary search trees . ACM Transactions on Database Systems , 3 : 339 – 353 .
   Google Scholar
• Kwong , Y. S. and Wood , P. L. 1980 . Approaches to concurrency in B-trees . In Mathematical Foundations of Computer Science, Lecture Notes in Computer Science , 88 : 402 – 413 .
   Google Scholar
• Larsen , K. S. 1994 . AVL trees with relaxed balance . Proceedings of the Eighth International Parallel Processing Symposium . 1994 . pp. 888 – 893 .
   Google Scholar
• Larsen , K S. and Fagerberg , R. 1995 . B-trees with relaxed balance . Proceedings of the Ninth International Parallel Processing Symposium . 1995 . pp. 196 – 202 .
   Google Scholar
• Lehman J. Carey M. J. A Study of Index Structures for Main Memory Database Management Systems University of Wisconsin, Department of Computer Science Technical Report 1986
   Google Scholar
• Manber , U. and Ladner , R. E. 1984 . Concurrency control in a dynamic search structure . ACM Transactions on Database Systems , 9 : 439 – 455 .
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Nurmi O. Soisalon-Soininen E. Chromatic binary search trees : A structure for concurrent rebalancing. Acta Informatica 1996 to appear
   Google Scholar
• 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 .
   Google Scholar
• Nurmi O. Soisalon-Soininen E. Wood D. Relaxed AVLTrees, Main-Memory Databases, and Concurrency University of Western Ontario, Department of Computer Science Technical Report, 351 1993
   Google Scholar
• Ottmann Th. Soisalon-Soininen E. Relaxed balancing made simple. Unpublished manuscript 1996
   Google Scholar
• Ottmann , Th. , Schrapp , M. and Wood , D. 1985 . Purely top-down updating algorithms for stratified search trees . Acta Informatica , 22 : 85 – 100 .
   Web of Science ®Google Scholar
• Sagiv , Y. 1986 . Concurrent operations on B-trees with overtaking . Journal of Computer and System Sciences , 3 : 275 – 296 .
   Web of Science ®Google Scholar
• Soisalon-Soininen E. Widmayer P. Relaxed balancing in binary search trees. Unpublished manuscript 1995
   Google Scholar
• Soisalon-Soininen E. Wood D. AVLTrees, On-The-Fly Restructuring, and Concurrency University of Waterloo, Department of Computer Science Research Report CS-86-52 October 1986
   Google Scholar
• Stout , Q. F. and Warren , B. L. 1986 . Tree rebalancing in optimal time and space . Communications of the ACM , 29 : 902 – 908 .
   Web of Science ®Google Scholar