Highly Scalable Data Balanced Distributed B trees
Padmashree Krishna, Theodore J. Johnson · 2009
Scalable distributed search structures are needed to maintain large volumes of data and for parallel databases. In this paper, we analyze the performance of two large scale data-balanced distributed search structures, the dB-tree and the dE-tree. The dB-tree is a distributed B-tree that replicates its interior nodes. The dE-tree is a dB-tree in which leaf nodes represent key ranges, and thus requires far fewer nodes to represent a distributed index. The performance of both algorithms depends on the method by which tree nodes are assigned to processors (i.e., the algorithm for performing data balancing). We present a simulation study of data balancing algorithms for the dB-tree and the dE-tree. We find that a simple distributed data balancing algorithm works well for the dB-tree, requiring only a small space and message passing overhead. We compare three algorithms for data balancing in a dE-tree, and find that the most aggressive of the algorithms makes the dE-tree scalable. Using the ...