The widespread of geospatial services produces massive volumes of spatial data. Cloud computing is a necessity for big data management. Efficient retrieval algorithms of such data are a prerequisite. In this paper, we evaluate the efficiency of spatial indexing for huge datasets at cloud computing environment. Two of the most common data structures are selected for this study namely the R-Tree and the priority R-tree (PR-Tree). R-Tree is one of the most common access methods for spatial data. Priority R-tree is an optimal variation of the R-tree and more efficient for extreme datasets. We implemented the two data structures then we deployed them on various cloud instances with different resources. We evaluated the performance of running these applications with different spatial datasets. The query response time is also measured for both data structures. We reported the results which can be useful in retrieving huge datasets on the cloud.