Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/3-540-46093-4_15 | DBPL |
Keywords | Field | DocType |
previous solution,concurrent reading,well-known link technique,concurrent index structures,view serializable updates,stronger serializability criterion,new algorithm,view serializability criterion,binary search tree,satisfiability | Serializability,Concurrency control,Concurrency,Computer science,Binary tree,Global serializability,B-tree,Algorithm,Theoretical computer science,Sequential algorithm,Database,Binary search tree | Conference |
Volume | ISSN | ISBN |
2397 | 0302-9743 | 3-540-44080-1 |
Citations | PageRank | References |
2 | 0.40 | 17 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stavros S. Cosmadakis | 1 | 507 | 350.62 |
Kleoni Ioannidou | 2 | 107 | 6.70 |
Stergios Stergiou | 3 | 339 | 15.84 |