Distributed search has become a very important research area in light of the proliferation of peer-to-peer (P2P) networks. The convergence of fixed and mobile networks increases node dynamics further and adds to the complexity of the problem. This paper presents an exhaustive two-dimensional design space and a comprehensive survey of search designs. In the functional dimension, it identifies a series of mappings and integrated approaches like keyword lookup or semantic routing. In the structural dimension, design options for each mapping include computational approaches, central or completely replicated tables, classic or symmetric hierarchies, ordered spaces, and random structures and topologies. An evaluation of these design options serves as a guideline for system designers. Finally, it enables us to derive general implications and recommendations for P2P search design.