A distributed B-tree for distributed databases

The design of algorithms for distributed databases should involve the design of a distributed data structure. However, it is assumed that arising from the distribution of any entity are problems on data consistency and efficiency. Efforts on the solution to these problems in the context of distributed data structures have been quite few. As a contribution to this area, a distributed B-tree is designed to index a distributed database. The distributed structure includes two logical processors, namely, the tree manager and the subtree managers, in addition to the features of the sequential B-tree. In order to allow more concurrency, the design and verification of the algorithms on the structure are based on the semantics of a dictionary abstract data type. A link technique, which operated in the context of the semantic approach, is used to provide data consistency without involving large updates on the structure. A maintenance process, which covers the split and merge operations, is conceived to reorganize the structure during idle periods. Since a B-tree is always balanced and large updates to not occur, the operations on the distributed structure are efficient. No node is replicated so that extra space requirement is only incurred by the logical processors