RP*: A Family of Order Preserving Scalable Distributed Data Structures

Hash-based scalable distributed data structures (SDDSs), like LH* and DDH, for networks of interconnected computers (multicomputers) were shown to open new perspectives for file management. We propose a family of ordered SDDSs, called RP*, providing for ordered and dynamic files on multicomputers, and thus for more efficient processing of range queries and of ordered traversals of files. The basic algorithm termed RP*N, builds the file with the same key space partitioning as a B-tree, but avoids indexes through the use of multicast. The algorithms, RP*C and RP*S enhance throughput for faster networks, adding the indexes on clients, or on clients and servers, while either decreasing or avoiding multicast. RP* files are shown highly efficient with access performance exceeding traditional files by an order of magnitude or two, and, for non-range queries, very close to LH*.