Distributed search structures are useful for parallel databases and in maintaining distributed
storage systems. Although a considerable amount of research has been done on developing parallel
search structures on shared-memory multiprocessors, little has been done on the development of
search structures for distributed-memory systems. In this paper we discuss some issues in the design
and implementation of distributed B-trees, such as methods for low-overhead synchronization of tree
restructuring and node mobility. One goal of this work is to implement a data-balanced dictionary
which allows for balanced processor and space utilization. We present an algorithm for dynamic
data-load balancing which uses node mobility mechanisms. We also study the effects that balancing
and not balancing data have on the structure of a distributed B-tree. Finally, we demonstrate that
our load-balancing algorithm distributes the nodes of a B-tree very well.