Les Tables de Hachage Distribuées (Distributed Hash Tables, ou DHT, en anglais) permettent la construction de réseaux pair-à-pair structurés pour des services de stockage persistant, hautement disponibles, et passant à l'échelle. Les fonctions de hachage utilisées pour générer les clés assurent une bonne répartition des objets sur les pairs du réseau et permettent la localisation très efficace d'un objet à partir de sa clé. Cependant, les DHTs sont peu efficaces pour gérer des requêtes complexes telles que les requêtes par intervalle. Pour pallier cela, plusieurs solutions ont été proposées dans la littérature. Dans cette thèse, nous nous intéressons plus particulièrement aux solutions reposant sur des arbres préfixes (trie en anglais) construit au-dessus des DHTs car ces arbres fournissent une solution portable et passant à l'échelle pour réaliser des requêtes complexes. Cependant, les méthodes de recherche proposées par les arbres préfixes distribués ont généralement une latence importante et génèrent un nombre de messages élevés qui dégradent les performances du système global. De plus, certaines des solutions proposées équilibrent mal la charge des noeuds et sont particulièrement inefficaces en cas d'arrivées et de départs massifs de noeuds (churn en anglais). Cette thèse vise donc à fournir de nouveaux supports pour les arbres préfixes au-dessus de DHT permettant de faire des requêtes complexes performantes. Nos approches assurent un bon un équilibrage de charge des noeuds stockant les index et offrent un surcoût limité en messages combiné à une latence faible. De plus, elles supportent mieux la dynamique du réseau pair-à-pair par rapport aux approches classiques. Nous avons étendu l'arbre préfixe PHT en proposant deux solutions: PORQUE et ECHO. PORQUE vise à réduire la latence tandis qu'ECHO fournit des recherches avec un faible surcoût. Nous avons implémenté et évalué ses deux solutions au-dessus du simulateur PeerSim. Les résultats des expérimentations confirment que PORQUE et ECHO peuvent réduire la latence et le trafic réseau de plus de 50% par rapport à PHT. Nos solutions équilibrent aussi la charge en évitant les goulets d'étranglement dans les noeuds stockant les niveaux supérieurs de l'arbre. Nous avons réalisé nos évaluations sur plusieurs ensembles de données (réels et synthétiques) ayant des répartitions de clés différentes. Les résultats montrent que nos solutions sont peu sensibles à l'asymétrie dans la distribution des clés tout en ayant une bonne résistance à la dynamique du réseau.