The expanding cloud computing services offer great opportunities for consumers to find the best service and best pricing. Meanwhile, it also raises new challenges for consumers who need to select the best service out of such a huge pool since it will be time-consuming for consumers to collect the necessary information and analyze all service providers to make the decision. Therefore, in this paper, we propose a novel brokerage-based architecture in the cloud, where the cloud brokers is responsible for the service selection. We also design an efficient indexing structure, called B$^{cloud}$-tree, for managing the information of a large number of cloud service providers. We then develop the service selection algorithm that recommends most suitable cloud services to the cloud consumers. We carry out extensive experimental studies on real and synthetic cloud data, and demonstrate a significant performance improvement over previous approaches.