Multi-level transaction model for semantic concurrency control in linear hash structures

In this paper, we present a version of the linear hash structure algorithm to increase concurrency using multi-level transaction model. We exploit the semantics of the linear hash operations at each level of transaction nesti ng to allow more concurrency. We implement each linear hash operation by a sequence of operations at lower level of abstraction. Each linear hash oper ation at leaf-level is a combination of search and read/write operations. W e consider locks at both vertex (page) and key level (tuple) to further inc rease concurrency. As undo-based recovery is not possible with multi-level transactions, we use compensation-based undo to achieve atomicity. We have implemented our model using object-oriented technology and multithreading p aradigm. In our implementation, linear hash operations such as find, insert , delete, split, and merge are implemented as methods and correspond to mul ti-level transactions. (C) 2000 Elsevier Science B.V. All rights reserved.