We address the problem of how a data-oriented, structured overlay networks can be constructed efficiently from scratch in a self-organized way, a problem that has so far not been addressed in the literature. This problem occurs when using overlay networks to implement index structures for data-oriented applications such as peer-to-peer databases or peer-to-peer information retrieval. There changing application requirements frequently lead to re-indexing of the data and hence (re-)construction of overlay networks. Standard maintenance algorithms for overlay networks cannot efficiently deal with this task as they are inherently sequential. We propose a randomized algorithm which is completely decentralized and parallel that can construct a new overlay network with short latency. At the same time our approach ensures good load-balancing for skewed data key distributions which result from preserving key order relationships as necessitated by data-oriented applications. We provide both a theoretical analysis of the basic algorithms and a complete system implementation that has been tested on PlanetLab. We are using this system to support peer-to-peer information retrieval and database applications.