BIB-VERSION:: CS-TR-v2.0
ID:: UCB//S2K-94-46
ENTRY:: April 29, 1994
TITLE:: RP: A Family of Order Preserving Scalable
        Distributed Data Structures
DATE::
AUTHOR:: Litwin, W.
AUTHOR:: Neimat, M-A.
AUTHOR:: Schneider, D.
PAGES:: 19
ABSTRACT:: Hash-based scalable distributed data structures (SDDSs),
like LH* or DDH, for networks of interconnected computers (multi-
computers) 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 range partitioning as a B-tree, but avoids indexes
through the use of multicast. The algorithms, RP*c and RP*s enhance
the throughput for faster networks, adding the indexes on clients,
or on clients and servers, decreasing or avoiding the 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*.
RETRIEVAL:: postscript (in all.ps)
END:: UCB//S2K-94-46