A computer performed method models a spatial index having n spatial regions defined in a multidimensional space using a tree-based model representing an infinite number of arrangements of n spatial regions in the multidimensional space allowable by the spatial index using a finite number of tree representations, computes an average retrieval complexity measure for content retrieval using the spatial index based on the tree based model, and provides a spatial index recommendation based on the average retrieval complexity measure. In some embodiments a spatial index selection module selects the spatial index based on average retrieval complexity measures for candidate spatial indices that are functionally dependent upon a number of spatial regions to be defined by the spatial index.