Aberer, Karl2005-07-132005-07-132005-07-132002https://infoscience.epfl.ch/handle/20.500.14299/214568Scalable mechanisms to support efficient key-based search in distributed systems are an important part of the infrastructure of peer-to-peer systems and global information systems. They received substantial attention both in information and communication systems research. A particularly important class of approaches is based on a principle of scalable distribution of binary search trees that has been introduced by Plaxton \cite{PLAXTON}. When adapting the shape of such a tree search structure to the data distribution in order to obtain load balancing, the search trees may become highly unbalanced. We show that for P-Grid, a Plaxton-like distributed search structure that we first introduced in \cite{PGRID1}, the expected communication cost for searches is strictly limited by $\log(n)$ where $n$ is the number of peers. This result is completely independent of the shape of the underlying tree. The approach exploits the randomization principle of the P-Grid structure by virtue of its decentralized and randomized construction process.Scalable Distributed Data StructuresP-GridNCCR-MICS/CL4NCCR-MICStext::report