Physical Sciences and Mathematics Commons^™

Coarse-Grained, Fine-Grained, And Lock-Free Concurrency Approaches For Self-Balancing B-Tree, Edward R. Jorgensen Ii

UNLV Theses, Dissertations, Professional Papers, and Capstones

This dissertation examines the concurrency approaches for a standard, unmodified B-Tree which is one of the more complex data structures. This includes the coarse grained, fine-grained locking, and the lock-free approaches. The basic industry standard coarse-grained approach is used as a base-line for comparison to the more advanced fine-grained and lock-free approaches. The fine-grained approach is explored and algorithms are presented for the fine-grained B-Tree insertion and deletion. The lock-free approach is addressed and an algorithm for a lock-free B- Tree insertion is provided. The issues associated with a lock-free deletion are discussed. Comparison trade-offs are presented and discussed. As …