P2P overlays offer a convenient way to host an infrastructure that can scale to the size of the Internet and yet manageable. Current proposals, however, do not offer support for structuring data, other than assuming a distributed hash table.

In reality, both applications and users typically organize data in a structured form. One such popular structure is tree as employed in a file system, and a database. A na?ve approach such as hashing the pathname not only ignores locality in important operations such as file/directory lookup, but also results in uncontrollable, massive object relocations when rename on a path component occur.

In this paper, we investigate policies and strategies that place a tree onto the flat storage space of P2P systems. We found that, in general, there exists a tradeoff between lookup performance and balanced storage utilization, and attempts to balance these two requirements calls for intelligent placement decision.