| B-trees and their variants are efficient data structures for finding records in a large collection (e.g. databases). The efficiency of algorithm based on B-trees increases when a number of users can manipulate the tree simultaneously. Many algorithms have been developed over the last three decades to achieve both concurrency and consistency in B-trees. However, current lock-based concurrency control techniques limit concurrency. Moreover, lock-based B-trees suffer from certain negative scheduling anomalies, such as deadlock, convoying and priority inversion. Lock-free concurrency control techniques using, for example, Compare and Swap (CAS) can provide improved concurrent access to data structures including B-trees and other search structures. Besides this, correctly designed lock-free techniques prevent deadlock, convoying and priority inversion. Considering the advantages of lock-free techniques for other concurrent data structures, I propose to develop a lock-free B-tree like structure to support high performance concurrent in-memory searching in a Non Uniform Memory Access (NUMA) parallel computing environment.; The use and parallelization of B-trees have both been widely explored in the past---primarily for application to database implementation and hence, disk-based operations. Moving B-trees into memory for use in new online searching applications, however, fundamentally changes the characteristics of managing them and will allow me to effectively exploit the use of lock-free techniques, something that has previously not been applicable to B-trees. |
