In recent years, a new generation of structured and decentralized P2P CDNs based on distributed hash tables (DHTs) has emerged. Nowadays, DHT algorithms are a powerful building block when designing distributed behaviors. However, sometimes DHTs are not flexible enough and problems arise when an efficient lookup in the DHT structure itself - instead of in the stored data - is required. Our motivation scenario is the resource discovery problem in a decentralized and distributed caching architecture, deployed in a set of clusters built from cheap off-the-shelf computers organized in a DHT overlay network. In this paper we present the design of a resource discovery service layered on the underlying DHT and based on the combination of (1) an spanning-tree built mapping DHT nodes to their parents in a bottom-up fashion, and (2) a set of routing indices which allow nodes to efficiently lookup other nodes in the DHT overlay network, matching some resource constraints This service does not alter the underlying DHT behavior, it scales to large wide area systems and it tracks both relatively static and frequently changing resources. Furthermore, the results of the experiments conducted to evaluate the good performance and scalability of the architecture are also presented.