Data structures based on uniform subdivisions of the space —also known as bucketing— have the nice properties that they can be walked through very easily and can provide neighborhood relations at low cost. For data sets which are uniformly scattered in 2D or 3D space, this makes the imple- mentation of algorithms such as ray tracing, nearest neigh- bors computation or Delaunay triangulation almost trivial. But should the processed data set admit dense clusters, the spatial partitioning does not result in data partitioning so that the performances are collapsing. Although it has been known for a long time in dimension one that recursive bucket-sort admits a linear complexity for a wide range of probability densities, recursive bucket- like data structures have not received any attention in the computational geometry community. It has been observed in computer graphics that these were the fastest to ray-trace, but the question of understanding why they are not just another space partitioning data structure but rather the only data structure that succeeds in capturing the probabilistic properties of data distribution remains open. This paper is a first step in this direction and investi- gates hierarchical recursive and non recursive data struc- tures for ray-tracing. First, we show that precisely analyz- ing an optimized ray-tracer is a difficult task due to the context sensitivity of the calls costs of the functions called most often. Second, we exhibit statistics showing that if uniform grids are definitely not the right data structure to use for non-uniform distributions, recursive grids are very good at handling such distributions. Third, we present sev- eral improvements of the Hierarchy of Uniform Grids data structure, which result for the best cases in running times improved by up to a factor three with reference to the pre- viously best known solution.