Τίτλος:
View serializable updates of concurrent index structures
Γλώσσες Τεκμηρίου:
Αγγλικά
Περίληψη:
We present new algorithms for concurrent reading and updating of B*-trees and binary search trees. Our algorithms are based on the well-known link technique, and improve previously proposed solutions in several respects. We prove formally that our algorithms are correct. We show that they satisfy a view serializability criterion, which fails for previous solutions. This stronger serializability criterion is central to the proof that several subtle (but essential) optimizations incorporated in our algorithms are correct. © Springer-Verlag Berlin Heidelberg 2002.
Συγγραφείς:
Cosmadakis, S.
Ioannidou, K.
Stergiou, S.
Περιοδικό:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Λέξεις-κλειδιά:
Forestry, Binary search trees; Index structure; Serializability, Binary trees
DOI:
10.1007/3-540-46093-4_15
