A Concurrent Blink-Tree Algorithm Using a Cooperative Locking Protocol
- 176 Downloads
We present a new concurrent Blink-tree algorithm that provides a concurrent tree restructuring mechanism for handling underflow nodes as well as overflow nodes. Our algorithm does not require any lock for downward searching and preserves bottom-up tree restructuring without deadlock. To this end, we develop a new locking mechanism for inserters and deleters and a node update rule that preserves the semantical tree consistency during tree restructuring. Our analytical experiment shows that the overhead of additional disk I/O is acceptable.
KeywordsIndex Entry Parent Node Concurrency Control Search Operation Sibling Node
Unable to display preview. Download preview PDF.
- 9.Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. International Conference on Data Engineering (1992) 184–191Google Scholar
- 11.Jan Jannink: Implementing Deletion in B+-Trees. ACM SIGMOD 24 (1995) 33-38Google Scholar
- 12.Gray, J. and Reuter, A.: Transaction Processing: Concepts and Techniques. Reading Mass (1993) 449–490. Morgan Kaufmann Pub.Google Scholar