Le volume d'information contenu dans un entrepôt de données s'accroît sans cesse, augmentant de ce fait le temps d'exécution des requêtes décisionnelles. Pour y remédier, l'administrateur doit, durant la phase de conception physique de l'entrepôt, effectuer une sélection de structures d'optimisation (index, vues matérialisées ou fragmentation), puis assurer leur gestion et maintenance. Pour optimiser un nombre maximum de requêtes, il est indispensable d'opter pour une sélection multiple de structures ayant une forte similarité. Dans la littérature, deux principales similarités entre les structures d'optimisation ont été identifiées : une entre les vues et les index et l'autre entre la fragmentation horizontale dérivée et les index de jointure binaire. Dans ce travail, nous proposons une approche de sélection multiple des index de jointure binaire et de fragmentation. Vue la complexité de la sélection multiple, nous proposons une nouvelle approche permettant d'abord de partager l'ensemble des attributs extraits des requêtes entre les deux structures, ensuite sélectionner chaque structure avec un algorithme. Pour réaliser ce partage, nous proposons d'utiliser la méthode K-means. Une étude expérimentale et des tests comparatifs sur un entrepôt de données réel sous le SGBD Oracle 11g sont proposés illustrant l'intérêt de notre approche.