In this work we present the average-case analysis of orthogonal range search for several multidimensional data structures. We first consider random relaxed K- d trees as a prototypical example. Later we extend these results to many different multidimensional data structures. We show that the performance of range searches is related to the performance of a variant of partial matches using a mixture of geometric and combinatorial arguments. This reduction simplifies the analysis and allows us to give exact lower and upper bounds for the performance of range searches. Furthermore, under suitable conditions ( “small range queries”), we can also get a very precise asymptotic estimate for the expected cost of range searches.